Five Ways to Build a Concurrent Linked List: From Coarse-Grain Locking to Lock-Free Algorithms

Zeeshan Mohammed Rangrej · 2026

Read Five Ways to Build a Concurrent Linked List: From Coarse-Grain Locking to Lock-Free Algorithms by Zeeshan Mohammed Rangrej (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-28972.txt.

Introduction

Rangrej compares five ways to build a linked list that many computer threads can use safely at the same time. Linked lists are basic data structures, but simultaneous access creates races and corruption risks. His versions range from one big lock guarding the whole list, through finer-grained and lazy locking schemes, to a lock-free design using no locks at all.

All five were implemented in C++ and benchmarked across read-heavy, balanced and write-heavy workloads at several list sizes. The right choice depended heavily on usage. The coarse-grain and lazy lists won under workloads heavy on reads, with small key ranges. The lock-free list became competitive when key ranges were large and threads were many. Fine-grain locking, despite its theoretical appeal, paid a heavy cost in per-node lock overhead. It performed worst throughout, a caution against assuming more locks mean better scaling.

Catalog record

CREATORZeeshan Mohammed Rangrej
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE29 KB
LICENSEhttp://creativecommons.org/publicdomain/zero/1.0/
RIGHTSCC0
SOURCEarXiv

Source: https://arxiv.org/abs/2606.28972

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Five Ways to Build a Concurrent Linked List: From Coarse-Grain Locking to Lock-Free Algorithms Zeeshan Mohammed Rangrej Abstract Linked lists are one of the most basic data structures in computer science. But when many threads try to use the same linked list at the same time, things get complicated. In this paper, we look at five different ways to make a linked list work correctly and efficiently with multiple threads running at once. We start with the simplest approach—one big lock for the whole list— and step by step improve it, ending with a lock-free design that uses no locks at all. We implemented all five versions in C++ and measured how fast each one is across different workloads (read-heavy, balanced, and write-heavy) and different list sizes. Our results show that the right choice of algorithm depends heavily on how the list is used: the coarse-grain and lazy lists win under read-heavy workloads with small key ranges, while the lock-free list becomes competitive when key ranges are large and more threads are running. Fine-grain locking, despite its theoretical appeal, pays a heavy cost from per-node lock overhead and consistently performs the worst in our tests. Keywords— concurrent linked list, mutual exclusion, fine-grain locking, lazy deletion, lock-free algorithm, compare-and-swap, linearizability, benchmarking I. Introduction Every programmer learns about linked lists early on. A linked list stores a chain of nodes, where each node holds a value and a pointer to the next node. Operations like adding a value, removing a value, and searching for a value are all O(n) in the worst case, but linked lists are still very useful because they can grow and shrink easily. The challenge we study in this paper is: what happens when multiple threads try to use the same linked list at the same time? Imagine two threads both trying to insert a value at the same position in the list. If they both read the same predecessor node and both write their new nodes in, one insertion will be lost. This kind of problem is called a race condition , and it can cause data corruption, crashes, or silent wrong answers that are very hard to debug. The standard fix is to use locks (also called mutexes). A lock makes sure that only one thread can change the list at a time. But how you place those locks matters a lot for performance: • One lock for everything : correct but slow—only one thread can work at a time. • One lock per node : allows more parallelism but adds a lot of overhead. • Optimistic locking : skip locks while searching, lock only to commit. • Lazy deletion : mark nodes as deleted first, then clean up later. • Lock-free : no locks at all—use hardware atomic operations instead. Each step in this list is more complex to implement and reason about, but potentially faster under high concurrency. We implemented all five approaches and benchmarked them to see whether the added complexity actually pays off. A. Our Contributions 1. We implement all five concurrent linked-list algorithms from scratch in modern C++ (C++17), keeping each implementation clean and self-contained so it is easy to read and learn from. 2. We build a thorough benchmark harness that tests each algorithm under three realistic workload mixes (read-heavy, balanced, write-heavy) and two key ranges (small = high contention, large = low contention) with varying thread counts (1, 4, 8 threads). 3. We analyze the results and explain why certain algorithms win in certain conditions, connecting the performance numbers back to the design choices in the code. The rest of this paper is organized as follows. Section 2 gives the background knowledge needed to understand the algorithms. Sections 3 – 7 each describe one algorithm. Section 9 describes our benchmark setup. Section 10 presents and discusses the results. Section 12 concludes. II. Background A. What We Are Building: A Concurrent Set All five implementations represent the same abstract data type: a set of integers . The set supports three operations: • add(v) : insert value v ; return true if v was not already present. • remove(v) : delete value v ; return true if v was found. • contains(v) : return true if v is currently in the set. Internally, the set is stored as a sorted singly-linked list. Two sentinel nodes are always present: a head node with value -\infty ( INT_MIN ) and a tail node with value +\infty ( INT_MAX ). This trick means we never have to check for null pointers during traversal. head( -\infty ) \to a \to b \to … \to tail( +\infty ) B. Linearizability When multiple threads run at the same time, we need a way to say whether the data structure is correct . The standard way is called linearizability [ 1 ] . The idea is simple: even though operations from different threads overlap in real time, each operation should appear to take effect at a single instant (called its linearization point ). As long as we can find such a point for every operation, the concurrent execution is as good as some valid sequential execution. C. Mutual Exclusion with Locks A mutex (mutual exclusion lock) lets a thread say “I am working on something, nobody else should touch it”. The thread acquires the lock, does its work, then releases the lock. Only one thread can hold a mutex at a time; others block until it is released. Mellor-Crummey and Scott [ 7 ] gave a thorough treatment of scalable spin-lock designs for shared-memory systems, including the MCS queue lock that eliminates cache-line bouncing. Their work explains why simple test-and-set locks perform poorly under high thread counts, a lesson that directly motivates the move toward finer-grain and eventually lock-free designs. In C++17 we use std::mutex and std::lock_guard . A lock_guard automatically releases the lock when the scope ends, which prevents forgetting to unlock. D. Compare-And-Swap (CAS) Modern CPUs provide a special instruction called compare-and-swap (CAS) . It does this atomically (in one uninterruptible step): If the memory location currently holds expected , replace it with desired ; otherwise do nothing. Return whether the swap happened. In C++ this is std::atomic::compare_exchange_strong . CAS is the key building block for lock-free algorithms: instead of blocking other threads, a thread retries its operation whenever a CAS fails (meaning someone else changed the value first). Boehm and Adve [ 11 ] formally defined the C++ concurrency memory model that governs how atomic operations like CAS interact with the memory subsystem and other threads, making programs with std::atomic well-defined across all conforming implementations. E. Linearization Points for Each Algorithm Table 1 summarizes the linearization point of each add , remove , and contains for all five algorithms. Table 1 : Linearization Points Algorithm add remove contains Coarse pred->next = node (inside lock) pred->next = curr->next read inside lock Fine pred->next = node (inside 2 locks) pred->next = curr->next read inside 2 locks Optimistic pred->next = node (validated) pred->next = curr->next read inside 2 locks Lazy pred->next = node (validated) curr->marked = true read of !marked Lock-Free CAS on pred->next succeeds CAS marking curr->next succeeds read of !is_deleted() III. Coarse-Grain List A. Design The

Read the complete text