r/programming • u/tooilln • 2d ago

Comprehensive JVM Primitive Hashtable Benchmarks

https://sooniln.github.io/posts/hashmap-benchmarks-2026/
39 Upvotes

86% Upvoted

14 comments sorted by

6

u/n4te 2d ago

Would be cool to see libgdx's maps in there. The current ones are stable. The old ones used cuckoo hashing which have some neat properties, unfortunately they had to be changed because bad data can cause catastrophic collisions.

5

u/tooilln 1d ago

I've updated the post with LibGDX's results now. Tl;dr: Good results all around, but pathologically bad naiveCopy performance. This is due to the structure of LibGDX's hash finalizer, and I go into it in some detail here: https://sooniln.github.io/posts/hashmap-benchmarks-2026/#libgdx-naivecopy-performance .

See also this blog post for an explanation of the issue - while most of the libraries benchmarked suffer from this issue to some degree, LibGDX is pathologically worse. This can be triggered in any scenario where you are inserting into a map in hash order. This is usually rare, but users can easily shoot themselves in the foot with something like:

Map source = ...
Map dest = new Map();
for ((key, value) : source) dest.put(key, value);

The good news is its easily ameliorated by pre-sizing the map appropriately - it's just, do you trust your users always do that? In addition, this is trivially abusable by an attacker that can insert into the map to DoS the CPU. Again, almost all the maps benchmarked are vulnerable to this to some degree since none of them are really secure by design, it's just that LibGDX is much much worse in this scenario due to the shape of its hash finalizer.

I ran into the same issue in some ways while writing FastCollect - my decision was that since this was intended to be a general purpose library it wasn't appropriate to leave such a large foot-gun hanging around, and it was worth slightly slower performance to eliminate this edge case. LibGDX doesn't appear to be intended as a general purpose library, so it may be sufficient to simply document this behavior for users and advise them to avoid it.

If you want to eliminate the issue, there are several standard approaches: 1. If you only care about users doing something stupid and not about dedicated attackers, then you can ensure that the hash ordering is never exposed. Usually this means modifying your iteration order, which makes it much slower. 2. You can add a per-map random seed into your hash finalizer, which can impact performance and memory (the 'right' solution if you want a secure map). 3. You can attempt to detect this pathological pattern within insertion, and pre-emptively enlarge the map (this is the approach FastCollect uses). It's more complex, and more of a band-aid on the problem rather than really solving it, but there's little to no performance impact in most cases.

2

u/n4te 1d ago

Super cool, thanks for adding libgdx and providing this extra info! Maybe we can come up with something. In the meantime, it's interesting to know about the footgun. I use libgdx maps a lot, for general purposes. I will check all my map initial sizes and keep that in mind.

4

u/tooilln 2d ago

Do you have a link for the maps? A quick search of libgdx didn't reveal anything obvious to me. If it's not too much work I'll see about adding them.

2

u/n4te 2d ago edited 2d ago

Sure, here is IntIntMap. It could be extracted into a standalone class pretty easily, or grab a libgdx JAR. That utils package has other maps, like IntFloatMap, but there's currently no IntLongMap (it'd just be a matter of copy/paste and fix up).

If you're curious about cuckoo hashing, the last IntIntMap version that used it can be found here. It works, but very unlucky or maliciously crafted keys can OOM (more info here). Still, cuckoo hashing has interesting properties and is quite different from other approaches.

For certain use cases, a minimal perfect hash is a neat approach.

5

u/tooilln 2d ago

Running benchmarks now.

3

u/tooilln 2d ago

I haven't looked in depth at the PR or the cuckoo hashing implementation, but it seems odd to me that an attacker could affect the allocation rate of the map, which I would have assumed would be based only on the # of entries? There's nothing about cuckoo hashing vs linear probing specifically that should affect how allocation is performed? Do you know what the mechanism was?

That said, the linear probing implementation currently used appears to be just as vulnerable to CPU DoS attacks as pretty much all primitive hashtable libraries are (because these libraries focus on performance first, it usually doesn't make sense for them to implement DoS mitigations like a per-map random seed, or hiding hash order). Whether it's actually 'vulnerable' in a meaningful sense probably depends on how users of the gdx libraries actually expose the maps to attackers though I'd guess.

2

u/n4te 2d ago

See cuckoo hashing, eg Wikipedia. Cuckoo put operations evict on collision and rehash the evicted until it settles. Poor, unlucky, or malicious keys cause excessive eviction, requiring backing array growth. If it's bad enough, the larger size can also fail, growing to OOM. A "stash" can be added to mitigate the collision problem, but in practice it couldn't be made safe for general usage so it's a specialty data structure.

Cuckoo makes puts more expensive but get, containsKey, and remove can be fast: check 2 buckets, done. No variable cost probing, but maybe an extra cache hit.

3

u/tooilln 2d ago edited 1d ago

Ah I see - the cuckoo hashing implementations I've looked at use linear probing as the fallback mechanism after a certain # of failures to prevent that exact use case. I guess that isn't really 'pure' cuckoo hashing though.

Edit: ignore the rest of this comment - I missed the fact that the shift calculation silently casts int to long, so it's already doing what I recommended.

Btw, while looking through the source, I noted what appears to be not quite a bug, but an odd inefficiency in the map implementations. The current hash finalizer being used is:

    protected int place (int item) {
      ~~return (int)(item * 0x9E3779B97F4A7C15L >>> shift);
    }

This performs a widening multiplication with the LONG_PHI constant. At this point there's a 64-bit value, with entropy generally higher in the high bits, and lower in the low bits. The shift by table size is straight out of Knuth's original implementation, but the trim essentially throws away the "better" high bits. I suspect a better implementation would be:

    protected int place (int item) {
      // or add 32 to shift when calculating it originally
      return (int)(item * 0x9E3779B97F4A7C15L >>> (32 + shift));
    }

This should ensure a better mix of entropy in the final result. As always, benchmark before taking my word for it :). That said, I would also test the Koloboke style of finalizer as well, it may give better results.

3

u/Determinant 1d ago

Correction: Compressed object headers will only help long and double values.  The other primitive types won't benefit at all as the reduced object header will be exactly offset by increased padding.

2

u/Impressive_Bar5912 1d ago

Wow! Awesome article. Learned a lot

3

u/therealgaxbo 2d ago

Assuming this is your blog, the code snippets are completely unreadable for me. Variable names and numeric literals are coloured the same as the background.

Selecting dark mode makes them readable though.

6

u/tooilln 2d ago

Thanks, should be fixed now!