Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step
summary
A new hash table called SwissTable implements a 2-level, N-way associative probing design with per-slot control bytes (seven-bit H2 tags) packed in 16-byte groups and scanned with SSE intrinsics, removing pointers and reducing indirections. The implementation gets about 2–3x faster than std::unordered_map for typical keys, cuts memory use enough to save roughly 1% of Google’s fleet RAM, and reduces fleet CPU sampling by ≈0.5% in rollout — it is production-deployed and works.
AI-written summary · about
chapters (14)
- 0:00Introduction and credits
- 6:45Starting with unordered map
- 12:36Simplifying the hash table
- 18:41Introducing node_hash_set
- 21:33Benchmarking results
- 23:47Eliminating sentinels
- 27:00Metadata and hash groups
- 31:37SSE optimization
- 36:58Ergonomics and pitfalls
- 42:10Fleetwide performance gains
- 45:31Swiss table naming
- 46:15Advanced probing experiments
- 47:41Seven-sized group experiment
- 49:49Q&A session
related talks
51m“Cache Optimized Hash Tables”
01h 00mCache Friendly C++
09mBig Data, Big Performance
56m“High Performance Code 201: Hybrid Data Structures"
01h 01mWhat do you mean by "Cache Friendly"?
01h 02mCache-friendly Design in Robot Path Planning with C++
58mC++ Performance and Optimisation
12mThe Storage Hierarchy is Not a Hierarchy: Optimizing Caching on Modern Storage Devices...