Checking out the Linux kernel in under a second

[Byron]

Here we will explore how to increase the speed when checking out a repository using the Linux kernel as popular and well-known example. We will see how fast we can go with git itself and then transition to an early implementation provided by gitoxide while trying to make it as comparable as possible while pointing out the differences.

Tl;dr

On tmpfs, one can now checkout v5.16 of the Linux kernel in ~874ms, which equals more than 85k files/s and 1.2GB/s on a machine with 8hpc/2ec on MacOS 12. gix, the plumbing binary of gitoxide, is 1.8 times faster than git with multi-threaded checkout (even though it's not a perfect apples to apples comparison, see Caveats).

Here is the results measured on a 10 core MacBook…

…with 10 cores…

	wallclock	files	throughput	speedup	efficiency¹
git	1.584s	49.9k/s	689MB/s	1x	40%
gix	874ms	85.8k/s	1.3GB/s	1.81x	60%

…and with a single core… .

	wallclock	files	throughput	speedup
git	5.084s	14.6k/s	214.8MB/s	1x
gix	4.447s	16.7k/s	246MB/s	1.14x

Take a look below the fold at the very bottom of the document for another table showing results of checking out on a real file system - gix will do that in ~3.3s and git takes 4.6s. There you also find instructions for how to repeat the test on your system.

Bonus: gix on even more powerful CPUs with 10-core limit

CPU	wallclock	files	throughput
Intel Xeon Gold 6248 CPU @ 2.50GHz	548.3ms	135.6k/s	2.0GB/s
AMD EPYC 7643 48-Core Processor	402.5ms	184.8k/s	2.7GB/s

For details of the runs, see this comment and this one.

What is 'efficiency¹'?

This value measures the effective scaling and the difference between 100% and the actual value would be waste.

If a single core finishes the task in X time, then N cores should finish in X/N time if they would scale perfectly.

The percentage is calculated using <files/s measured for N> / (<files/s measured for 1> * N).

N is 8.5 (8HP cores + (2E cores * 0.25).

What is a 'checkout'?

git will create an index from a tree if none is present and use the in-memory index to checkout files. From what I can see, it will always check for existence of the file prior to writing it using lstat as it uses this as part of its collision detection mechanism along with change detection. Once a file is written, another lstat call is issued to update that information in the in-memory index. Finally, the in-memory index is written back to disk.

git pays great attention to not allow symlinks in the path of a file that is being checked out nor will it write through a symlink. Additionally it will track collisions on file systems that are case-sensitive or have other folding rules for that matter.

Caveats

gitoxide in its current very specialized implementation named checkout-exclusive requires the target directory is empty and fully under its control, hence the -exclusive suffix, a situation that would be present for initial clones. It needs an index to be present and will not write the updated in-memory index back to disk, thus it does less work than git. It does, however, pay the same attention to correctness as git does, and detects collisions while avoiding to write through symlinks.

Creating an index from the tree at v5.16 of the linux kernel appears to take 200ms (time git read-tree HEAD), and is something that typically doesn't have to be done as an existing index is used. It's something we do in our tests to force git to actually perform the full checkout. Writing the index back with a single thread seems to take 40ms using touch a && time git add a with a single thread. If gitoxide were to perform all these operations (none of which are implemented) equally well one would have to add ~240ms to the results. Having marked a sub-second checkout time for the linux kernel I will be hard pressed to assure to stay sub-second even when these operations are done.

Special Thanks

• @joshtriplett got this article started by suggesting to run it on TMPFS to minimize IO cost, and pushed for the sub-second headline you see here now. Previously I planned to get to less than 2 seconds only. Additionally the git invocation with hyperfine was provided by him and was used just like that. Oh, and he is the reason you can read those tables, there were much more complicated before. Thank you!
• @sharkdp as the author of hyperfine, an indispensable tool to run benchmarks and comparisons, and sometimes it can help reproduce race conditions, too.
• @pmmccorm for contributing additional results on very powerful machines, setting a new performance record right away.

Reproduction and Measurements

Setup

Initial State

# assuming the working directory is tmpfs or the file system under test
git clone https://github.com/torvalds/linux
cd linux && git checkout v5.16

$ git --version
git version 2.32.0 (Apple Git-132)

The exact version of gix used here is at 3f28e20 , and can be installed like so:

cargo install --git https://github.com/Byron/gitoxide --rev 3f28e2037fcb07fa022220e52bcf967d6d6ef647 --locked

On MacOS, the tmpdisk program can be used to create a tmpfs file system in memory.

Measurements

All scripts that follow assume to start out in the linux clone created as the initial state.

git

10 cores on tmpfs

hyperfine -p 'git checkout -f v5.16 && rm -rf .git/index * .clang-format .cocciconfig .get_maintainer.ignore .gitattributes .gitignore .mailmap' 'git -c checkout.workers=-1 checkout v5.16'

Benchmark 1: git -c checkout.workers=-1 checkout v5.16
  Time (mean ± σ):      1.584 s ±  0.012 s    [User: 3.776 s, System: 3.707 s]
  Range (min … max):    1.570 s …  1.614 s    10 runs

1 core on tmpfs

hyperfine -p 'git checkout -f v5.16 && rm -rf .git/index * .clang-format .cocciconfig .get_maintainer.ignore .gitattributes .gitignore .mailmap' 'git -c checkout.workers=1 checkout v5.16'

Benchmark 1: git -c checkout.workers=1 checkout v5.16
  Time (mean ± σ):      5.084 s ±  0.049 s    [User: 3.213 s, System: 1.833 s]
  Range (min … max):    5.002 s …  5.159 s    10 runs

1 core on APFS/SSD

hyperfine -p 'git checkout -f v5.16 && rm -rf .git/index * .clang-format .cocciconfig .get_maintainer.ignore .gitattributes .gitignore .mailmap' 'git -c checkout.workers=1 checkout v5.16'

Benchmark 1: git -c checkout.workers=1 checkout v5.16
  Time (mean ± σ):      7.911 s ±  0.109 s    [User: 3.333 s, System: 4.278 s]
  Range (min … max):    7.792 s …  8.061 s    10 runs

10 cores on APFS/SSD

hyperfine -p 'git checkout -f v5.16 && rm -rf .git/index * .clang-format .cocciconfig .get_maintainer.ignore .gitattributes .gitignore .mailmap' 'git -c checkout.workers=0 checkout v5.16'

Benchmark 1: git -c checkout.workers=0 checkout v5.16
  Time (mean ± σ):      4.622 s ±  0.026 s    [User: 4.246 s, System: 22.237 s]
  Range (min … max):    4.592 s …  4.673 s    10 runs

gitoxide

10 cores on tmpfs

hyperfine -p 'rm -Rf ../gix-linux-1' 'GITOXIDE_PACK_CACHE_MEMORY=32MB gix -t 0 index checkout-exclusive -r . ../gix-linux-1' -i

Benchmark 1: GITOXIDE_PACK_CACHE_MEMORY=32MB gix -t 0 index checkout-exclusive -r . ../gix-linux-1
  Time (mean ± σ):     874.2 ms ±  12.0 ms    [User: 3152.7 ms, System: 3338.7 ms]
  Range (min … max):   852.1 ms … 899.1 ms    10 runs

  Warning: Ignoring non-zero exit code.

1 core on tmpfs

hyperfine -p 'rm -Rf ../gix-linux-1' 'GITOXIDE_PACK_CACHE_MEMORY=32MB gix -t 1 index checkout-exclusive -r . ../gix-linux-1' -i

Benchmark 1: GITOXIDE_PACK_CACHE_MEMORY=32MB gix -t 1 index checkout-exclusive -r . ../gix-linux-1
  Time (mean ± σ):      4.447 s ±  0.012 s    [User: 2.782 s, System: 1.637 s]
  Range (min … max):    4.425 s …  4.467 s    10 runs

  Warning: Ignoring non-zero exit code.

1 core on APFS/SSD

hyperfine -p 'rm -Rf ../gix-linux-1' 'GITOXIDE_PACK_CACHE_MEMORY=32MB gix -t 1 index checkout-exclusive -r . ../gix-linux-1' -i

Benchmark 1: GITOXIDE_PACK_CACHE_MEMORY=32MB gix -t 1 index checkout-exclusive -r . ../gix-linux-1
  Time (mean ± σ):      6.820 s ±  0.064 s    [User: 2.869 s, System: 3.654 s]
  Range (min … max):    6.737 s …  6.920 s    10 runs

  Warning: Ignoring non-zero exit code.

10 cores on APFS/SSD

 hyperfine -p 'rm -Rf ../gix-linux-1' 'GITOXIDE_PACK_CACHE_MEMORY=32MB gix -t 0 index checkout-exclusive -r . ../gix-linux-1' -i

Benchmark 1: GITOXIDE_PACK_CACHE_MEMORY=32MB gix -t 0 index checkout-exclusive -r . ../gix-linux-1
  Time (mean ± σ):      3.303 s ±  0.035 s    [User: 3.501 s, System: 17.385 s]
  Range (min … max):    3.240 s …  3.341 s    10 runs

  Warning: Ignoring non-zero exit code.

Appendix

Checking out on APFS/SSD

	core count	wallclock	files	throughput	speedup	efficiency¹
gix	10	3.303s	22.5k/s	331MB/s	1.40x	24%
gix	1	6.820s	11.2k/s	160MB/s	1.16x	100%
git	10	4.622s	16.1k/s	236MB/s	1x	20%
git	1	7.911s	9.4k/s	138MB/s	1x	100%

[LoganDark]

10 core MacBook

Off topic, but how in the world did you achieve this? M1?

[Byron]

Yes, an M1 Pro. This machine is certainly a factor but I expect other computers to achieve the same.

[pmmccorm]

What is the locking here?

x$ strace -c gix -t 20 index checkout-exclusive -r . ../gix-linux-1
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
 99.24    1.153210       12813        90           futex
  0.52    0.006044         671         9           munmap
  0.07    0.000764          36        21           clone
  0.06    0.000755          14        51           mmap
  0.03    0.000346          11        30           mprotect
  0.01    0.000157           1        83         4 statx

[pmmccorm]

Also looking at @cbane 's numbers I wonder if they fixed some concurrency issue in newer git.

[Byron]

Also looking at @cbane 's numbers I wonder if they fixed some concurrency issue in newer git.

I wouldn't be surprised if the worker option is entirely ignored in your case. And after checking the code I could validate this assumption. You could probably build it from source for a more recent version.

[Byron]

What is the locking here?

Thanks for the strace , very helpful! Actually all object database access is practically lock-free, but the way parallelization is done is through two channels are definitely locked and a place for contention. One is for receiving work, another one is for sending the result for aggregation, both with a buffer of the amount of threads used.

In 3b324b8 I swapped in a crossbeam channel which might be faster to receive the results, maybe that helps a little bit. Ultimately maybe there needs to be another version of the fan-out-fan-in-style parallelization that avoids communicating inputs and outputs, and instead operates on mutable chunks of vectors, one is the input, one is pre-allocated for the output.

Would you be able to run it once more if I gave that a shot?

[Byron]

Would you be able to run it once more if I gave that a shot?

I tried a different way of parallelizing the work but didn't see any speed-up. In theory, it should have advantages when starting work and be more fine-grained when stealing work, but it lost more than it won probably due to it not checking paths out in sort order anymore, causing more work for tmpfs.

Thinking about it, the current parallelization is able to scale to 870k decoded object per second on the linux kernel repo, so it's probably slowed down by the file system. The futex calls don't seem to show up in my instrumentation runs on MacOS, maybe they are hidden or they don't contribute significantly to the overall cost. The instrumentation run, however, shows that some threads aren't busy for 30ms-70ms towards the end of the operation, which might mean the chunk size could be lower. When doing so, however, it usually gets slower instead of faster so I feel I am out of ideas here.

Thus, I have to give up on my hope to achieve ~0.5s checkouts on my system, but am happy it can already be done for those with a beefier machine.

If you want, you can see how well the CPU scales with non-IO dependent work with this invocation, which is ~11GB/s when resolving the pack on my machine.

./target/release/gix  -t0 --verbose pack  index create -p  /<linux>/.git/objects/pack/<hash>.pack

I'd expect the machine to scale very well with each core.