read-cache: make the index write buffer size 128K

From: Neeraj Singh <[email protected]>

Writing an index 8K at a time invokes the OS filesystem and caching code very frequently, introducing noticeable overhead while writing large indexes. When experimenting with different write buffer sizes on Windows writing the Windows OS repo index (260MB), most of the benefit came by bumping the index write buffer size to 64K. I picked 128K to ensure that we're past the knee of the curve.

With this change, the time under do_write_index for an index with 3M files goes from ~1.02s to ~0.72s.

Quoted 10 lines · Neeraj K. Singh via GitGitGadget

From: Neeraj Singh <[email protected]>
Writing an index 8K at a time invokes the OS filesystem and caching code
very frequently, introducing noticeable overhead while writing large indexes. When experimenting with different write buffer sizes on Windows writing the Windows OS repo index (260MB), most of the benefit came by bumping the index write buffer size to 64K. I picked 128K to ensure that we're past the knee of the curve.
With this change, the time under do_write_index for an index with 3M files goes from ~1.02s to ~0.72s.

[...]

Quoted 4 lines

-#define WRITE_BUFFER_SIZE 8192
+#define WRITE_BUFFER_SIZE (128 * 1024)
static unsigned char write_buffer[WRITE_BUFFER_SIZE]; static unsigned long write_buffer_len;

[...]

Very nice.

Quoted 14 lines · Jeff Hostetler

Quoted 10 lines · Neeraj K. Singh via GitGitGadget

From: Neeraj Singh <[email protected]>
Writing an index 8K at a time invokes the OS filesystem and caching code
very frequently, introducing noticeable overhead while writing large indexes. When experimenting with different write buffer sizes on Windows writing the Windows OS repo index (260MB), most of the benefit came by bumping the index write buffer size to 64K. I picked 128K to ensure that we're past the knee of the curve.
With this change, the time under do_write_index for an index with 3M files goes from ~1.02s to ~0.72s.

[...]

Quoted 8 lines

Quoted 4 lines

-#define WRITE_BUFFER_SIZE 8192
+#define WRITE_BUFFER_SIZE (128 * 1024)
static unsigned char write_buffer[WRITE_BUFFER_SIZE]; static unsigned long write_buffer_len;

[...]

Very nice.

I wonder if we gain more by going say 4M buffer size or even larger?

Is this something we can make the system auto-tune itself? This is not about reading but writing, so we already have enough information to estimate how much we would need to write out.

Thanks.

Quoted 15 lines

Quoted 8 lines

Quoted 4 lines

-#define WRITE_BUFFER_SIZE 8192
+#define WRITE_BUFFER_SIZE (128 * 1024)
static unsigned char write_buffer[WRITE_BUFFER_SIZE]; static unsigned long write_buffer_len;

[...]

Very nice.

I wonder if we gain more by going say 4M buffer size or even larger?

Is this something we can make the system auto-tune itself? This is not about reading but writing, so we already have enough information to estimate how much we would need to write out.

Quoted 2 lines

Thanks.

Hi Junio,
At some point the cost of the memcpy into the filesystem cache begins to dominate the cost of the system call, so increasing the buffer size has diminishing returns.

Quoted 15 lines · Neeraj Singh

Quoted 15 lines

Quoted 8 lines

Quoted 4 lines

-#define WRITE_BUFFER_SIZE 8192
+#define WRITE_BUFFER_SIZE (128 * 1024)
static unsigned char write_buffer[WRITE_BUFFER_SIZE]; static unsigned long write_buffer_len;

[...]

Very nice.

I wonder if we gain more by going say 4M buffer size or even larger?

Is this something we can make the system auto-tune itself? This is not about reading but writing, so we already have enough information to estimate how much we would need to write out.

Quoted 7 lines

Quoted 2 lines

Thanks.

Hi Junio,
At some point the cost of the memcpy into the filesystem cache begins to dominate the cost of the system call, so increasing the buffer size has diminishing returns.

Yes, I know that kind of "general principle".

If I recall correctly, we used to pass too large a buffer to a single write(2) system call (I do not know if it was for the index---I suspect it was for some other data), and found out that it made response to ^C take too long, and tuned the buffer size down.

I was asking where the sweet spot for this codepath would be, and if we can take a measurement to make a better decision than "8k feels too small and 128k turns out to be better than 8k". It does not tell us if 128k would always do better than 64k or 256k, for example.

I suspect that the sweet spot would be dependent on many parameters (not just the operating system, but also relative speed among memory, "disk", and cpu, and also the size of the index) and if we can devise a way to auto-tune it so that we do not have to worry about it.

Thanks.

If we think about doing the fastest possible memcpy, I think we want to aim for maximizing the use of the CPU cache. A write buffer that's too big would result in most of the data being flushed to DRAM between when git writes it and the OS reads it. L1 caches are typically ~32K and L2 caches are on the order of 256K.
We probably don't want to exceed the size of the L2 cache, and we should actually
leave some room for OS code and data, so 128K is a good number from that perspective.

I collected data from an experiment with different buffer sizes on Windows on my 3.6Ghz Xeon W-2133 machine:
https://docs.google.com/spreadsheets/d/1Bu6pjp53NPDK6AKQI_cry-hgxEqlicv27dptoXZYnwc/edit?usp=sharing

The timing is pretty much in the noise after we pass 32K. So I think 8K is too small, but
given the flatness of the curve we can feel good about any value above 32K from a performance
perspective. I still think 128K is a decent number that won't likely need to be changed for
some time.

Quoted 4 lines · Neeraj Singh

I collected data from an experiment with different buffer sizes on Windows on my 3.6Ghz Xeon W-2133 machine:
https://docs.google.com/spreadsheets/d/1Bu6pjp53NPDK6AKQI_cry-hgxEqlicv27dptoXZYnwc/edit?usp=sharing

Quoted 7 lines

The timing is pretty much in the noise after we pass 32K. So I think 8K is too small, but
given the flatness of the curve we can feel good about any value above 32K from a performance
perspective. I still think 128K is a decent number that won't likely need to be changed for
some time.

Thanks for a supporting graph.

I can very well imagine that it would have been tempting to instead say "after we pass 128k" while explaining exactly the same graph, and doing so would have given a more coherent argument to support the choice of 128k the patch made. You knew that a "then perhaps we can reclaim 96k by sizing the buffer down a bit?" would become a reasonable response, but you still chose to be honest, which I kinda like ;-)

Linux/BSD/etc stat system calls report st_blksize values to tell user code the optimal size for read and write calls. Does Windows have one? (It's not POSIX but is XSI.)

(How *well* the OS reports st_blksize is another question entirely, but at least if the report says, say, 128k, and that's wrong, that's no longer Git's fault. :-) )
...
128K is correct for ZFS; 64K is typically correct for UFS2; 8K is the old UFS1 size. Anything under that has been too small for a long time. :-)

Quoted 11 lines · Chris Torek

Linux/BSD/etc stat system calls report st_blksize values to tell user code the optimal size for read and write calls. Does Windows have one? (It's not POSIX but is XSI.)

(How *well* the OS reports st_blksize is another question entirely, but at least if the report says, say, 128k, and that's wrong, that's no longer Git's fault. :-) )
...
128K is correct for ZFS; 64K is typically correct for UFS2; 8K is the old UFS1 size. Anything under that has been too small for a long time. :-)

That's rather tempting. After opening a locked index to write things out, the value is a single fstat() away...

From a quick perusal of freebsd, st_blksize seems to be the system PAGE_SIZE by default (4k most of the time, I assume). The Windows equivalent of this value is really tuned to what you want to send down when bypassing the cache (to avoid partial cluster/stripe writes).

https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/sys_stat.h.html
doesn't elicit much confidence. The units of st_blksize aren't even defined.