[jgit-dev] Improving ObjectIdSubclassMap performance

[Shawn Pearce <spearce@xxxxxxxxxxx>]

One of the profiling tools I have access to at $DAY_JOB is telling me
the obj_hash table within ObjectIdSubclassMap is one of the major
sources of garbage when enumerating all objects in the linux-2.6
repository. This makes some sense as the obj_hash table needs to be
about 4 million entries large to store the entire 1.8 million object
list that PackWriter is discovering during the enumeration phase (as
the table is only powers of 2, doubles on each expansion, and expands
when its at 50% capacity). As a source of garbage, the GC is spending
an inordinate amount of time trying to allocate the next largest table
size during expansions.

Unfortunately I can't do better. So I'm looking for ideas.

My extendible hashing patch that I abandoned today[1] was slower by
several seconds (~37s current code, ~42s extendible hashing) despite
having the property that it should never generate garbage. The extra
array lookups and branches during get() and add() completely
overshadowed the GC savings.

I tried using plain java.util.HashMap just to compare, and our current
code is faster (~37s current code, ~39s HashMap). So moving to HashMap
isn't a solution. :-)

I tried implementing linear hashing[2], but the table has a bug that
is causing some objects to be lost during a resize. Even if I fix that
(its only 6%) I don't think its going to beat the current code, its
too complex and is using a unique ArrayList inside of each hash
bucket. I don't think its useful to try and fix the resize bug,
removing the 6% duplicates may not save enough work to drop the time,
and the overall memory footprint is quite a bit bigger.

I hardcoded ObjectIdSubclassMap to initially allocate its obj_hash at
3,600,000 entries, 2x the final size, thus ensuring it never grows.
This shaved about 500 milliseconds off the running time, but its
difficult to get an estimate for the table size in advance. If
PackWriter is doing a full repacking, we can guess close by summing up
the object counts from the PackFile instances of the source
Repository, but this doesn't correctly include the loose objects. I'm
not sure saving 1.3% of the running time is worth the code complexity
to define APIs exposing an estimated object count from ObjectDatabase
up to PackWriter. Getting that count from the PackFiles may require
500 milliseconds itself if there are more than a handful of pack
files.

So I think I've hit a wall here, PackWriter is about as fast as its
getting anytime soon. But I'd still like to improve that counting
phase. :-(


Profiling shows our real hot spots are ~30% inflate() and ~30%
ObjectIdSubclassMap (the other 40% is in tiny pockets that aren't
worth major mention). Dropping inflate requires switching the pack
format to store commit tree/parent pointers uncompressed, and trees
uncompressed. This isn't going to happen anytime soon. Hence my
attempt to speed up the other 30%.


[1] http://egit.eclipse.org/r/2670
[2] http://citeseer.ist.psu.edu/griswold93design.html

-- 
Shawn.