Abseil's Open Source Hashtables: 2 Years In
summary
Abseil’s flat hash tables use 16-wide SSE probes with an h1/h2 split to avoid EQ calls, yielding about 5–10% faster finds but 10–20% slower hot inserts in microbenchmarks; a floating-window layout adds four h1 bits and gives ~0.5% overall web-search win but breaks assumptions in some code. Small-table layout cuts metadata so int sets drop from ~92 to ~24 bytes and SSO strings save ~10x. Global sampling (pprof + atomic sample handles, geometric sampling) finds stuck-bit hashes and reduces flagged bad tables from ~15k to ~2k.
AI-written summary · about
chapters (13)
- 0:00Introduction and background
- 1:54Flat hash set terminology
- 3:18Swiss table core mechanics
- 8:30Rollout across Google
- 12:02Hyrum’s Law and hash tables
- 14:10Deterministic hash tables impact
- 17:40Floating group probing optimization
- 26:50Small table memory optimization
- 31:13CPU profiling and sampling
- 41:23Memory and system call concerns
- 43:55Fixing poor hash functions
- 47:08Global analysis and debugging
- 47:58Q&A session
related talks
51m“Cache Optimized Hash Tables”
30m“Esoteric Data Structures and Where to Find Them”
51mThe Holy Grail! A Hash Array Mapped Trie for C++
36mThe Holy Grail - A Hash Array Mapped Trie for C++
58mRefresher on Containers, Algorithms and Performance
57mCache friendly data + functional + ranges = ❤️
01h 04mBetter Code: Data Structures
57mAdventures in SIMD-Thinking (part 1 of 2)