HashMap - Hybrid approach

[Doug Lea]

Alex Yakovlev wrote:
>> This suggests a
>> different sort of tactic for helping with indirections and
>> prefetches.  Suppose that index[h] was usually just h; that is,
>> with the key in elements[2*h]. 
> 
> I did a little test of this and saw no performance gain,
> I even posted a link to sources right after changing subject
> from 'fast' to 'hybrid'.
> 
> Do you have any idea why second array prefetching may not happen?

This was fun to figure out. Performance on some of our
tests involving get() is sensitive to the serial
correlation of slot indices for the keys used across
successive calls. The current bit-spreading function
is biased to improve locality without hurting collisions
too much for numerically nearby hashCodes. So on tests where
this holds, prefetching buys very little since cache misses
are already relatively low. I'll check in some tests I threw
together that help diagnose this after some cleanup.
(One reason for having several tests that have this bias
is that they are good indicators of performance on
other artificial benchmarks like specjbb.)

As another quick experiment, I just tried a hacked
version of IdentityHashMap carrying hashes
array, and did see around a 20% improvement in some
tests for get() versus version with index-dependence.
So some variant of direct access still seems likely to
be worth pursuing.
I'll try to put together a more serious version along
the lines of my suggestions, although maybe not for
a few days.

-Doug