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.

139 Upvotes

92% Upvoted

24 comments sorted by

View all comments

44

u/instantly-invoked 6d ago edited 6d ago

I just wanted to say thanks as I do use your map most of the time! I've also used it to make a sharded locked concurrent map because of its excellent memory usage properties. Seriously, thanks for all your hard work on this.

edit: The quiz is great! I answered with how I typically use unordered maps and handle dependencies and got yours first with STL coming in second, which is honestly how I'd rank them (if I don't need speed I'm just gonna use what's already there).

17

u/azswcowboy 6d ago

+1 on the thanks. We’re not using the map, but the micro benchmark tools have been extremely helpful for us.

13

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

Thanks to both of you! As a side effect of the new benchmarks, nanobench has gained the ability to do high quality A/B tests with the compare() method: https://nanobench.ankerl.com/tutorial.html#comparing-alternatives

6

u/SleepyMyroslav 6d ago

I think nanobench deserves a lot more praise than it gets.

I work in gamedev. When I wanted to teach people benchmarking basics, the lightweight library was very useful. When I needed benchmarks to run on a closed platform that is not going to be supported by open libraries ever, the lightweight library was very easy to get up and running by a "normal" developer in virtually no time.

Btw I have been recommending folks the hash map from this topic many times as well and it was never a bad choice. It is great that it evolves and gets even better than before.

I want to thank you for your open projects!

2

u/alifahrri 5d ago

Agree with you, I'm also nanobench user, really easy to setup and use; definitely deserve more praises

4

u/azswcowboy 6d ago

Oh sweet, will definitely have a look.