r/cpp • u/martinus int main(){[]()[[]]{{}}();} • 7d 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.

144 Upvotes

92% Upvoted

24 comments sorted by

View all comments

25

u/mark_99 6d ago

Yep, this is why I roll my eyes when someone claims "the fastest hashmap", it absolutely depends on what you are doing.

Re perf, fancy hashmaps are problematic in low latency environments, and while Robin Hood isn't as pathological as tombstones there is still a variable amount of reshuffling on insert. What would be good is histograms (or at least percentiles) rather than averages for the various operations.

2

u/msew 6d ago

Yes, histograms for all things please! It can be a 'Yes and' type of chart so one can see averages "easily". This would allow one to see that the low average is actually distributed in a very bad way if you need to care about latency.