[jgit-dev] Performance of Inflaters

[Shawn Pearce <spearce@xxxxxxxxxxx>]

I just learned something about java.util.Inflater that I didn't really
know before.

If we have an input buffer we want to inflate, e.g.:

  byte[] input = new byte[1 * 1024 * 1024];

Passing the entire thing into the Inflater is a bad idea:

  inf.setInput(input, 12, input.length - 12);


The time it takes to perform inflation goes through the roof.  It
seems that the JNI layer is copying the entire array into an internal
buffer.  If we only needed 1024 bytes of that input for the current
inflation stream, we just wasted a huge amount of effort copying the
rest of the array.  This has a negative performance impact on
ObjectWalk, where it needs to inflate many thousands of tree objects,
and most of those are very small deltas (e.g. 40 bytes when
compressed).

Changing the code to only setInput() for 512 bytes at a time into the
Inflater improves performance considerably, what used to take 1.5
hours to "count" the 1.7 million objects in linux-2.6.git completes in
just minutes with the 512 byte stride.  So what I learned is,
PackChunk in the new storage.dht package needs to use a stride when
setting input into the Inflater, because chances are the Inflater
won't touch all of the data, it only needs a tiny fraction for each
decompress() invocation.

This also implies that PackParser might want to have its use of
Inflater reworked to use a small stride, because right now its usually
setting the entire 8192 byte buffer into the Inflater.  We may see
better performance with a smaller input size.  Highly compressed packs
have small delta objects, that makes most of the buffer not useful to
the current inflation attempt.

It also suggests we should revisit how PackFile does decompression.
When mmap is disabled (the default), we put the entire ByteArrayWindow
into the Inflater, even if only a small slice is needed.  At the
default size of 8192 bytes, this is about on par with PackParser and
isn't entirely horrible.  But if the user tries to increase the window
size to 64K or 1M (which I do on the Android code review servers I
run), there is definitely a negative performance impact.  If mmap was
enabled, we have the data in a ByteBuffer and have to copy it, in
which case we use a small stride temporary array... I just don't
recall off hand what size it is, but it might be 256 or 512 bytes.

Looks like I need to write some patches to fix how we use Inflater.

-- 
Shawn.