Re: [jgit-dev] Improving ObjectIdSubclassMap performance

[Robin Rosenberg <robin.rosenberg@xxxxxxxxxx>]

On 2011-03-09 02.36, Shawn Pearce wrote:
> 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.
>
Have you measured how much time is spend doing linear searches? Seems
only using half the table would mean lots of holes, but unlike other
tables the penalty for having one could be quite large, because you
steal buckets from the legitimate owners, and that could perhaps be much
more expensive that you expect.

Allowing more air than 50% in the table could give some hints about this
behavior, or even adding counters just for measuring.

@@ -123,7 +124,7 @@ public boolean contains(final AnyObjectId toFind) {
         *            type of instance to store.
         */
        public <Q extends V> void add(final Q newValue) {
-               if (obj_hash.length - 1 <= size * 2)
+               if (obj_hash.length - 1 <= size * 3)
                        grow();
                insert(newValue);
                size++;
@@ -160,7 +161,7 @@ public boolean contains(final AnyObjectId toFind) {
                                i = 0;
                }

-               if (obj_hash.length - 1 <= size * 2) {
+               if (obj_hash.length - 1 <= size * 3) {
                        grow();
                        insert(newValue);
                } else {

-- robin