Against SIMD, Robin Hood, and Another Hybrid Table
The benchmarked hash tables are the SIMD tables absl::flat_hash_map (a.k.a. Abseil/Swiss) from Google and boost::unordered_flat_map from Boost; the Robin Hood tables ankerl::unordered_dense::map from Martinus, tsl::robin_map from Tessil, and CC map from me; and the hybrid open-addressing/chaining tables Bytell from Skarupke and Verstable from me.
The integer hash function for all tables is MurmurHash3’s 64-bit finalizer. The string hash function is FNV-1a.
The maximum load factor for all tables is set via their respective APIs to 0.95. However, some tables—namely Abseil, Boost, and Bytell—forcibly rehash before this limit, either because of extra internal constraints or because their actual maximum load factors are hard-coded and not customizable. Hence, these tables have an advantage in these benchmarks because their performance in the load factor range of about 0.875 to 0.95 is not shown. For example, the peaks in their plots, which represent their performance at their load factor limit, are lower than they would be if these tables could—like the other tables—continue all the way to 0.95.
The test environment is an AMD Ryzen 7 5800H with the frequency locked at 90%. The compiler is GCC 12.1 via MinGW-w64 with optimization set to O3.
The data sets consist of sequential integers randomly shuffled and randomly generated strings.
Each datapoint is the result of taking ten recordings, removing the highest and lowest recording, and averaging the remaining eight.
The graphs are interactive. Hover over a label to highlight the associated plot, and click the label to toggle the plot’s visibility. The graphs automatically scale to the visible plots.
Update 14/12/2023: Replaced Martinus' old robin_hood map with his newer unordered_dense map and marked the hash functions as avalanching for detection by Boost and unordered_dense.