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

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% 0 5 10 15 20 25 30 35 Baseline Branchy cuckoo Branchless cuckoo Load factor Lookup 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% 0 5 10 15 20 25 30 Baseline Branchy cuckoo Branchless cuckoo Load factor Lookup time (ns) In cache (512 KiB) Out of cache (512 MiB)

... continue reading