Paper benchmarks five concurrent linked list algorithms from coarse-grain to lock-free
Coarse-grain locking beats lock-free in read-heavy workloads, fine-grain locking performs worst.
A new paper by Zeeshan Mohammed Rangrej on arXiv evaluates five techniques for building concurrent linked lists, comparing them across diverse workloads. The five methods progress from simplest to most advanced: coarse-grain locking (one global lock), fine-grain locking (per-node locks), lazy synchronization (logical removal before physical), lock-free design using CAS (compare-and-swap), and likely a fifth hybrid or optimistic approach. All five were implemented in C++ and tested under read-heavy, balanced, and write-heavy workloads with varying list sizes.
The results challenge conventional wisdom. Coarse-grain locking and lazy synchronization dominate read-heavy workloads when key ranges are small, despite their theoretical overhead. Lock-free lists become competitive only when key ranges are large and thread counts increase, showing diminishing returns for simpler scenarios. Fine-grain locking, despite its theoretical appeal of high concurrency, consistently performed worst due to costly per-node lock acquisitions and management. The paper provides concrete performance measurements to guide developers in choosing the right concurrency strategy based on their specific access patterns and system scale.
- Five concurrent linked list approaches implemented in C++: coarse-grain, fine-grain, lazy, lock-free, plus an additional variant.
- Coarse-grain and lazy lists outperform lock-free under read-heavy workloads with small key ranges.
- Fine-grain locking performs worst across all workloads due to high overhead from per-node lock management.
Why It Matters
Helps developers choose optimal concurrent data structures based on workload type and scale, avoiding performance pitfalls.