Introduction to Wait-free Algorithms in C++ Programming
summary
Claims a concrete wait-free design for a “sticky” atomic counter in C++ that uses atomics (compare-exchange, fetch_add/fetch_sub, exchange), compare-exchange loop avoidance by helping, and the trick to steal two bits from the counter to mark “zero” and a help flag. Implements an atomic shared_ptr using that counter and runs microbenchmarks on a 28‑core machine: read‑heavy workloads show lower tail latency for the wait‑free variant, but mixed/write‑heavy workloads sometimes favor the simpler lock‑free version.
AI-written summary · about
chapters (16)
- 0:00Introduction
- 1:27What we will cover in this talk
- 3:14Sticky counter problem
- 8:06Lock-based solution limits
- 10:12Danger of guessing performance
- 11:58Progress guarantees defined
- 17:14Wait-free algorithms intro
- 21:50Lock-free compare-exchange loops
- 24:37Wait-free design principles
- 27:26Helping in wait-free algorithms
- 32:20Bits for counter state signaling
- 34:07Wait-free counter without read
- 43:48Adding read to wait-free counter
- 52:41Benchmarking wait-free counter
- 56:15Summary of progress guarantees
- 57:22Q&A
related talks
01h 02mA Lock-Free Atomic Shared Pointer in Modern Cpp
01h 00mLock-Free Programming (or, Juggling Razor Blades), Part I
55mThe Memory Model in C++
01h 02mThe foundation of C++20 atomics
01h 04m[old version]The C++20 Synchrononization Library
01h 04mConcurrency TS2: Improved C++ Concurrency and Lock-free Programming
59mThreads and Locks must Go
52mBest Practices for Concurrency