Comprehensive C++ Hashmap Benchmarks (2022)

Summary

It’s been over 3 years since I’ve spent considerable time finding the best C++ hashmap. After several requests I finally gave in and redid the benchmark with state of C++ hashmaps as of August 2022. This took much more work than I initially anticipated, mostly due to the fact that benchmarks take a looong time, and writing everything up and creating a representation that is actually useful takes even more time. Thanks everyone who annoyingly kept asking me for updates TL;DR: Here are the benchmark results! Table of Contents This time I have evaluated 29 different hashmaps, and also added several variants with special allocators. Each of these was combined with 6 differend hashes, resulting in 174 different combinations to benchmark. Each of these combinations was evaluated in 11 different benchmarks, totaling in 1914 benchmark evaluations. This almost doubles the number of benchmarks from my evaluation in 2019. Benchmark Infrastructure Hardware All benchmarks ran on an Intel i7-8700, locked at 3200 MHz. The benchmarks ran on an isolated core dedicated to benchmarking I disabled frequency scaling and turbo boost. the PC was kept completely idle otherwise while running the benchmarks. Software I used Manjaro Linux with an up to date kernel. All benchmarks are done with clang++ 13, which at that time was the default compiler on Manjaro Linux. I used the compile flags -O3 -march=native. Each benchmark was run multiple times, and I’m using the median to get rid of any potential outliers. Benchmarks Stable References The hashmaps can be divided into two types: ones where the inserted elements always reside at the same location, thus pointers & references to the elements are stable, and ones where elements can be shuffled around. This is usually the case in open address hashing. Hashmaps with no reference stability tend to be faster because they can usually get rid of one memory indirection and can better optimize for cache locality and allocations. Modifying Numbers Bench...