Cuckoo hashing improves SIMD hash tables (and other hash table tradeoffs)

Summary

Cuckoo hashing improves SIMD hash tables (and other hash table tradeoffs) There are many options when designing a hash table. Cuckoo hashing is a curious design that is popular in academia, but unused in some of industry’s most popular designs, such as Google’s Swiss Tables and Meta’s F14 tables. Cuckoo hashing is often avoided because it has worse memory system performance and is beaten by SIMD-accelerated probing. This doesn’t have to be the case! With careful engineering, you can combine SIMD-accelerated probing with cuckoo hashing to beat the standard implementations in many scenarios. Benchmark highlights Adding cuckoo hashing to a strong baseline is typically close to neutral for performance on low load factors, and greatly improves performance on high load factors. We show performance across the range of load factors used by Swiss Tables. For different use cases the best baseline design may also differ; in each case we take the best baseline design and then add cuckoo hashing. Successful lookups on u64 keys and values, “Direct SIMD” baseline: 50%62.5%75%87.5%05101520253035BaselineBranchy cuckooBranchless cuckooLoad factorLookup time (ns)In cache (512 KiB)Out of cache (512 MiB) Failed lookups on u64 keys and values, “Indirect SIMD” baseline: 50%62.5%75%87.5%051015202530BaselineBranchy cuckooBranchless cuckooLoad factorLookup time (ns)In cache (512 KiB)Out of cache (512 MiB) Insertions on u64 keys and values, “Indirect SIMD” baseline: 50%62.5%75%87.5%01020304050BaselineCuckooLoad factorInsertion time (ns)In cache (512 KiB)Out of cache (512 MiB) Benchmarks are available. No library release is available yet, but perhaps in future. What is cuckoo hashing? All hash tables we consider use open addressing, where keys are stored in a flat array. The designs differ in the probe sequence: which elements, and in what order, we search during a lookup. Baseline SIMD hash tables such as Swiss Tables use SIMD quadratic probing. This starts searching from a position determine...