Faster HashMap implementation
dl at cs.oswego.edu
Mon Jun 8 07:24:57 PDT 2009
Alex Yakovlev wrote:
> I've finished HashMap, HashSet, LinkedHashMap, and LinkedHashSet
> porting to my approach. I run several tests I've found in
> that are directly related to these classes, not sure I've found all of them.
There are a lot of tests around for HashMaps, strewn all over.
The ones in you found are the "jtreg" regression tests that
correspond to bug reports.
We JSR166 folks have a bunch of miscellaneous functionality
and performance tests for maps.
Some of them are geared to concurrent maps, but if you grab the tarball at
you can browse through *Map*.java to find ones that apply,
such as MapCheck, MapWordLoops, DenseMapMicroBenchmark,
plus a few like IteratorLoops that can be used on maps.
Sorry that there's no documentation for running them.
(I just noticed a few were stale in CVS so updated.)
While running some of them I noticed that your simplification
of our bit-spreading function leads to too many conflicts
on some data sets. You probably want to revert to...
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
I'll send some other notes on your implementation
HashMaps are also prominent in some SPEC tests, that don't
have public sources. One of the main tests (jbb) includes
some truly idiotic usages, like using a HashMap<Integer, X>
instead of a dense array. (The DenseMapMicrobenchmark
independently tests some similar usages). Because SPEC
scores are overly important to vendors, some of them
do weird things with HashMap (like attempt to use
alternative implementations that are rarely otherwise better)
under switches like -XX:+ +AggressiveOpts. Beware.
More information about the core-libs-dev