“How to make your data structures wait-free for reads"
summary
Presents the Left-Right algorithm: writers take a mutex and update the inactive copy while readers use an atomic version index and per-thread padded counters (hashing thread ID into an array) to do wait-free population-oblivious reads without a GC. Implementation keeps two copies (two-instance double-buffering), is linearizable, provides its own safe memory reclamation, and benchmarks on x86 (18 cores) and PowerPC show near-linear read scaling and 10x lower tail latency (example: reader/writer 99th ~51µs vs Left-Right ~2–7µs). Code and slides on the CppCon 2015 GitHub.
AI-written summary · about
chapters (18)
- 0:00Introduction to progress
- 0:55Understanding progress types
- 3:34Blocking and scalability
- 6:29Starvation-free locks
- 10:09Lock-free algorithms
- 12:30Wait-free properties
- 15:23Analyzing method progress
- 17:40Latency distributions
- 25:02Reader-writer locks
- 27:02Copy-on-write technique
- 29:06The left-right pattern
- 35:25Read indicator design
- 38:51Left-right state machine
- 41:51Consistency models
- 47:20Performance benchmarks
- 55:05Optimized left-right
- 57:11Technique interchangability
- 59:34Questions and answers
related talks
42mReader-Writer Lock versus Mutex - Understanding a Lost Bet
21mEvery Data Structure Deserves Lock-Free Memory Reclamation
01h 08mRead, Copy, Update, then what? RCU for non-kernel programmers
01h 11mLock-Free Programming (or, Juggling Razor Blades), Part II
28mAre mutexes slow?
48m“Is Parallel Programming still hard? PART 2 of 2”
01h 32mLock-free programming with modern C++
55m“A lock-free concurrency toolkit for deferred reclamation and optimistic speculation"