Lock-Free Data Structures: Why Compare-and-Swap Isn’t the Whole Story

Most engineers learn the same simplified narrative: mutexes are slow, lock-free data structures are fast, therefore avoid locks. The reality is more nuanced. Writing correct lock-free code is genuinely hard, and the memory reclamation problem — not the core algorithm — is where real implementations get subtle and dangerous.

Progress Guarantees Aren’t Binary

“Lock-free” is frequently used to mean “not using a mutex,” but the formal definition is more precise. A data structure is lock-free if at least one thread is always guaranteed to make progress, even if other threads are suspended indefinitely. This is distinct from wait-free, where every thread is guaranteed to complete its operation in a bounded number of steps regardless of contention.

Most practical lock-free structures are lock-free but not wait-free. Under heavy contention, individual threads can be repeatedly starved — they retry a failed operation while other threads succeed and move on. Wait-free algorithms exist, but tend to carry constant overhead that makes them slower in the common case.

Compare-and-Swap: The Universal Primitive

Modern CPUs expose compare-and-swap (CAS) as an atomic instruction — CMPXCHG on x86, load-linked/store-conditional (LL/SC) pairs on ARM. The semantics are simple: atomically compare a memory location to an expected value, and if they match, replace it with a new value. The operation reports whether the swap succeeded.

CAS is expressive enough to implement almost any lock-free algorithm. A lock-free stack is roughly: read the current head, point the new node at it, then CAS the head from the old value to the new node. If another thread modified the stack between your read and your CAS, the operation fails and you retry. That retry loop is the core of most lock-free algorithms.

The ABA Problem

Here’s the classic trap. Thread 1 reads head = A and prepares a CAS to replace it with B. Before it executes, thread 2 pops A, pushes several other nodes, and then pushes a new node that happens to be allocated at the same address as A (because the allocator reused it). When thread 1 finally runs its CAS, it sees head = A again and succeeds — but the structure is not in the state thread 1 assumed.

The address matched; the meaning did not. This is the ABA problem.

The standard fix is a version counter paired with the pointer. Instead of a bare pointer, you store a (pointer, version) pair and CAS both atomically. On 64-bit systems this is often done with a double-wide CAS (CMPXCHG16B on x86) or by packing the counter into unused high pointer bits. The counter increments on every modification, so address reuse no longer causes a false match.

The Real Challenge: Memory Reclamation

Version counters address ABA, but leave a harder problem unsolved: when is it safe to free a removed node?

With a mutex, no thread can access the data structure while you hold the lock, so freeing a removed node is straightforward. Lock-free structures offer no such guarantee. Thread 1 may be mid-dereference on a pointer to node X at the exact moment thread 2 decides to free it. If thread 2 wins and the allocator reuses that memory, thread 1 has a use-after-free.

Three main approaches handle this:

Hazard pointers (introduced by Maged Michael in 2004): Before dereferencing a pointer, a thread publishes it in a per-thread “hazard pointer” slot. Before freeing a node, the freeing thread scans all hazard pointer slots; if the node appears anywhere, the free is deferred. Overhead is deterministic and memory use is bounded, but every dereference and every free incurs a scan.

Epoch-based reclamation (EBR): Threads periodically announce entry into a new epoch. A node can only be freed once every thread has passed through an epoch newer than the one in which the node was removed. EBR has very low common-case overhead, but reclamation stalls if any thread stops advancing its epoch — a real hazard with preempted or blocked threads.

Read-Copy-Update (RCU): Popularized by the Linux kernel, RCU makes reads extremely cheap (often just a memory barrier) while writers atomically publish an updated copy. Old versions are freed after a “grace period” — once it is certain no reader holds a reference to the old data. Kernel RCU ties grace periods to CPU scheduling quiescent states; userspace implementations typically use epoch-based mechanisms underneath.

Each approach trades off latency, throughput, memory overhead, and implementation complexity differently.

When Lock-Free Structures Actually Help

The overhead of CAS retry loops, memory barriers, and reclamation bookkeeping means lock-free structures are not universally faster. Under low contention, a well-implemented mutex is often comparable because CAS still requires a cache-line exclusive access. Under high contention, retry loops waste significant CPU cycles.

Lock-free structures genuinely excel in specific scenarios: single-producer/single-consumer queues (where careful memory ordering can eliminate CAS entirely), read-dominated data where RCU shines, or real-time systems where the worst-case latency of mutex contention is unacceptable.

For most applications, the safe default is a well-tuned concurrent queue or map from the standard library — written by specialists who have already wrestled with all of the above. Rolling your own lock-free structure is a meaningful systems engineering project, not a routine optimization.