Lock-Free Data Structures, in depth: when they beat locks, three correct builds, and how to test them

What lock-free actually promises

The terms describe progress guarantees, not speed. A blocking algorithm can stall every thread if one thread stops while holding something, such as a mutex. An obstruction-free algorithm guarantees that a thread running alone eventually finishes. A lock-free algorithm guarantees that, in any interval where threads keep taking steps, some thread completes an operation: the system as a whole always makes progress, even if an individual thread can retry forever. A wait-free algorithm guarantees that every thread completes in a bounded number of its own steps.

The practical consequence is about what happens when a thread is paused at the worst moment. Under a mutex, if the holder is preempted or page-faults, everyone waiting stalls behind it. The result is convoys and latency spikes that look random. In a lock-free structure, a paused thread holds nothing the others need; they finish their operations around it. That is also why lock-free structures can be used from signal handlers and real-time audio callbacks, where blocking is forbidden.

What is not promised is higher throughput: threads hammering one atomic word still serialise on its cache line, just without blocking each other.

When a mutex is the better answer

An uncontended mutex on Linux is one atomic read-modify-write in user space, with the kernel involved (via futex) only when there is a waiter: about the cost of the compare-and-swap at the heart of most lock-free operations. Under heavy contention the bottleneck is the shared cache line, and both designs suffer. Lock-free clearly wins in fewer cases than its reputation suggests:

Try the boring fixes first: shrink the critical section, shard the data, batch work per lock acquisition, or give each thread its own structure and merge later.

The primitives: atomics, CAS and memory ordering

Every lock-free algorithm is built from atomic loads, atomic stores and atomic read-modify-write operations. The workhorse is compare-and-swap: compare_exchange(expected, desired) writes desired only if the current value equals expected, and otherwise loads the current value into expected. On x86 this compiles to LOCK CMPXCHG; on Arm it may be a load-linked/store-conditional pair. The _weak variant may fail spuriously, which is fine inside a retry loop.

Atomicity alone is not enough, because compilers and CPUs reorder ordinary memory operations. Memory orderings say which reorderings are forbidden. A release store guarantees that every write before it in program order is visible to any thread that performs an acquire load which reads that store's value. That pairing is how you publish data: plain-write the payload, release-store an index; the reader acquire-loads the index, then reads the payload. Relaxed operations are atomic but order nothing else, which is right for counters and for re-reading your own index. Sequentially consistent, the default, adds one global order over such operations and is the safe choice while learning.

The rule that prevents most bugs: for every piece of data handed between threads, name the release store that publishes it and the acquire load that receives it. If you cannot name both, the code is wrong. The memory model article covers happens-before in more depth.

Build 1: a single-producer, single-consumer ring buffer

The SPSC ring buffer needs no CAS, which makes it the best first build. The producer is the only writer of tail and the consumer is the only writer of head. Release/acquire on the indices publishes the slot contents.

#include <atomic>
#include <cstddef>
#include <optional>

template <typename T, std::size_t N>   // N must be a power of two
class SpscRing {
    static_assert((N & (N - 1)) == 0, "capacity must be a power of two");
    alignas(64) std::atomic<std::size_t> head_{0};  // written only by consumer
    alignas(64) std::size_t cached_tail_{0};         // consumer's private copy
    alignas(64) std::atomic<std::size_t> tail_{0};  // written only by producer
    alignas(64) std::size_t cached_head_{0};         // producer's private copy
    T slots_[N];

public:
    bool try_push(const T& v) {                      // producer thread only
        std::size_t t = tail_.load(std::memory_order_relaxed);   // our own index
        if (t - cached_head_ == N) {                 // looks full: refresh
            cached_head_ = head_.load(std::memory_order_acquire);
            if (t - cached_head_ == N) return false;
        }
        slots_[t & (N - 1)] = v;                     // plain write to the slot
        tail_.store(t + 1, std::memory_order_release);  // publish the slot
        return true;
    }

    std::optional<T> try_pop() {                     // consumer thread only
        std::size_t h = head_.load(std::memory_order_relaxed);
        if (h == cached_tail_) {                     // looks empty: refresh
            cached_tail_ = tail_.load(std::memory_order_acquire);
            if (h == cached_tail_) return std::nullopt;
        }
        T v = slots_[h & (N - 1)];
        head_.store(h + 1, std::memory_order_release);  // hand slot back
        return v;
    }
};

The producer reads its own tail relaxed because no other thread writes it. The release store of tail publishes the slot write that precedes it. The consumer's acquire load of tail makes that slot write visible before it reads the slot. The consumer's release store of head tells the producer the slot's old contents have been read, so the producer's acquire load of head makes overwriting safe. Unsigned subtraction handles index overflow.

Two performance details matter as much as correctness. The alignas(64) keeps the two indices on separate cache lines; without it, every push invalidates the consumer's line and vice versa, the effect described in the false sharing article. The cached copies mean each side touches the other's line only when the buffer looks full or empty, not on every operation. The pattern underlies the LMAX Disruptor and most audio ring buffers.

Build 2: a Treiber stack, and the ABA problem

With more than one writer you need CAS. The Treiber stack is the classic: push links a new node to the current top and swings top to it with CAS; pop reads the top, reads its next, and swings top to next.

struct Node { int value; Node* next; };
std::atomic<Node*> top{nullptr};

void push(int v) {
    Node* n = new Node{v, top.load(std::memory_order_relaxed)};
    while (!top.compare_exchange_weak(n->next, n,
            std::memory_order_release, std::memory_order_relaxed)) {
        // n->next now holds the current top; retry
    }
}

bool pop(int& out) {   // BROKEN as written: ABA and use-after-free
    Node* old = top.load(std::memory_order_acquire);
    while (old && !top.compare_exchange_weak(old, old->next,
            std::memory_order_acquire, std::memory_order_acquire)) {}
    if (!old) return false;
    out = old->value;
    delete old;        // another thread may still be reading old->next
    return true;
}

The push is fine; the pop has two bugs. Use-after-free: thread A loads old and is preempted before reading old->next; thread B pops and deletes the same node; A then dereferences freed memory. ABA: thread A reads top = node X with next = Y and is preempted. Thread B pops X, pops Y, and pushes X back (or a new node that the allocator placed at X's address). Top is X again, so A's CAS succeeds and installs Y, a node that is no longer in the stack. The CAS compared addresses, and the address came back meaning something else.

There are four standard fixes. Tagged pointers pair the pointer with a counter incremented on every change and CAS both together, using a double-width CAS or spare pointer bits; this fixes ABA but not use-after-free. Hazard pointers let each thread publish the pointer it is about to dereference, and reclaimers skip published nodes; see the hazard pointers article. Epoch-based reclamation defers frees until every thread has passed a quiescent point, cheaper per operation, but one stalled thread holds back all reclamation. In garbage-collected languages such as Java the collector solves both problems, because a node cannot be reused while any thread still references it.

Build 3: a bounded multi-producer, multi-consumer queue

Dmitry Vyukov's bounded MPMC queue avoids ABA by never freeing anything: a fixed array of cells, each with a sequence number saying whose turn it is. A cell at index i starts with sequence i. A producer that claims position pos may write the cell when its sequence equals pos, then stores pos + 1 to mark it full. A consumer at position pos may read when the sequence equals pos + 1, then stores pos + N to mark it empty for the next lap.

template <typename T, std::size_t N>
class MpmcQueue {
    struct Cell { std::atomic<std::size_t> seq; T data; };
    alignas(64) Cell cells_[N];
    alignas(64) std::atomic<std::size_t> enq_{0};
    alignas(64) std::atomic<std::size_t> deq_{0};
public:
    MpmcQueue() { for (std::size_t i = 0; i < N; ++i) cells_[i].seq.store(i, std::memory_order_relaxed); }

    bool try_enqueue(const T& v) {
        std::size_t pos = enq_.load(std::memory_order_relaxed);
        for (;;) {
            Cell& cell = cells_[pos & (N - 1)];
            std::size_t seq = cell.seq.load(std::memory_order_acquire);
            auto dif = static_cast<std::ptrdiff_t>(seq) - static_cast<std::ptrdiff_t>(pos);
            if (dif == 0) {                       // cell free for this lap: claim it
                if (enq_.compare_exchange_weak(pos, pos + 1, std::memory_order_relaxed)) {
                    cell.data = v;
                    cell.seq.store(pos + 1, std::memory_order_release);  // publish
                    return true;
                }                                 // CAS failed: pos was reloaded
            } else if (dif < 0) {
                return false;                     // a full lap behind: queue full
            } else {
                pos = enq_.load(std::memory_order_relaxed);  // another producer won
            }
        }
    }

    // try_dequeue mirrors try_enqueue: proceed when seq == pos + 1, CAS deq_ forward,
    // read the data, then store seq = pos + N to free the cell for the next lap.
};

Work through one round with N = 4. Producers P1 and P2 both load enq_ = 0. Cell 0 has sequence 0, so both see dif == 0 and race on the CAS; P1 wins and moves enq_ to 1, P2's CAS fails and reloads pos = 1, where cell 1 also has sequence 1, so P2 claims it. P1 writes data and stores sequence 1 into cell 0. A consumer at deq_ = 0 now sees sequence 1 = pos + 1 and can take it. Had P1 been preempted between its CAS and its sequence store, the consumer would see sequence 0 and report empty although P2's item is ready.

That last case is the honest caveat: this queue is not strictly lock-free; the Michael-Scott queue in the lock-free architecture article is. The window is tiny, but if your reason for going lock-free is robustness against preemption, know that this structure only partly delivers it.

Testing: assume it is wrong until a tool says otherwise

Unit tests rarely catch lock-free bugs: bad interleavings are rare and x86 hides ordering mistakes that appear on Arm. Use tools that explore schedules or detect races:

• ThreadSanitizer (-fsanitize=thread in Clang and GCC) detects data races; run stress tests under it in CI.
• Model checkers explore interleavings systematically. In Rust, loom runs a test under every interleaving and many weak-memory outcomes for small thread counts. For C and C++, GenMC serves the same purpose; Java has jcstress for concurrency stress tests against the Java memory model.
• Linearizability checking: record a history of operations with invocation and response times, then check that some sequential order explains them. This catches lost and duplicated items.
• Run on weakly ordered hardware. Arm servers and Apple silicon reorder more than x86; x86-only test runs pass code with missing orderings.

In stress tests, assert every item is popped exactly once and per-producer FIFO order holds.

Failure modes

What to do next

1. Write down why you need lock-free: real-time context, tail latency under preemption, or measured lock contention. If you cannot, use a mutex and shard it.
2. Benchmark the batched-mutex and per-thread alternatives first at production thread counts, including an oversubscribed run, recording p99 and p99.9 latency, not just throughput.
3. Prefer a reviewed library implementation over writing your own.
4. If you do write one, start from SPSC, annotate every atomic with the release/acquire pair it belongs to, and pad hot indices.
5. For multi-writer pointer structures, choose a reclamation scheme before writing the first CAS.
6. Gate merges on ThreadSanitizer stress runs, a model checker where available, and Arm CI.