HashMap - Hybrid approach (original) (raw)

Doug Lea dl at cs.oswego.edu
Fri Jun 12 14:23:58 UTC 2009

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

More information about the core-libs-dev mailing list