Re: [jgit-dev] Improving ObjectIdSubclassMap performance

[Shawn Pearce <spearce@xxxxxxxxxxx>]

On Wed, Mar 9, 2011 at 16:28, Robin Rosenberg
<robin.rosenberg@xxxxxxxxxx> wrote:
> 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.

Sadly, we're sort of in a sweet spot at 50% load factor.

If I change the code to double the table when a linear chain gets
longer than 64, the same final table size is reached but its 1s
slower.

If I change the code to use 75% load factor, the same final table size
is reached, but its 3s slower.

If I change the code to use 25% load factor, the table is 33M entries
large (rather than 4M), and its 2s slower.


I have a few cleanups and micro optimizations that I'll upload in a
minute, these shaved a little bit off the running time, but we're
talking <1s for a 37s operation.


As far as chain lengths go, we're not that bad.

Here is the raw data. Objects is the number of items in the table at
the end, table is the size of the obj_hash array, wasted is the
difference. A hit is a successful get() returning an object, a miss is
a get that returned null and later turns into an insert. The number of
calls on chain lengths above 18 falls off fast so I elided it out.
With a 50% load factor, most operations have shorter than 7 items in
their chain. A wide majority are below 2.

objects: 1886362
table: 4194304
  (wasted 2307942)
chains (hit):
  length   0 : 42396217 get calls
  length   1 : 13675300 get calls
  length   2 : 6756795 get calls
  length   3 : 3759100 get calls
  length   4 : 2213449 get calls
  length   5 : 1413852 get calls
  length   6 : 1046289 get calls
  length   7 : 812226 get calls
  length   8 : 596076 get calls
  length   9 : 529995 get calls
  length  10 : 357039 get calls
  length  11 : 321895 get calls
  length  12 : 261752 get calls
  length  13 : 162623 get calls
  length  14 : 163727 get calls
  length  15 : 112538 get calls
  length  16 : 78401 get calls
  length  17 : 103203 get calls
  length  18 : 81563 get calls
  ...
  length >63 : 11553 get calls

chains (miss):
  length   0 : 872894 get calls
  length   1 : 345177 get calls
  length   2 : 187751 get calls
  length   3 : 117402 get calls
  length   4 : 78825 get calls
  length   5 : 55710 get calls
  length   6 : 41359 get calls
  length   7 : 31547 get calls
  length   8 : 24517 get calls
  length   9 : 19507 get calls
  length  10 : 15565 get calls
  length  11 : 12767 get calls
  length  12 : 10550 get calls
  length  13 : 8895 get calls
  length  14 : 7573 get calls
  length  15 : 6382 get calls
  length  16 : 5542 get calls
  length  17 : 4847 get calls
  length  18 : 4162 get calls
  ...
  length >63 : 1096 get calls

-- 
Shawn.