“Cache Optimized Hash Tables”
summary
Describes a cache‑focused hash implementation (Rabbit) that combines linear probing with a small overflow end‑of‑run bucket, stores separate keys and values and a compact bitmap states array to cut memory and cache misses. Presents microbenchmarks vs Google sparse_hash and std::unordered_map showing roughly 20–50% faster lookups on medium/high‑entropy data and much lower memory growth, and reports integration into treestore MySQL and use with Facebook linkbench for mostly lock‑free allocation and concurrent versioning.
AI-written summary · about
chapters (18)
- 0:00Introduction to talk
- 0:25Why optimize CPU cache
- 3:03CPU cache fundamentals
- 9:20Memory access patterns
- 11:34Cache hierarchy overview
- 12:17Hash table algorithms
- 13:30Linear probing basics
- 16:18Separate keys and values
- 17:47Linear probing clustering
- 21:32Hash function randomness
- 23:40Load factor and clustering
- 27:02Bucket optimization
- 28:32Bitmap for state storage
- 29:40Birthday paradox in hash tables
- 30:23Benchmark results overview
- 34:33Profiling workload example
- 37:09Cache misses in practice
- 37:32Q&A session starts
related talks
01h 00mDesigning a Fast, Efficient, Cache-friendly Hash Table, Step by Step
51mThe Holy Grail! A Hash Array Mapped Trie for C++
36mThe Holy Grail - A Hash Array Mapped Trie for C++
54mAbseil's Open Source Hashtables: 2 Years In
01h 00mCache Friendly C++
30m“Esoteric Data Structures and Where to Find Them”
50mMastering the unordered_map in C++
01h 01mWhat do you mean by "Cache Friendly"?