[PATCH 2/2] use zstd zlib wrapper

There's a fancy new compression algorithm called "zstd". The idea is that it's supposed to get similar compression ratios to zlib, but with much faster compression and decompression times. And on top of that, a nice sliding scale to trade off size versus time on the compression side.

The zstd site at https://facebook.github.io/zstd/ claims close to 3x speedup for both compression and decompression versus zlib, with similar compression ratios. There are other fast algorithms (like lz4), but they usually compress much worse (follow the link above for a nice table of results).

Since any git operations that have to access objects need to do a zlib inflate, in theory we can speed up everything by using zstd. And then on the packing side, use higher compression levels when making on-disk packfiles (which will be accessed many times) and lower ones when making loose objects, or deflating packed objects on the fly when serving fetches.

The catch, of course, is that it's a new incompatible format. This would be a pretty huge change and totally break backwards compatibility for git, not just on disk but on-the-wire as well. So my goal here was not a finished product but just a quick experiment to see if it did indeed bring the promise speedups.

Disappointingly, the answer seems to be "no".

The patch is relatively straightforward. zstd ships with a zlib-compatible wrapper that we can just plug in. For compression, it writes with zlib by default, but you can flip it to zstd mode with a run-time flag. For decompression, it auto-detects and runs the correct choice between zlib and zstd. So this patch _could_ serve as the basis for a real solution. We'd bundle zstd and its wrapper with the runtime switch off, and then after several years people could enable zstd writing to cut off older clients. In the patch below, that switch is just setting the pack.compression level to "zstd1", "zstd2", etc.

I ran a series of tests where I would:

  1. Repack with "-F" and a particular pack.compression
     setting, measuring both the time to repack and the size
     of the resulting pack.

  2. Time "git rev-list --objects --all" to see the effect
     on commit/tree traversal.

  3. Run "log -Sfoo --raw" to see the additional effect on
     accessing the blobs.

All the timings below are against linux.git. The rev-list timings are best-of-five, but I didn't do multiple timings for the repack or "log -S" tests, because they were so painfully slow (and because the effect sizes seemed to be larger than run-to-run noise).

I did these on top of my delta-cache and pack-mru patches, since that would amplify any effect we see (i.e., those speed up other things so decompression time is a relatively larger share of the pie).

Here's a baseline run using stock zlib, with the default compression settings:

 [zlib]
 - pack
   1122845190
 - repack
   real    4m43.817s
   user    17m32.396s
   sys     0m5.964s
 - rev-list --objects --all
   real    0m27.378s
   user    0m27.132s
   sys     0m0.240s
 - log -Sfoo --raw
   real    5m3.490s
   user    5m0.040s
   sys     0m3.424s

You can see that we're pretty much CPU bound. You can also see that there's quite a bit of parallelism going on in the repack (this is a quad-core with hyperthreading).

Here's the same thing built against the zstd wrapper, but still using zlib:

 [zstd, disabled]
 - pack
   1123089975
   (+0.02%)
 - repack
   real    4m58.263s
   user    17m50.596s
   sys     0m7.200s
   (+5%)
 - rev-list --objects --all
   real    0m28.143s
   user    0m27.864s
   sys     0m0.272s
   (+3%)
 - log -Sfoo --raw
   real    5m12.742s
   user    5m9.804s
   sys     0m2.912s
   (+3%)

The percentages show the difference against the baseline run above (wall-clock times for the timing results). The pack size is similar, which we'd expect (it's not identical because the threaded delta search is slightly non-deterministic).

Sadly we lose 3-5% just to the wrapper sitting in front of zlib. So that's not a great start. But it also means we might be able to recover that through code optimizations of the wrapper, the way we call it, etc.

Now here it is with zstd turned onto its lowest setting:

 [zstd, 1]
 - pack
   1199180502
   (+7%)
 - repack
   real    4m11.740s
   user    16m36.510s
   sys     0m7.700s
   (-11%)
 - rev-list --objects --all
   real    0m25.870s
   user    0m25.632s
   sys     0m0.232s
   (-5.5%)
 - log -Sfoo --raw
   real    4m10.899s
   user    4m7.788s
   sys     0m3.056s
   (-17%)

We've definitely traded off some space here. But the compression is faster, _and_ so is the decompression.

So let's bump up the compression level a bit:

 [zstd, 3]
 - pack
   1162416903
   (+3.5%)
 - repack
   real    5m1.477s
   user    19m34.476s
   sys     0m17.720s
   (+6.2%)
 - rev-list --objects --all
   real    0m25.716s
   user    0m25.468s
   sys     0m0.244s
   (-6%)
 - log -Sfoo --raw
   real    4m10.547s
   user    4m6.500s
   sys     0m3.884s
   (-17%)

OK, the size is improving. But now our compression is noticeably slower. The decompression remains better, which is nice. Let's go further:

 [zstd, 5]
 - pack
   1144433165
   (+2%)
 - repack
   real    5m46.050s
   user    22m7.580s
   sys     1m2.212s
   (+22%)
 - rev-list --objects --all
   real    0m25.717s
   user    0m25.404s
   sys     0m0.304s
   (-6%)
 - log -Sfoo --raw
   real    4m14.651s
   user    4m11.176s
   sys     0m3.448s
   (-16%)

Getting close to parity on the size. But the compression time keeps creeping up.

 [zstd, 10]
 - pack
   1132922195
   (+0.8%)
 - repack
   real    41m35.835s
   user    166m36.956s
   sys     50m11.436s
   (+780%)
 - rev-list --objects --all
   real    0m25.946s
   user    0m25.656s
   sys     0m0.284s
   (-5%)
 - log -Sfoo --raw
   real    4m8.490s
   user    4m5.864s
   sys     0m2.604s
   (-18%)

Oof. We still haven't reached size parity, and now we're using a _lot_ more CPU on the repack.

I wanted to take it all the way to "22", zstd's maximum, just for fun. But after 2 hours (real time, so pegging all my cores while doing so), we were only at 12% of the delta phase. Yikes.

So...it doesn't seem like a great tradeoff (especially considering the costs in migrating to a new algorithm). The decompression _is_ delightfully faster, and it's true that we decompress more than we compress. But the speed/size tradeoff for compression doesn't seem great.

I'm not sure why we don't get numbers as nice as the ones on the zstd website. Obviously possibility 0 is that I simply screwed something up. But here are some other thoughts / wild guesses:

  1. There's clearly some overhead to using the zlib
     wrapper. Even just calling into zlib with it to
     compress seems to cost about 5%.

     For zstd, it's less clear. The regular (non-wrapper)
     zstd API seems to involve allocating a zstd compressor,
     and then feeding multiple compressions to it. So that
     would amortize the setup cost. I'd guess that the zlib
     wrapper has to allocate a new zstd compressor for each
     wrapped compression (obviously they could share one,
     but then you run into threading issues).

     The fact that the time increases as we bump the
     compression level implies to me that the main cost is
     in the actual compression, though, not in the setup.
     It's possible that the setup cost is higher when the
     compression level is higher, but I wouldn't really
     expect it to scale as rapidly as my numbers show.

     So this is probably making things worse than they
     otherwise could be, but I doubt it's the real cause of
     the problems.

  2. Git tends to do a lot of relatively small compressions,
     as we zlib-compress deltas. So I wonder (and this is a
     wild guess) if zstd performs more favorably on "normal"
     sized inputs.

     That would be possible to test. Or could probably be
     found out by digging more into the zstd benchmarks;
     they used some standard corpuses, but the results are
     summarized. More broken-down results may show patterns.

     I didn't do those things, hence "wild guess".

And obviously even this patch series _does_ show an improvement on the decompression side (which happens a lot more often than compression!). So this isn't a total dead end. But given the ratio/time tradeoff I saw on the compression side, there are other options. E.g., lz4 is even faster than zstd, but comes with a size penalty (though I think it's more like 30%, not 7%).

I would have liked to test with lz4, too, but they don't ship a totally trivial zlib wrapper. :)

Signed-off-by: Jeff King <peff@peff.net>
---
 Makefile               |  9 +++++++++
 builtin/pack-objects.c | 19 +++++++++++++------
 cache.h                |  4 ++++
 3 files changed, 26 insertions(+), 6 deletions(-)