Conference Presentation, Lecture, Other
The Cost of Concurrency Coordination with Jon Gjengset
- Mutexes maintain high performance with a single thread at approximately 250 million operations per second but drop to roughly 25 million operations per second with two threads, remaining flat and low thereafter, contradicting the assumption that adding threads maintains performance.
- Reader-writer locks initially match mutex performance but degrade by approximately 10x as threads increase, eventually performing worse than mutexes when reader counts rise due to cache line contention on shared reader count counters.
- Cache coherence protocols like MESI introduce significant overhead, where reading and releasing a read lock requires two cache line transfers costing about 30 nanoseconds each, totaling 60 nanoseconds which exceeds half the time of a main memory access.
- The left-right data structure offers linear scaling performance up to approximately 3 billion operations per second across 10 cores for read-heavy workloads by eliminating reader coordination, provided readers use private counters and writes remain rare.
- Left-right structures are unsuitable for write-heavy scenarios or applications requiring strict linearizability, as frequent writes cause writer contention, and the architecture enforces eventual consistency where readers may see stale data until a pointer swap.
- Real-world performance optimization requires balancing read-to-write ratios, avoiding false sharing through 64-byte alignment, and recognizing that lock acquisition overhead dominates only in short critical sections, whereas mutexes remain viable for longer operations.
- Hardware advancements such as 3D stacking and proprietary cache coherence variants aim to reduce access latency, but fundamental coordination costs remain high, meaning developers must select algorithms based on specific data transfer patterns rather than expecting universal lock improvements.
- Specific implementation details influence outcomes, including the necessity for deterministic operations to support logging, potential bottlenecks from reader list mutexes during joins, and the requirement for writers to wait for all readers to exit before modifying data.
- Performance variability includes scenarios where adding cores causes dips due to false sharing on unaligned counters, which can be resolved via alignment fixes, and systems where the number of threads is small enough that cache coherence issues are negligible.
- Future outlook suggests that while software mutex quality has converged, reader-writer lock iterations on OS mechanisms are needed, and optimization strategies may increasingly rely on hardware-level cache improvements rather than revolutionary lock algorithm changes.