Mar 25, 2026, 10:41 AM ETConference Presentation, Lecture, Other

The Cost of Concurrency Coordination with Jon Gjengset

Observed vs. Actual Performance: While mutexes often appear slow in high-concurrency benchmarks, the slowness is not intrinsic to the lock mechanism itself but stems from CPU cache coherence overheads.
The Counter-Intuitive Graph: Benchmarks show mutex performance dropping significantly (from ~250M ops/sec to ~25M ops/sec) when moving from 1 to 2 threads, then plateauing at a low level, contrary to the expectation of constant single-thread throughput.
Reader-Writer Lock Degradation: Reader-writer locks perform slightly better than mutexes initially but degrade more rapidly as thread count increases, eventually becoming slower than standard mutexes due to "cache line ping-ponging."

Cache Hierarchy: CPUs utilize a three-level cache hierarchy (L1, L2, L3) where L1 is private and fast (1ns latency), while L3 is shared and larger, closer to RAM latency (~100ns).
Cache Lines: Memory is divided into 64-byte chunks called "cache lines," which are the unit of transfer and coherence management, not individual addresses.
MESI States: Coherence protocols (MESI and variants like MSI, MESIF) manage data states:
- Modified: The core holds the only dirty copy; must write back to RAM before others read.
- Exclusive: The core holds the only clean copy; can upgrade to Modified instantly.
- Shared: Multiple cores hold identical clean copies; a write requires invalidating all other copies.
- Invalid: The core holds no valid copy of the line.
Cost of Coherence: Transitions between states (e.g., Shared to Modified) require cross-core communication, costing approximately 30ns per transaction, which is 30x slower than L1 access but only 1/3 the cost of RAM.

Lock Acquisition Overhead: For short critical sections, the time spent on cache coherence traffic (acquiring/releasing the lock) can exceed the time spent executing the actual code inside the lock.
Reader-Writer Lock Bottleneck: Implementations of reader-writer locks often require writing to a shared "reader count" variable to acquire a read lock, forcing a "fetch-add" operation that triggers exclusive access for every single reader.
Sequentialization of Reads: This forced serialization of the reader count updates means reader-writer locks behave sequentially under high read contention, negating their theoretical parallel advantage.
Mutex Resilience: Mutexes handle this better in read-only scenarios because the lock holder maintains exclusive ownership, preventing the constant invalidation cycle that plagues reader-writer locks.

Concept: Uses two copies of data (Left/Right) and a single atomic pointer indicating which copy readers should access.
Write Strategy: Writers modify the inactive copy and, upon completion, atomically flip the pointer. Writers must then wait for all readers to acknowledge the new pointer (via per-thread counters) before reusing the old copy.
Read Performance: Reads are lock-free and wait-free; readers access a single copy without coordinating with other readers or the writer, eliminating cache line bouncing for reads.
Performance Gain: Benchmarks show linear scaling up to ~3 billion operations per second, avoiding the contention penalty seen in reader-writer locks.
Constraints:
- Write-Heavy Penalties: Performance degrades significantly if write frequency matches or exceeds read frequency due to writer overhead.
- Eventual Consistency: Readers may observe stale data; the system is not linearizable.
- Determinism Requirement: The data structure must support an operational log that can be applied deterministically to both copies to maintain consistency.
- Single Writer: Only one writer can operate at a time; multiple writers require additional synchronization layers.

The Anomaly: Left-Right performance dipped ~10x at four cores despite the lock-free design, contradicting expectations of linear scaling.
Root Cause: Multiple per-thread counters were allocated within the same 64-byte cache line, causing the MESI protocol to trigger invalidations for distinct writes to the same cache line (false sharing).
The Fix: Applying 64-byte alignment to the counter type ensured each thread's counter resided on a distinct cache line, restoring linear performance.
Key Insight: Lock-free does not imply contention-free; memory bandwidth and cache coherence rules apply equally to atomic operations and standard variables.

Selection Criteria:
- Ratio of Reads to Writes: High read ratios favor Left-Right; balanced or write-heavy ratios favor standard mutexes.
- Critical Section Length: Short sections magnify lock overhead; long sections amortize the cost, making mutexes viable.
- Consistency Requirements: Applications requiring linearizability or read-after-write consistency cannot use Left-Right.
General Advice:
- Avoid Blind Optimization: Do not select algorithms solely based on benchmarks of "fastest" libraries without analyzing the specific data transfer patterns of the application.
- Measure First: Hardware behaviors (cache misses, false sharing) often cannot be predicted by high-level code review; profiling is essential.
- Hardware Reality: Modern CPU optimizations (e.g., 3D stacking, proprietary MESI variants) exist but are opaque; developers should reason in terms of cache coherence costs rather than abstract lock primitives.

Hardware Innovations: No revolutionary new instructions have eliminated lock latency; 3D stacking (AMD 3D V-Cache) helps by increasing L3 capacity and reducing access distances.
Reader Join/Leave: In Left-Right, dynamic reader management can become a bottleneck if implemented via a mutex; optimizing the reader list to a lock-free linked list is a viable solution.
Compiler Optimizations: Compilers use acquire/release barriers to prevent out-of-order execution across lock boundaries; they do not typically optimize away lock acquisition logic if side effects are present.
Mutex Implementation: User-space mutex implementations (e.g., Linux futexes) have largely standardized; optimization now focuses on minimizing mutex footprint to avoid false sharing, rather than reducing raw acquisition latency.