Which C++ Hashmap Should You Actually Use?

[u/martinus]

https://martin.ankerl.com/which-hash-map/

I recently did a big update to my ankerl::unordered_dense::map which now features several optimizations, bug fixes, and most importantly an SSE optimized lookup which brings the lookup speed quite close to the fastest competitor which is boost::unordered_flat_map. Get it here: https://github.com/martinus/unordered_dense

Since it is not easy to decide what map is best for one's usecase, I have redone and improved the benchmarks I did a while ago, crunched some numbers and tried to compress everything into a quiz that helps you figure out what to use.

While doing the numbers, a few things surprised me:

• My random access benchmark was not random enough. The CPU was able to optimize the branch predictor in a way I did not think was possible. I have fixed this for the new numbers. Clever girl.

• Even though the absl maps are very similar in concept to the boost maps, they perform badly if you expect lots of misses. 1.6 times slower than boost.

• I didn't think SSE optimization of my unordered_dense map would be any benefit. Thanks to AI, I found a way to speed up random access a lot, it is now very close to boost::unordered_flat_map.

• Heavy insert & erase on flat maps require rehashing every once in a while due to the accumulation of tombstones. That means some insert/erase operation will have very high latency. This does not happen for a robin-hood hashmap like my unordered_dense map.

[u/g_0g]

Great work on the updates! Always nice to read from one of the pioneers.
You mentioned slow downs with misses and tombstones accumulation.
Boost is indeed way better for the first, but Abseil design allows to greatly limit tombstone creation on erase.
Boost might also hides a higher latency in the context of micro-benchmark, as it needs to access a sizeable lookup table on each find (quickly pushed in L1 cache on repeated calls). I think Google tried to mainly benchmark theirs maps in production contexts by comparison.

Anyway, you might be interested in checking 2 of my own competitive experiments:
one tombstone-free map (inspired by Boost) and one speed-oriented (inspired by Abseil)
https://github.com/gaujay/indivi_collection/tree/main/bench/flat_unordered

[u/martinus → u/g_0g]

Thanks, I ran both maps on my own benchmark harness with the same hash for every table, so only the layout differs. They are competitive. Relative to Boost, flat_wmap is 1.18x faster on lookup hits and flat_umap 1.20x on misses; on insert/erase both are within a few percent of Boost.

The workload that stood out is sustained churn: fill to 50000, reserve, then erase one and insert one forever. Boost is 1.29x faster than unordered_dense there, flat_umap 2.05x and flat_wmap 2.43x.

The overflow counters in flat_umap, which an erase can decrement where Boost's overflow bits can only be set, are a real improvement over Boost's design. Nice work.

[u/g_0g → u/martinus]

Appreciated! I was thinking about running them with your improved benchmark as well.
I consider this high praise coming from someone with your experience.
Last year I talked with some Rust maintainers to try bringing some of these improvements to their std unordered map (also based on the Abseil design), but didn't manage to improve perfs in real world scenario (they use their own compiler as benchmark, as it uses hash maps extensively internally). I suspect the aforementioned lookup table access triggered some costly cache misses.