04 — Lock-Free Basics

Lock-free programming is where C++ stops being a portable language and becomes an interface to your CPU. You are now writing code where the memory model from file 01 is not academic — it is what determines whether your program works on Apple Silicon at all. This file teaches you exactly one useful lock-free structure (the SPSC ring buffer) properly, and then argues that you probably shouldn’t write more of them.

That sounds like a paradox. It isn’t. The value of learning lock-free is not “I will hand-roll queues in production.” It is “I now understand what the queues in my JIT / audio thread / trading engine are actually doing, and I can debug them.”

---

1. Terminology, precisely

• Lock-free: at least one thread makes progress in a bounded number of steps, regardless of scheduling. A blocked thread cannot stall the whole system.

• Wait-free: every thread makes progress in a bounded number of steps. Strictly stronger; rarely worth the cost.

• Obstruction-free: a thread running in isolation completes in bounded steps. Weakest useful guarantee.

A lock-free algorithm can still spin. What it cannot do is block waiting for another thread that has been preempted.

What most people get wrong: they think “lock-free” means “faster.” It means “no thread can stall another thread by being descheduled.” Real-time audio and hard-latency trading care about this. A web server does not. Fedor Pikus’s talk “Speed of Concurrency: is lock-free faster?” (CppCon 2016) shows short-critical-section mutex code often beats hand-rolled lock-free, because contention on a single atomic can be worse than a well-sized mutex.

2. When lock-free is worth it — the honest list

Domain	Lock-free is worth it?	Reason
Real-time audio callback	Yes	You cannot block a 128-sample deadline.
Trading gateway hot path	Yes	Tail latency budget is single-digit µs.
GC / JIT worklists	Sometimes	High contention on tiny units of work.
Web server request queue	No	mutex + condvar with batched wake is fine.
Thread pool submission	Usually no	Standard mutex + deque + cv handles it.
Any “I heard mutexes are slow” case	No	You have not measured. Measure first.

Rule: if you cannot describe the contention pattern (readers vs writers, burst rate, queue depth) in one sentence, you are not ready to pick lock-free.

3. compare_exchange_weak vs strong

Every non-trivial lock-free structure hinges on CAS (compare-and-swap). C++ gives you two:

• compare_exchange_strong(expected, desired) — returns true iff the value equaled expected; on false, expected is updated to the current value.

• compare_exchange_weak(expected, desired) — same semantics, but may spuriously fail even when the value equaled expected. Cheaper on LL/SC architectures (ARM, RISC-V), including Apple Silicon.

Rule of thumb:

• Use weak inside a loop (while (!x.compare_exchange_weak(exp, des)) {}). The loop absorbs spurious failures.

• Use strong when you do a single try and branch on it.

// Correct CAS loop shape:
T expected = a.load(std::memory_order_relaxed);
T desired;
do {
    desired = compute_new_from(expected);
} while (!a.compare_exchange_weak(expected, desired,
                                  std::memory_order_release,   // success
                                  std::memory_order_relaxed)); // failure

4. False sharing and cacheline padding

A cache line on modern x86 and Apple Silicon is 64 or 128 bytes. When two atomics live on the same line and two cores hit them, every store invalidates the other core’s cached copy — you pay the full coherence roundtrip on every update. This is false sharing.

C++17 gave you the portable knob:

#include <new>
constexpr std::size_t CACHELINE = std::hardware_destructive_interference_size;

struct alignas(CACHELINE) Slot {
    std::atomic<int> counter{0};
    char pad[CACHELINE - sizeof(std::atomic<int>)];
};

On Apple Silicon this constant is 128 (the M-series prefetches pairs of 64B lines, so effective sharing granularity is 128). On x86-64 it is 64. Trust the constant, not folklore. A single misaligned struct can cost you a 5-10x throughput drop — documented on Rigtorp’s blog.

5. The ABA problem — what it is, when it bites

CAS says: “if the value equals A, replace with B.” But if a value went A → X → A between your read and your CAS, the CAS succeeds and you never noticed. If the value is a pointer and X was a freed-and-recycled node, you just linked a stale node back into the list.

ABA hits pointer-based lock-free structures (Treiber stack, Michael-Scott queue), essentially never a fixed-array ring buffer.

Defenses:

• Tagged pointers — pack a 16-bit counter into the low bits (only works with over-aligned pointers) or use atomic<pair<T*, uintptr_t>> where a double-width CAS is available (x86 cmpxchg16b, ARMv8.1 casp).

• Hazard pointers — defer reclamation until no thread holds a reference. C++26 will ship std::hazard_pointer (WG21 P2530); until then, use Anthony Williams’s atomic_shared_ptr or the reference impl in Facebook’s folly.

• Epoch-based reclamation — batch frees at epoch boundaries. Simpler to implement, higher memory overhead.

For P3.1 you get to skip all of this because SPSC on a fixed ring has no reclamation — the array is preallocated.

6. THE PROJECT: SPSC ring buffer, Rigtorp design

One producer thread, one consumer thread, fixed-capacity queue. This is the workhorse of every low-latency system — audio callback → renderer, network RX → parser, sensor → fusion. Erik Rigtorp’s design (github.com/rigtorp/SPSCQueue, blog post “Correctly implementing a spinlock in C++” and “Optimizing a ring buffer for throughput”) is the reference. Here is a self-contained version you can put into P3.1:

// spsc_queue.hpp — header only
#pragma once
#include <atomic>
#include <cstddef>
#include <new>
#include <memory>
#include <cassert>

template <typename T>
class SpscQueue {
public:
    explicit SpscQueue(std::size_t capacity)
      : capacity_(capacity),
        buf_(static_cast<T*>(::operator new[](
              sizeof(T) * capacity, std::align_val_t{alignof(T)}))) {
        assert(capacity_ >= 2 && "capacity must be >= 2");
    }

    ~SpscQueue() {
        while (auto* p = front()) { p->~T(); pop(); }
        ::operator delete[](buf_, std::align_val_t{alignof(T)});
    }

    SpscQueue(const SpscQueue&)            = delete;
    SpscQueue& operator=(const SpscQueue&) = delete;

    // Producer side
    template <typename... Args>
    bool try_emplace(Args&&... args) {
        const auto head = head_.load(std::memory_order_relaxed);
        auto next = head + 1;
        if (next == capacity_) next = 0;

        // Fast path: use cached tail
        if (next == cached_tail_) {
            cached_tail_ = tail_.load(std::memory_order_acquire);
            if (next == cached_tail_) return false;   // full
        }
        new (buf_ + head) T(std::forward<Args>(args)...);
        head_.store(next, std::memory_order_release);
        return true;
    }

    // Consumer side
    T* front() {
        const auto tail = tail_.load(std::memory_order_relaxed);
        if (tail == cached_head_) {
            cached_head_ = head_.load(std::memory_order_acquire);
            if (tail == cached_head_) return nullptr; // empty
        }
        return buf_ + tail;
    }

    void pop() {
        const auto tail = tail_.load(std::memory_order_relaxed);
        assert(tail != head_.load(std::memory_order_acquire) && "pop on empty");
        buf_[tail].~T();
        auto next = tail + 1;
        if (next == capacity_) next = 0;
        tail_.store(next, std::memory_order_release);
    }

private:
    static constexpr std::size_t CL =
        std::hardware_destructive_interference_size;

    // Layout: cold field, then producer line, then consumer line.
    std::size_t capacity_;
    T*          buf_;

    alignas(CL) std::atomic<std::size_t> head_{0};   // producer writes
    alignas(CL) std::size_t              cached_tail_{0}; // producer-only cache

    alignas(CL) std::atomic<std::size_t> tail_{0};   // consumer writes
    alignas(CL) std::size_t              cached_head_{0}; // consumer-only cache
};

Why every line matters:

• head_ and tail_ on separate cache lines. Producer only writes head_, consumer only writes tail_. If they shared a line, every op invalidates the other core’s cache.

• cached_tail_ / cached_head_. The producer only needs to know the tail has moved past X. It caches the last observed tail and only reloads when the cache says “full.” This turns most enqueues from an atomic-load-with-acquire into a plain memory read — Rigtorp reports going from ~5.5M items/sec to ~112M items/sec on x86 with this one change.

• memory_order_release on producer store, memory_order_acquire on consumer load. Establishes happens-before so buf_[head]’s payload is visible to the consumer before it sees the updated head_. Weaker than seq_cst; on ARM this is stlr/ldar, one instruction.

• Placement new / explicit destructor. Slots hold non-trivially-constructible T; you cannot default-construct the whole array.

7. Benchmark harness (what P3.1 will actually run)

#include "spsc_queue.hpp"
#include <thread>
#include <chrono>
#include <cstdint>
#include <cstdio>

int main() {
    constexpr std::size_t N = 1'000'000;
    SpscQueue<std::uint64_t> q(1024);

    auto t0 = std::chrono::steady_clock::now();

    std::jthread prod([&]{
        for (std::uint64_t i = 0; i < N; ) {
            if (q.try_emplace(i)) ++i;
        }
    });

    std::uint64_t sum = 0;
    for (std::uint64_t i = 0; i < N; ) {
        if (auto* p = q.front()) { sum += *p; q.pop(); ++i; }
    }

    prod.join();
    auto t1 = std::chrono::steady_clock::now();
    auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(t1-t0).count();
    std::printf("%zu items in %lld ms (sum=%llu)\n", N, (long long)ms,
                (unsigned long long)sum);
}

Build with:

clang++ -std=c++20 -O3 -Wall -Wextra -fsanitize=thread bench.cpp -o bench_tsan
clang++ -std=c++20 -O3 -Wall -Wextra                   bench.cpp -o bench

TSan must be clean on the 1M-item run. Any warning is a bug.

8. What NOT to do next

After you finish P3.1 you may feel like tackling a Michael-Scott queue or a Treiber stack. Resist unless you have a specific need. The next honest step after SPSC is:

1. Read Anthony Williams C++ Concurrency in Action 2nd ed, Chapter 7 (“Designing lock-free concurrent data structures”).

2. Read Fedor Pikus The Art of Writing Efficient Programs Ch. 8 (concurrency micro-benchmarks with google-benchmark).

3. Study folly::MPMCQueue and boost::lockfree::spsc_queue — read the code, don’t copy it.

9. Common bugs

1. memory_order_relaxed for the head/tail store. Kills correctness on ARM/Apple Silicon. Payload writes get reordered past the index update; consumer reads garbage. On x86 you might get away with it by accident — that is worse than crashing.

2. Sharing a cache line between producer and consumer indices. Correct but 5-10x slower than it should be. alignas(hardware_destructive_interference_size) is not optional.

3. Off-by-one on capacity. A ring of N slots holds N-1 items (one slot is always empty to distinguish full from empty). Get this wrong and you deadlock.

4. Non-trivially destructible T. Ring must destroy each moved-out slot; a naive head++ leaks.

5. Publishing via std::atomic<T*> with memory_order_relaxed. Same class of bug as (1). If you publish a pointer, use release/acquire.

6. Testing only on your Mac. Your M-series is weakly ordered but not maximally so. Run the same test on Linux/ARM if you can (a qemu-aarch64 run under TSan catches many bugs). If you cannot, run under rr on Linux/x86 to be sure the algorithm is not accidentally x86-TSO-dependent.

---

Required reading

• Erik Rigtorp — rigtorp.se/ringbuffer/ and github.com/rigtorp/SPSCQueue (the source you are cloning conceptually).

• Fedor Pikus — CppCon 2016 “Speed of Concurrency: is lock-free faster?” on YouTube. Watch before you write your own queue.

• Anthony Williams — C++ Concurrency in Action 2nd ed, Chapters 5-7.

• Paul McKenney — Is Parallel Programming Hard, And, If So, What Can You Do About It? (free PDF). The reference on memory models and RCU. Skim, don’t read cover to cover.

• cppreference <atomic> — hardware_destructive_interference_size, compare_exchange_weak, atomic_thread_fence.

Exercises

1. Delete the cached_tail_/cached_head_ fields, rerun the benchmark. Confirm the throughput cliff. Measure the ratio.

2. Change one memory_order_release to memory_order_relaxed. On x86 the test may still pass. Run under TSan — confirm it screams. Now cross-compile for aarch64-linux-gnu and run under qemu.

3. Write a wait-free single-item slot (one producer, one consumer, one T). Compare to the ring — which is easier to prove correct?

---

Nav: ← 03 Async, Futures, Coroutines · Phase 3 README · → 05 Linux Syscalls for C++