Diffing Performance (formerly included traversal numbers)

[Byron]

Using the traversal program both commit graph iteration as well as tree diff performance can be tested on real repositories with various cache settings.

Here is the results on the Rust repository.

➜  gitoxide git:(main) ./target/release/traversal tests/fixtures/repos/rust.git master
gitoxide (cache = 57MB): confirmed 124032 commits in 781.275791ms (158756 commits/s)
gitoxide (static cache = 64 entries): confirmed 124032 commits in 632.266291ms (196171 commits/s)
gitoxide (uncached): confirmed 124032 commits in 632.609333ms (196064 commits/s)
libgit2: confirmed 124032 commits in 847.252375ms (146393 commits/s)
gitoxide (uncached): collect all 124032 commits in 633.130125ms (195903 commits/s)

gitoxide-deltas (cache = memory obj map -> 57MB pack): collect 143791165 tree deltas of 124032 trees-diffs in 101.410786208s (1417908 deltas/s, 1223 tree-diffs/s)
gitoxide-deltas PARALLEL (cache = memory obj map -> 57MB pack): collect 143791165 tree deltas of 124032 trees-diffs in 27.693899833s (5192160 deltas/s, 4479 tree-diffs/s)
gitoxide-deltas PARALLEL (cache = memory-lrup -> 57MB pack): collect 143791165 tree deltas of 124032 trees-diffs in 27.906228708s (5152655 deltas/s, 4445 tree-diffs/s)
libgit2: collect 118999693 tree deltas of 124032 trees-diffs in 398.488184541s (298628 deltas/s, 311 tree-diffs/s)
libgit2 PARALLEL: collect 118999693 tree deltas of 124032 trees-diffs in 143.317779458s (830321 deltas/s, 865 tree-diffs/s)

Traversing commits is fast for both, and I have a feeling that it's mostly limited by object access performance. gitoxide is about 25% faster when traversing commits on a single thread.

Producing tree deltas is even more intense when it comes to object access performance, and thus having a better cache is critical especially since many objects are reused-similar in two trees that are just a commit apart. gitoxide allows implementing any caching in that regard - it's transparent to the tree diff implementation. It appears that memory-capped LRU caches work similarly well here as they do for the pack cache. And sometimes, no pack cache is actually better as there are not enough hits to improve performance or amortize the cost.

As usual, gitoxide has a near 4x performance gain in multithreaded mode, whereas libgit2 gets a similar scaling factor as for object-access. Even with multithreading libgit2 is about 30% behind gitoxide, which certainly is due to the fact that it's an apples and oranges comparison. Better tuning of the algorithm options may help in that regard.

➜  gitoxide git:(main) ✗ cargo run --release --package traversal -- .git main
gitoxide (cache = 57MB): confirmed 2440 commits in 55.540375ms (43932 commits/s)
gitoxide (static cache = 64 entries): confirmed 2440 commits in 21.083791ms (115729 commits/s)
gitoxide (uncached): confirmed 2440 commits in 17.55ms (139031 commits/s)
libgit2: confirmed 2440 commits in 24.404583ms (99981 commits/s)
gitoxide (uncached): collect all 2440 commits in 17.313083ms (140934 commits/s)

gitoxide-deltas (cache = memory obj map -> 57MB pack): collect 42751 tree deltas of 2440 trees-diffs in 207.73625ms (205795 deltas/s, 11746 tree-diffs/s)
gitoxide-deltas PARALLEL (cache = memory obj map -> 57MB pack): collect 42751 tree deltas of 2440 trees-diffs in 49.155916ms (869702 deltas/s, 49638 tree-diffs/s)
gitoxide-deltas PARALLEL (cache = memory-lrup -> 57MB pack): collect 42751 tree deltas of 2440 trees-diffs in 52.134666ms (820011 deltas/s, 46802 tree-diffs/s)
libgit2: collect 23123 tree deltas of 2440 trees-diffs in 427.531666ms (54085 deltas/s, 5707 tree-diffs/s)
libgit2 PARALLEL: collect 23123 tree deltas of 2440 trees-diffs in 285.7305ms (80926 deltas/s, 8540 tree-diffs/s)

In smaller repositories commit iteration is relatively close with tree diffing once again being far behind which encourages playing with libgit2 diff options more, currently they use the default() settings.

[Byron]

And here is the results on the linux kernel:

➜  gitoxide git:(main) cargo run --release --package traversal -- ../../torvalds/linux/.git master
    Finished release [optimized] target(s) in 0.20s
     Running `target/release/traversal ../../torvalds/linux/.git master`
gitoxide (cache = 57MB): confirmed 1002691 commits in 7.14539625s (140327 commits/s)
gitoxide (static cache = 64 entries): confirmed 1002691 commits in 5.765122708s (173924 commits/s)
gitoxide (uncached): confirmed 1002691 commits in 5.693319625s (176117 commits/s)
libgit2: confirmed 1002691 commits in 8.869912333s (113044 commits/s)
gitoxide (uncached): collect all 1002691 commits in 5.707329166s (175685 commits/s)
Skipping tree diff as cache size would be too big (unbounded)
gitoxide-deltas PARALLEL (cache = memory-lrup -> 57MB pack): collect 5229041972 tree deltas of 1002691 trees-diffs in 1227.192581875s (4260979 deltas/s, 817 tree-diffs/s)
gst
alibgit2: collect 4488572386 tree deltas of 1002691 trees-diffs in 39081.768889833s (114851 deltas/s, 26 tree-diffs/s)
^C [aborted the parallel version of libgit2]

A typical linux kernel tree has up to 75k files which seems to slow down libgit2 to the point where it is unusable (at least to this experiment, being 31.5 times slower and taking more than 10h to complete). It also becomes clear that better settings have to be found for the diffing of libgit2 to speed it up.

[Byron]

Another repository with a complex directory tree with thousands of folders and files, each of the few commits contains many changed paths. Thus it's a good approximation for the linux kernel tree and thus a decent test environment for finding better diff options.

     Running `target/release/traversal ../../the-lean-crate/criner/criner.db/reports/waste/.git master`
gitoxide (cache = 57MB): confirmed 8477 commits in 83.901875ms (101035 commits/s)
gitoxide (static cache = 64 entries): confirmed 8477 commits in 28.789791ms (294445 commits/s)
gitoxide (uncached): confirmed 8477 commits in 28.299416ms (299547 commits/s)
libgit2: confirmed 8477 commits in 35.670458ms (237648 commits/s)
gitoxide (uncached): collect all 8477 commits in 28.887416ms (293450 commits/s)
gitoxide-deltas (cache = memory obj map -> 57MB pack): collect 912835 tree deltas of 8477 trees-diffs in 227.101096375s (4020 deltas/s, 37 tree-diffs/s)
gitoxide-deltas PARALLEL (cache = memory obj map -> 57MB pack): collect 912835 tree deltas of 8477 trees-diffs in 74.854970041s (12195 deltas/s, 113 tree-diffs/s)
gitoxide-deltas PARALLEL (cache = memory-lrup -> 57MB pack): collect 912835 tree deltas of 8477 trees-diffs in 72.148094s (12652 deltas/s, 117 tree-diffs/s)
libgit2 PARALLEL: collect 474300 tree deltas of 8477 trees-diffs in 209.199420791s (2267 deltas/s, 41 tree-diffs/s)

Despite the apples vs oranges issue we might be having, the less scalable parallel version of libgit2 is 10% faster than a single thread of gitoxide.

[Byron]

I came to believe that the libgit2 implementation handles ignore-case mostly, so apparently the options are as good as they get.

[Byron]

When testing once again a repository with huge trees…

     Running `target/release/diffing ../../the-lean-crate/criner/criner.db/reports/waste/.git master`
gitoxide (uncached): collect all 8539 commits in 31.358708ms (272301 commits/s)
gitoxide-deltas PARALLEL (cache = memory-LRU -> 57MB pack): collect 922471 tree deltas of 8539 trees-diffs in 62.542201125s (14750 deltas/s, 137 tree-diffs/s)
gitoxide-deltas PARALLEL (cache = memory obj map -> 57MB pack): collect 922471 tree deltas of 8539 trees-diffs in 71.027044791s (12988 deltas/s, 120 tree-diffs/s)
gitoxide-deltas (cache = memory obj map -> 57MB pack): collect 922471 tree deltas of 8539 trees-diffs in 258.579919791s (3567 deltas/s, 33 tree-diffs/s)
[…]

…it shows that a lot of time is actually spent parsing tree entries themselves. Even though nom is used it might be possible to optimize the parser and safe considerable time there.

[Byron]

Re-running the tree-diffing on a repository with a single pack but massive trees yields the following results (but not the program was refactored to use memory constrained caches at all time, with a bigger cache nonetheless).

$ GITOXIDE_OBJECT_CACHE_IN_BYTES=1000000000 cargo run --release --package diffing -- ../../the-lean-crate/criner/criner.db/reports/waste/.git master
gitoxide (uncached): collect all 8631 commits in 49.721291ms (173588 commits/s)
gitoxide-deltas PARALLEL (cache = memory-LRU -> 954MB | pack -> 954MB): collect 932539 tree deltas of 8631 trees-diffs in 65.412971625s (14256 deltas/s, 132 tree-diffs/s)
gitoxide-deltas (cache = memory-LRU -> 954MB | pack -> 954MB): collect 932539 tree deltas of 8631 trees-diffs in 167.102752833s (5581 deltas/s, 52 tree-diffs/s)
libgit2 PARALLEL: collect 483702 tree deltas of 8631 trees-diffs in 243.923255s (1983 deltas/s, 35 tree-diffs/s)
^C

Here the multi-threaded version only gains a 2.5x speedup over the single-threaded version, which is still about 50% faster than the parallel libgit2 variant.

It's hard to see where exactly all the time is spent but shows that using more advanced caches available to git should really be implemented eventually to speed this up.