Designing fast lock free algorithms by understanding cache coherence dynamics
summary
Shows that cache-coherence dynamics (the MESI-style directory flow and forward/invalidation messages) make contended CAS operations serialize and incur latency that grows roughly linearly with the number of writers, so CAS failures waste most of the work and can make lock-free code slower than locks. Replaces contended CAS on head/tail with a non-failing fetch-and-add plus a bounded cyclic ring, sequence numbers, and an elimination/closure mechanism (LCRQ). Result: a practical queue that approaches hardware RMW throughput and avoids the CAS-driven collapse.
AI-written summary · about
chapters (24)
- 0:00Introduction
- 5:58Welcome
- 6:17Outline
- 6:57Context
- 8:00Model
- 10:00Parallel Operations
- 12:10Approach
- 13:35Algorithm
- 14:35Queue
- 16:02Issues with Queue
- 16:29Lockfree synchronization
- 20:53Lock free algorithm
- 22:26Lock free recipe
- 23:26Inconsistent states
- 25:22Log free version
- 30:11Log free version performance
- 31:02Cache coherence
- 32:26MSI protocol
- 34:17Directorybased protocol
- 36:56Why is this behavior important
- 39:48Atomic read modify instructions
- 41:02Cache line contention
- 45:26Question
- 50:45Unrealistic algorithm
related talks
52mNonblocking algorithms/ CAS/Atomics
01h 38mLock-free Programming is Dead - Long Live Lock-free Programming!
48m“Is Parallel Programming still hard? PART 2 of 2”
28mAre mutexes slow?
01h 22mBeyond Sequential Consistency - Leveraging Atomics for Fun & Profit
22mBuilding a lock-free STM for OCaml
47mUsing Java 8 Lambdas and Stampedlock to manage thread safety
01h 00mIntro to Concurrent Programming 1/3: Classic Stack and Queue Algorithms