Faster HashMap implementation
alex14n at gmail.com
Fri Jul 24 17:04:54 PDT 2009
On Wed, Jul 22, 2009 at 8:21 PM, Doug Lea<dl at cs.oswego.edu> wrote:
> On further evaluating it (among other possible HashMap replacements),
> I'm not convinced that they are enough better to commit.
> Size: ... 9216 36864 147456 589824
> HashMap ... 45 97 208 273
> V2 ... 40 78 188 257
Gain +12% +24% +11% +6%
More than 10% average improvement on big maps,
not worse on tiny maps, less memory usage - not a bad result imho
> Similarly for the mixed-side-array approach of Alex's Compact/Fast HashMap.
My version is a chained map, not an open map,
So concerns about locality and hit rates does not apply.
And with defragmentation there is not so many cache misses on collisions.
More information about the core-libs-dev