Note that this benchmark does not include boost::unordered_flat_map. This is an open addressing variant of boost::unordered_map which has only been released in December 2022.
I wanted to mention this because boost::unordered_flat_map and boost::unordered_flat_set are among the fastest open addressing hash containers in C++ land. Internally, they use lots of cool SIMD tricks. If anyone is interested in the details, here's a nice blog post by the developer: https://bannalia.blogspot.com/2022/11/inside-boostunorderedf...
Benchmarks are fine but they will only be loosely correlated with the measured performance for any specific use case.
There is still substantial performance to be gained by creating bespoke hashmap designs at every point of use in code. The high dimensionality of the algorithm optimization space makes it improbable that any specific hashmap algorithm implementation will optimally capture the characteristics of a use case or set of use cases. The variance can be relatively high.
It isn't uncommon to find several independent hashmap designs inside performance-engineered code bases. The sensitivity to small details makes it difficult to build excellent hashmap abstractions with broad scope.
It's also the case that performance of a hashmap, or anything, in a small-scale benchmark may not reflect the performance in a large system that does things other than manage maps. There are side effects like how many icache lines are visited during a map operation. These don't hurt microbenchmarks but they can matter in real systems. It may not be completely pointless to microbenchmark a data structure but it can be ultimately misleading.
Also it is very easy to find situations where hash table lookups dominate a measurement, but where the answer isn't to make the lookup faster but to make fewer lookups.
Definitely. As an extreme but fun example... in one project I had a massive hash map (~700 GB or so) that was concurrently read to/written from by 256 threads. The entries themselves were only 16 bytes and so I could use atomic cmpxchg, but the problem I hit was that even with 1GB huge pages, I was running out of dTLB entries. So I assigned each thread to a subregion of the hash table, then used channels between each pair of threads to handle the reads and writes (and restructured the program a bit to allow this). Since the dTLB budget is per core, this allowed me to get essentially 0 dTLB misses, and ultimately sped up the program by ~2x
This is not universally applicable, especially if an algo isn't deterministic. For example if you were to time "bogosort of 100 items" you'd see increasingly better times the more runs you performed.
20 comments
I wanted to mention this because boost::unordered_flat_map and boost::unordered_flat_set are among the fastest open addressing hash containers in C++ land. Internally, they use lots of cool SIMD tricks. If anyone is interested in the details, here's a nice blog post by the developer: https://bannalia.blogspot.com/2022/11/inside-boostunorderedf...
There is still substantial performance to be gained by creating bespoke hashmap designs at every point of use in code. The high dimensionality of the algorithm optimization space makes it improbable that any specific hashmap algorithm implementation will optimally capture the characteristics of a use case or set of use cases. The variance can be relatively high.
It isn't uncommon to find several independent hashmap designs inside performance-engineered code bases. The sensitivity to small details makes it difficult to build excellent hashmap abstractions with broad scope.
https://timharris.uk/papers/2013-opodis.pdf
I've covered it in my presentation: https://presentations.clickhouse.com/2017-hash_tables/
This is not how you should do benchmarks. Don't take the median, you don't even need to do any "warming up".
Simply run it long enough and only take the best result of each. This is more reliable and correct.
https://doc.qt.io/qt-6/qhash.html
https://www.youtube.com/watch?v=nSFIFlLpsTQ
> We encourage phmap users to switch to gtl if possible. gtl provides the same functionality as this repository, but requires C++20 or above.
And the benchmarks do include gtl.