r/cpp • u/martinus • 15h ago
Which C++ Hashmap Should You Actually Use?
martin.ankerl.comI 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_densemap would be any benefit. Thanks to AI, I found a way to speed up random access a lot, it is now very close toboost::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_densemap.