Traversal Performance: Commits and trees

[Byron]

When figuring out which objects to send during a clone (and without any caches like bitmaps/multi-pack indices) one will have to find all commits starting from given tips, whose trees need to be traversed deeply to find all objects that are present and to be sent to the receiver.

Here is how this looks like for the linux kernel.

➜  gitoxide git:(main) ✗ cargo run --release --package traversal -- ../../torvalds/linux/.git master
    Finished release [optimized] target(s) in 0.21s
     Running `target/release/traversal ../../torvalds/linux/.git master`
gitoxide (uncached): collect all 1002691 commits in 8.03117075s (124850 commits/s)
gitoxide PARALLEL (cache = 64 entries: confirmed 1456006498205 entries (6029750 unique objects) in 1002691 trees in 46.985600833s (30988355584 entries/s, 21340 trees/s)
gitoxide (cache = 64 entries: confirmed 388955942 entries (6029750 unique objects) in 1002691 trees in 145.741751583s (2668802 entries/s, 6880 trees/s)
libgit2: confirmed 388955942 entries (6029750 unique objects) in 1002691 trees in 226.263075125s (1719043 entries/s, 4432 trees/s))
gitoxide (cache = 57MB): confirmed 1002691 commits in 7.775986s (128947 commits/s)
gitoxide (static cache = 64 entries): confirmed 1002691 commits in 6.465030375s (155095 commits/s)
gitoxide (uncached): confirmed 1002691 commits in 6.376370541s (157251 commits/s)
libgit2: confirmed 1002691 commits in 14.07148175s (71257 commits/s)

Traversing ancestors in gitoxide on a hot cache is about 2.2x faster than it is in libgit2, interestingly it's best to not have any cache at all. Apparently commits are barely delta-compressed in a way that would help cache hits.

Tree traversal on a single thread is still 1.55x faster for gitoxide when compared to libgit2. More might be possible if different caching stategies are employed. When using multiple threads and a dashmap to collect unique objects, we get a scaling factor of 3.1x which clearly shows the synchronization costs coming with the in fact excellent dashmap implementation. It would be interesting to see scaling factors on 16 or 96 core machines.

The parallel version of libgit2 isn't yet implemented, but expected speedups are in the range of 2x maximum from prior experience.