UPDATED: Scalable and Low Latency Lock-free Data Structures in C++
summary
Claims a Hash Trie hybrid lock-free cache-conscious C++ implementation that targets millions of lookups/inserts with low tail latency and compares microbenchmarks against hash tables and trees. Uses atomic bitmap buckets on 4KB pages, fixed-size collision packets, per-bucket boxing and split-on-full rehashing, and generation-based reclamation waits for readers instead of immediate frees. Designed for kernel/near‑real‑time use (Tempesta FW), shows better throughput on read‑heavy mixes and addresses worst‑percentile stalls from OS scheduling and TLB/cache effects.
AI-written summary · about
chapters (14)
- 0:00Project context and goals
- 2:33Latency and scheduling
- 5:16Lock-free data structures
- 8:55Memory management basics
- 12:38Trees vs hash tables
- 15:53Cache locality optimization
- 21:02Hash table limitations
- 24:01Radix and bison trie designs
- 28:42Hardware-aware design
- 34:06Hash trie implementation
- 39:01Handling resizing and growth
- 43:42Atomic state management
- 46:41Memory reclamation logic
- 50:26Scalability and conclusion
related talks
01h 04mConcurrency TS2: Improved C++ Concurrency and Lock-free Programming
33mRewrite, Optimize, Repeat
01h 00mLock-Free Programming (or, Juggling Razor Blades), Part I
01h 05mIntroduction to Wait-free Algorithms in C++ Programming
01h 01mHigh performance data structures in boost
30mRewrite, optimize, repeat: Our journey porting a triemap from C to Rust
09mTrees in C++
52mC++ Game Development - Techniques to Optimise Multithreaded Data Building