Lock-Free Programming: Atomics and Memory Ordering

Lock-free programming lets threads share data without holding a mutex. Done correctly it can eliminate lock contention and reduce tail latency. Done incorrectly it produces data races, subtle reorderings, and bugs that only appear on certain CPUs or at high load. The foundation is the C++ memory model and std::atomic.

Why memory ordering matters

Modern CPUs and compilers reorder instructions for performance. On a single thread this is invisible — the result is as-if the code ran in order. Across threads, reorderings become visible: one thread may observe another thread's writes in a different order than they were issued.

// Thread 1:
data = 42;           // (A)
ready.store(true);   // (B)

// Thread 2:
while (!ready.load()) {}  // waits for B
use(data);                // expects to see A's write — but may not!

Without memory ordering constraints, the CPU or compiler may reorder (A) after (B) from Thread 2's perspective. Thread 2 spins until ready is true, then reads data — but data may still be 0 because the write hasn't propagated yet.

This is not a race condition in the data-race sense (data is not accessed concurrently); it is a visibility ordering problem. Memory ordering constraints solve it.

The two mental models: seq_cst and acquire/release

There are two ways to think about atomics in C++.

Sequentially consistent (seq_cst) — the safe default

memory_order_seq_cst (the default when you don't specify an ordering) gives the strongest guarantee: there exists a single total order of all seq_cst operations across all threads. Every thread agrees on what happened and in what order.

#include <atomic>
#include <thread>

std::atomic<bool> ready{false};
int data = 0;

void producer() {
    data = 42;
    ready.store(true);                       // seq_cst store
}

void consumer() {
    while (!ready.load()) {}                 // seq_cst load
    assert(data == 42);                      // guaranteed
}

With seq_cst, the store(true) and load() form a synchronization point. All writes before the store are visible to the thread that observes the load returning true. This is the correct solution to the problem above.

Performance cost: on x86, seq_cst stores require a mfence or xchg instruction. On ARM and POWER, the cost is higher — a full memory barrier before and after the store. On a multi-socket system under high contention, this cross-core communication is measurable.

Rule: start with seq_cst. Profile before switching to weaker orderings. Most code is not bottlenecked on atomic ordering.

Acquire/release — the fast path

For most lock-free patterns, you only need a happens-before relationship between a producer and consumer. Acquire/release provides exactly that — without the global total order overhead.

• memory_order_release on a store: everything written before this store is visible to any thread that acquires the same atomic.
• memory_order_acquire on a load: all memory reads/writes after this load see everything that was written before the corresponding release store.

std::atomic<bool> ready{false};
int data = 0;

void producer() {
    data = 42;
    ready.store(true, std::memory_order_release);  // "releases" data
}

void consumer() {
    while (!ready.load(std::memory_order_acquire)) {}  // "acquires" data
    assert(data == 42);   // guaranteed by release/acquire pair
}

The release store synchronizes-with the acquire load. This creates a happens-before edge: everything before the release is visible to everything after the acquire.

Mnemonic: Release = "I'm done writing, here's my data." Acquire = "I'm starting to read, give me the data."

Key rule for choosing acquire/release:

• Loads: choose between acquire and relaxed
• Stores: choose between release and relaxed
• Loads are never release; stores are never acquire

Relaxed — no ordering, just atomicity

memory_order_relaxed guarantees that the operation is atomic (no torn reads/writes) but makes no ordering guarantees relative to other memory operations. Use it only when you don't care what order other threads observe the write relative to other writes.

// Counter where only the final value matters, not ordering:
std::atomic<int> counter{0};

void increment() {
    counter.fetch_add(1, std::memory_order_relaxed);
}

// Safe: the increment is atomic (no tearing).
// Not safe for: coordinating access to other memory.

Good uses for relaxed: statistics counters, reference counts (just the count, not the destructor trigger — that needs acq_rel).

The six memory orderings

Compare-and-swap (CAS) loops

CAS is the fundamental primitive for lock-free algorithms. compare_exchange_weak / compare_exchange_strong atomically:

1. Read the current value
2. Compare it to expected
3. If equal, write desired; return true
4. If not equal, load the current value into expected; return false

// Lock-free push onto a stack (Treiber stack):
template<typename T>
struct LockFreeStack {
    struct Node {
        T value;
        Node* next;
    };

    std::atomic<Node*> head{nullptr};

    void push(T val) {
        Node* node = new Node{std::move(val), nullptr};
        node->next = head.load(std::memory_order_relaxed);
        // CAS loop: retry if another thread changed head between our load and swap
        while (!head.compare_exchange_weak(
                   node->next, node,
                   std::memory_order_release,    // success: release the new node
                   std::memory_order_relaxed))   // failure: just re-read head
        {}
    }

    std::optional<T> pop() {
        Node* old_head = head.load(std::memory_order_acquire);
        while (old_head &&
               !head.compare_exchange_weak(
                   old_head, old_head->next,
                   std::memory_order_acquire,
                   std::memory_order_acquire))
        {}
        if (!old_head) return std::nullopt;
        T val = std::move(old_head->value);
        delete old_head;   // see: ABA problem below
        return val;
    }
};

compare_exchange_weak vs compare_exchange_strong:

• weak may spuriously fail (returns false even if *this == expected) but is faster on some architectures (LL/SC instruction pairs)
• strong never spuriously fails — but on LL/SC machines it loops internally
• In a CAS loop (which retries anyway), always use weak

The ABA problem

The ABA problem is a subtle correctness bug in CAS-based code. If a thread reads head = A, gets suspended, another thread pops A, pushes B, pops B, pushes A (same pointer), and the first thread resumes — the CAS head == A → expected succeeds, but the list structure has changed.

Thread 1: reads head = Node{1} → A
Thread 2: pops Node{1}, deletes A, pushes Node{2}, pushes NEW Node{1} at address A (reuse)
Thread 1: CAS succeeds (head == A), but A's next is now Node{2}, not what T1 expected

Mitigations:

1. Tagged pointer (version counter) — pack a counter into the low bits of the pointer:

struct TaggedPtr {
    uintptr_t ptr : 48;    // pointer (48-bit on x64)
    uintptr_t tag : 16;    // monotonically incrementing counter
};
std::atomic<TaggedPtr> head;

Each modification increments the tag. Even if the pointer value wraps back to A, the tag differs.

2. Hazard pointers — threads announce which nodes they are accessing. Deallocation is deferred until no thread holds a hazard pointer to the node.

3. Epoch-based reclamation — nodes are freed only after all threads have passed through a "grace period," ensuring no thread holds a stale pointer.

4. Just use a mutex — if ABA is a real concern and throughput isn't critical, a mutex eliminates the problem entirely.

std::atomic_flag — the simplest atomic

atomic_flag is the only type that is guaranteed to be lock-free on all platforms. It is a boolean flag with only two operations: test_and_set (sets to true, returns old value) and clear.

std::atomic_flag spinlock = ATOMIC_FLAG_INIT;

void lock()   { while (spinlock.test_and_set(std::memory_order_acquire)) {} }
void unlock() { spinlock.clear(std::memory_order_release); }

This is a simple spinlock. Spinlocks are appropriate when:

• The critical section is very short (< ~50 ns)
• You know the holder will release soon
• You cannot block (kernel/interrupt context, real-time)

For longer critical sections, prefer std::mutex — a spinning thread wastes a CPU core.

std::atomic<T> for non-trivial types

std::atomic<T> works for any T that is trivially copyable. For small types (T fitting in a machine word), operations are lock-free. For larger types, the implementation may use a hidden mutex.

struct Vec2 { float x, y; };   // 8 bytes — likely lock-free on 64-bit
std::atomic<Vec2> position;

// Check at runtime:
static_assert(std::atomic<Vec2>::is_always_lock_free, "need hardware support");
// or:
if (!position.is_lock_free()) { /* fall back */ }

On x86-64: int, long, pointers, and 8-byte structs are lock-free. 16-byte structs may use cmpxchg16b (lock-free but slower). Larger types use a mutex.

Wait/notify (C++20)

C++20 adds wait() and notify_one()/notify_all() to std::atomic, enabling efficient blocking without a mutex:

std::atomic<bool> done{false};

// Producer thread:
do_work();
done.store(true, std::memory_order_release);
done.notify_one();   // wake one waiter

// Consumer thread:
done.wait(false, std::memory_order_acquire);  // blocks until done != false
process_result();

wait is more efficient than spinning: the implementation uses futex (Linux) or WaitOnAddress (Windows) to block the thread at the OS level. Unlike std::condition_variable, no mutex or unique_lock is required.

Decision guide

Do you need multiple threads to share data without a mutex?
│
├─ Is the shared data a single integer/pointer?
│   └─ Yes → std::atomic<T>
│       ├─ Do you need ordering relative to other memory? → acquire/release
│       ├─ Just atomicity, no ordering? → relaxed
│       └─ Multiple atomics must be consistent? → seq_cst
│
├─ Do you need a lock-free queue/stack?
│   └─ Start with std::mutex — measure first
│       ├─ Profiler shows lock contention? → Treiber stack / Michael-Scott queue
│       └─ Need ABA protection? → tagged pointer or hazard pointers
│
└─ Critical section < 50 ns and will never block?
    └─ atomic_flag spinlock

The honest take: std::mutex with std::condition_variable is correct, debuggable, and scales well to most workloads. Reach for lock-free only when you have profiler evidence that mutex contention is a bottleneck.

SPSC queue: the simplest correct lock-free queue

A single-producer, single-consumer (SPSC) ring buffer is the only lock-free queue you can implement correctly with just memory_order_release and memory_order_acquire. With exactly one writer and one reader there is no contention on the head or tail indices, so no CAS loop is needed — only a release store on the write side and an acquire load on the read side. This makes SPSC queues both easy to reason about and extremely fast: on modern hardware the hot path is a handful of instructions with no bus-locking prefix.

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

template<typename T, std::size_t N>
class SPSCQueue {
    static_assert((N & (N - 1)) == 0, "N must be a power of two");
public:
    // Called by producer thread ONLY
    bool push(T value) {
        const std::size_t head = head_.load(std::memory_order_relaxed);
        const std::size_t next = (head + 1) & (N - 1);
        if (next == tail_.load(std::memory_order_acquire))
            return false;   // queue full

        buffer_[head] = std::move(value);
        head_.store(next, std::memory_order_release);   // publish
        return true;
    }

    // Called by consumer thread ONLY
    std::optional<T> pop() {
        const std::size_t tail = tail_.load(std::memory_order_relaxed);
        if (tail == head_.load(std::memory_order_acquire))
            return std::nullopt;   // queue empty

        T value = std::move(buffer_[tail]);
        tail_.store((tail + 1) & (N - 1), std::memory_order_release);
        return value;
    }

private:
    std::array<T, N> buffer_;
    alignas(64) std::atomic<std::size_t> head_{0};   // written by producer
    alignas(64) std::atomic<std::size_t> tail_{0};   // written by consumer
};

The alignas(64) on each index prevents false sharing: if head_ and tail_ lived in the same 64-byte cache line, every producer write would invalidate the consumer's cached copy of tail_, and vice versa — turning what should be independent updates into a cross-core cache coherence storm. See the next section for more on false sharing.

False sharing and cache padding

False sharing occurs when two independent variables that are written by different threads happen to reside in the same CPU cache line, causing each write to silently invalidate the other thread's cached copy. The result is the same coherence traffic as a real shared variable — without any logical sharing at all. The bug is invisible in single-threaded tests and only manifests as mysteriously poor scaling when two threads run simultaneously on separate cores.

A cache line is typically 64 bytes. C++17 exposes this as a compile-time constant:

#include <new>   // std::hardware_destructive_interference_size

// sizeof(Counter) is probably 4, but padding it to 64 bytes puts it
// alone on its own cache line.
struct alignas(std::hardware_destructive_interference_size) Counter {
    std::atomic<int> value{0};
};

// Per-thread counters: each lives on its own cache line.
// Threads can increment concurrently with zero coherence traffic.
std::array<Counter, 8> per_thread_counters;

Conversely, std::hardware_constructive_interference_size (also 64 on most platforms) tells you the size to target when you want two variables on the same cache line because they are always accessed together:

// Load factor struct: accessed as a pair — keep them on the same line.
struct alignas(std::hardware_constructive_interference_size) LoadFactor {
    std::atomic<uint32_t> numerator{0};
    std::atomic<uint32_t> denominator{1};
};

Diagnosis: if removing alignas(64) from your SPSC queue degrades throughput by 2–5× under load, false sharing is the cause. Tools: perf stat -e cache-misses,LLC-load-misses, Intel VTune's "Memory Access" analysis, or simply measuring throughput with and without padding.

Hazard pointers: safe memory reclamation

The hardest part of lock-free data structures is not the algorithm — it is reclaiming memory safely. In the Treiber stack pop() above, delete old_head is called immediately after the CAS succeeds. But another thread may still be dereferencing old_head->next after our CAS but before our delete: we have a use-after-free. Hazard pointers solve this by requiring each thread to "announce" which pointers it is currently accessing before dereferencing them; the deleting thread checks all announcements before freeing.

// Simplified hazard pointer sketch — production use std::hazard_pointer (C++26)
namespace hp {

constexpr int kMaxThreads = 64;
std::atomic<void*> hazards[kMaxThreads]{};

thread_local int tid = /* assigned per-thread */0;

// Before dereferencing p, publish it:
template<typename T>
T* protect(std::atomic<T*>& src) {
    T* p;
    do {
        p = src.load(std::memory_order_relaxed);
        hazards[tid].store(p, std::memory_order_release);
        // Re-read: if src changed while we stored, retry
    } while (src.load(std::memory_order_acquire) != p);
    return p;
}

void clear_hazard() {
    hazards[tid].store(nullptr, std::memory_order_release);
}

// Retire p: defer free until no hazard pointer references it
template<typename T>
void retire(T* p) {
    // Scan all hazard slots; if p appears, defer; otherwise delete now.
    for (int i = 0; i < kMaxThreads; ++i) {
        if (hazards[i].load(std::memory_order_acquire) == p)
            return;  // still in use; add to deferred list (elided here)
    }
    delete p;
}

} // namespace hp

C++26 formalises this as std::hazard_pointer / std::hazard_pointer_obj_base<T>. Until then, production code uses folly::hazptr (Facebook's open-source implementation) or epoch-based reclamation (EBR), which amortises the scan cost across a "grace period" during which all threads must have passed a checkpoint.

RCU: read-copy-update

RCU (read-copy-update) is a synchronisation primitive that makes reads virtually free by deferring writes until all ongoing readers have completed. Originating in the Linux kernel (circa 2001), it is optimal for read-heavy workloads where reads vastly outnumber updates. A reader simply loads the pointer and dereferences it — no atomic increment, no fence needed on most architectures. The writer atomically publishes a new version of the data and then waits for a "grace period" (all pre-existing readers finish) before freeing the old version.

// Conceptual RCU usage pattern (using C++26 std::rcu or folly::rcu):
#include <rcu.h>   // hypothetical header

struct Config {
    int timeout;
    std::string endpoint;
};

std::atomic<Config*> global_config{new Config{30, "api.example.com"}};

// Reader — runs in a hot path, no blocking:
void handle_request() {
    rcu_read_lock();
    const Config* cfg = global_config.load(std::memory_order_consume);
    // use cfg safely — guaranteed not freed while read lock is held
    connect(cfg->endpoint, cfg->timeout);
    rcu_read_unlock();
}

// Writer — infrequent config reload:
void reload_config(Config* new_cfg) {
    Config* old = global_config.exchange(new_cfg, std::memory_order_release);
    synchronize_rcu();   // wait for all current readers to finish
    delete old;          // now safe to free
}

synchronize_rcu() may block for milliseconds — that is acceptable because config reloads are rare. The read path pays no synchronisation cost at all. In userspace, liburcu (Userspace RCU, used in LTTng and Babeltrace) provides a production-quality implementation. C++26's std::rcu_obj_base<T> and std::rcu_retire bring this pattern into the standard library.

Testing lock-free code

Lock-free code is notoriously difficult to test with conventional unit tests because the bugs are timing-dependent reorderings that standard test frameworks cannot expose. A test suite that runs correctly on x86 (which has a strong memory model that masks many races) may hide bugs that surface on ARM, POWER, or under TSan. The correct approach combines multiple tools: a model checker for exhaustive state-space exploration, ThreadSanitizer for dynamic race detection, and stress tests on weakly-ordered hardware.

ThreadSanitizer (TSan):

# Compile with TSan instrumentation:
clang++ -fsanitize=thread -g -O1 my_lockfree.cpp -o test_tsan
./test_tsan

# TSan intercepts all atomic operations and memory accesses at runtime.
# It reports data races, lock-order violations, and some atomics misuse.
# Caveat: TSan cannot explore all thread interleavings — only those that
# actually occur during the run. Run under high parallelism and load.

CDSChecker (Berkeley) is a model checker for C++ concurrent programs. It systematically explores all possible thread interleavings permitted by the C++ memory model, finding bugs that stress tests may never hit:

# CDSChecker compiles your code against its own atomic model and
# replays executions exhaustively:
./cdschecker -- ./my_lockfree_test
# Reports: "Bug found: assertion failure in execution #47 of 2048"

Relacy (by Dmitriy Vyukov, Google) takes a similar model-checking approach and integrates directly into C++ unit tests via a macro layer that intercepts atomic operations. It is particularly effective for verifying SPSC and MPSC queue correctness.

Practical checklist:

1. Run TSan under high thread counts (std::thread::hardware_concurrency() * 4)
2. Run CDSChecker or Relacy on isolated algorithm tests
3. Test on real ARM hardware or under QEMU with -cpu cortex-a57 (weaker memory model than x86)
4. Use assert() liberally inside the data structure to catch invariant violations

When to reach for lock-free

Lock-free is not automatically faster than a mutex — on low-contention workloads, std::mutex often wins because it avoids spinning and is optimised by the OS. The decision to use lock-free should always be driven by profiler data, not intuition. On Linux, pthread_mutex_lock on an uncontended mutex takes roughly 20–30 ns on x86 — comparable to a single cache miss. Lock-free structures spend that budget on CAS retries and memory fences instead.

Benchmark both before committing to lock-free complexity:

#include <benchmark/benchmark.h>
#include <mutex>
#include <atomic>
#include <queue>

// Baseline: mutex-protected queue
std::mutex mu;
std::queue<int> q_mutex;

static void BM_MutexPush(benchmark::State& state) {
    for (auto _ : state) {
        std::lock_guard lk(mu);
        q_mutex.push(42);
    }
}

// Lock-free SPSC queue from earlier
SPSCQueue<int, 4096> q_spsc;

static void BM_SPSCPush(benchmark::State& state) {
    for (auto _ : state) {
        while (!q_spsc.push(42)) {}   // retry if full
    }
}

BENCHMARK(BM_MutexPush)->Threads(1)->Threads(4)->Threads(8);
BENCHMARK(BM_SPSCPush)->Threads(1);   // SPSC: single producer only!

Guidance for choosing: