JGit server performance

As Gerrit Code Review provides Gitosis-like functionality, but that is implemented through JGit's pure Java implementation, the performance of JGit's UploadPack matters to me.

JGit is about 66% slower on my hardware when cloning the linux-2.6 repository, compared to git-core (jgit 2m21s, git-core 1m23s).

The bottlenecks are:

  ~41.2% in ObjectLoader.getCachedBytes()

    This is the tree objects being parsed out of the pack file.
    The problem here (I believe) is we have horrible locality
    when reading.  The delta base for a tree isn't in memory most
    of the time, because its been evicted by other trees accessed
    since the last time that tree was touched.

    Conceptually this makes some sense, as ObjectWalk does a depth
    first traversal through the tree of each commit, in most-recent
    to least-recent commit order.  On a larger project like the
    kernel we'll touch a lot more objects between two root trees,
    and there isn't even any guarantee that two root trees that
    appear near each other in the commit sequence have a delta
    base relationship.

  ~20.5% in AbstractTreeIterator.getEntryObjectId()

    The bulk of the time here is really down in NB.decodeInt32().
    We spend a lot of time converting an object id in a tree data
    stream into an AnyObjectId (really a reused MutableObjectId)
    so that we can probe the ObjectIdSubclassMap to see if we have
    seen this object before.

    The sad fact is, we need all 20 bytes to be converted into the 5
    words, because the majority of the time, we have actually seen
    the object before, and it exists in our hash table.  The only
    way to know is to convert and compare all 5 words.  Any attempt
    to lazily convert the 5 words would just make it slower.

... and it falls off from there.

I'm at a loss on how to improve the performance. I don't think that we can do anything about the 20% in getEntryObjectId() due to the way our data structures are organized around the 5-word ObjectId, and not a byte[]. That 20% is a penalty git-core doesn't have to pay, and is most certainly one reason why JGit is so much slower.

The only thing that may work is to modify ObjectWalk to try and deduce some delta-chain locality from the pack. Buffer up objects that it needs to parse in a queue, rank them by the delta base they would need to use, and then try to unfold the base first, and then the children.

That is, do something like what IndexPack does, where we try to unpack each object exactly once, and recursively process the delta chain children after unpacking the parent.

We _might_ get better locality if we can queue up all root trees, process all of them, then process the first level children, etc, so go breadth first.

But that seems like a lot of code, and it probably wrecks the simple recency ordering produced natively by ObjectWalk. :-\