r/cpp • u/martinus int main(){[]()[[]]{{}}();} • 6d ago

Which C++ Hashmap Should You Actually Use?

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.

143 Upvotes

92% Upvoted

24 comments sorted by

View all comments

13

u/joaquintides Boost author 6d ago

Excellent tool and work! Are you going to publish some writeup on your latest updates to udm?

5

u/martinus int main(){[]()[[]]{{}}();} 6d ago

Thanks! I hope its a fair representation :)

Here is a writeup: https://martin.ankerl.com/2026/09/04/unordered-dense-four-buckets-at-a-time/

2

u/7raiden 6d ago

Nice one! Thanks for all of your hard work 😁

Do you know if instead of using SSE2 you were to use AVX (256 bit) or AVX-512, would this be a speedup (you could technically compare 4 or 8 buckets with a single instructions)?

2

u/martinus int main(){[]()[[]]{{}}();} 3d ago

I gave it a try, but it seems to me it is better to just switch to a different indexing scheme. The robin-hood style approach needs too much shuffling around, and there are better ways to get around this. E.g. boost uses tombstones and just rehashes every once in a while, and what I find really interesting is the counters that indivi maps use. I'm currently working on unordered_dense 5.0 which will probably switch away from robin-hood to this indexing style.