medium.com 12 min read Original Source

Lock-Free in C++ Without the Mysticism: Building an SPSC Queue and Actually Understanding…

Mahad Nadeem

October 23, 2026 · 28 readers

The itch

Most C++ engineers I know have the same relationship with std::memory_order. They have read cppreference twice, they nod at the words “acquire” and “release”, and then they type seq_cst because it compiles and nothing bad happens. That is a perfectly good engineering decision. It is also a bad place to stay if you write latency-sensitive code, because the alternative to understanding is one of two failure modes: sprinkling relaxed around until a benchmark looks nice, or never touching atomics at all and wrapping everything in a mutex forever.

So here is the plan. We will build the smallest lock-free structure that is actually useful, a single-producer single-consumer ring buffer, and we will justify every single memory order in it. By the end you should be able to look at an acquire/release pair in someone else’s code and say whether it is correct, and why.

Everything below is C++20, but nothing exotic is used. The ideas are the same in C++11.

Why SPSC is the right teaching structure

Multi-producer queues need compare-and-swap loops, ABA protection, and memory reclamation, and each of those deserves its own article. The single-producer single-consumer case strips all of that away. Exactly one thread writes tail, exactly one thread writes head, and nobody ever contends on a write. There is no retry loop. Both operations finish in a bounded number of steps, which makes the queue wait-free rather than merely lock-free.

It is also not a toy. SPSC rings sit between a network thread and a parser, between an audio callback and a worker, between a logging call site and a background writer. If you have a pipeline where the shape is “one thread hands work to the next”, this is the structure you want.

The mental model: happens-before, not cache flushes

The most common wrong idea about memory ordering is that release means “flush my caches” and acquire means “refresh my caches”. It is a decent story for a first week, and it will mislead you for years. The C++ standard says nothing about caches. Hardware cache coherence already makes a single memory location behave sanely. What it does not give you is any promise about the order in which writes to different locations become visible to another core, and the compiler adds its own reordering on top.

The language gives you a different tool: the happens-before relation. If operation A happens-before operation B, then everything A did is visible to B. Memory orders are how you build that relation across threads, and the pattern you need most often has exactly two parts:

Thread 1 writes some data, then does a release store to an atomic flag.
Thread 2 does an acquire load of that same flag and sees the value thread 1 stored.

When that happens, the load synchronizes-with the store. Every write thread 1 made before its release store is guaranteed to be visible to thread 2 after its acquire load. Release says “nothing I did earlier may be moved after this store”. Acquire says “nothing I do later may be moved before this load”. The atomic variable is the handshake, and the payload rides along for free.

Hold on to that picture. The whole queue is two of those handshakes running in opposite directions.

Attempt 0: the version that looks right

Here is the queue most people write the first time, and it is wrong in at least three ways.

// Do not use. Shown so we know what we are fixing.
struct BrokenQueue {
    static constexpr std::size_t N = 1024;
    int buf[N];
    std::size_t head = 0, tail = 0;   // plain integers shared across threads
bool push(int v) {                // producer thread
        if (tail - head == N) return false;
        buf[tail % N] = v;
        ++tail;
        return true;
    }
    std::optional<int> pop() {        // consumer thread
        if (head == tail) return std::nullopt;
        int v = buf[head % N];
        ++head;
        return v;
    }
};

// Do not use. Shown so we know what we are fixing.
struct BrokenQueue {
    static constexpr std::size_t N = 1024;
    int buf[N];
    std::size_t head = 0, tail = 0;   // plain integers shared across threads
bool push(int v) {                // producer thread
        if (tail - head == N) return false;
        buf[tail % N] = v;
        ++tail;
        return true;
    }
    std::optional<int> pop() {        // consumer thread
        if (head == tail) return std::nullopt;
        int v = buf[head % N];
        ++head;
        return v;
    }
};

The first problem is the obvious one: concurrent unsynchronized access to tail and head is a data race, which is undefined behavior, full stop. The second is subtler. Even if you ignore the UB, nothing stops the compiler or the CPU from making ++tail visible before the store to buf[tail % N]. The consumer then sees a new tail, reads a slot that has not been written yet, and returns garbage. The third is that the compiler is allowed to hoist the load of tail out of any loop that polls it, so a consumer spinning on pop() can in theory never notice new data.

People reach for volatile here. Do not. volatile stops the compiler from caching a value in a register, but it provides no atomicity guarantees and no ordering against other memory accesses. It is the wrong tool in standard C++.

Attempt 1: correct, boring, seq_cst

The first fix is to make the indices atomic and leave every operation at its default ordering, which is memory_order_seq_cst.

struct SeqCstQueue {
    static constexpr std::size_t N = 1024;
    int buf[N];
    std::atomic<std::size_t> head{0}, tail{0};
bool push(int v) {
        auto t = tail.load();
        if (t - head.load() == N) return false;
        buf[t % N] = v;
        tail.store(t + 1);
        return true;
    }
    std::optional<int> pop() {
        auto h = head.load();
        if (h == tail.load()) return std::nullopt;
        int v = buf[h % N];
        head.store(h + 1);
        return v;
    }
};

struct SeqCstQueue {
    static constexpr std::size_t N = 1024;
    int buf[N];
    std::atomic<std::size_t> head{0}, tail{0};
bool push(int v) {
        auto t = tail.load();
        if (t - head.load() == N) return false;
        buf[t % N] = v;
        tail.store(t + 1);
        return true;
    }
    std::optional<int> pop() {
        auto h = head.load();
        if (h == tail.load()) return std::nullopt;
        int v = buf[h % N];
        head.store(h + 1);
        return v;
    }
};

This one is correct. Sequential consistency gives every atomic operation a place in a single total order that all threads agree on, and it implies acquire/release semantics for the loads and stores. I would happily ship this as a first version. Measure before you optimize.

But seq_cst buys more than this queue needs. A single total order across all atomics is a global property, and we only have two atomics with a very specific relationship. The interesting question is: what is the weakest ordering that is still correct, and can we say why?

Attempt 2: say what you mean

Here is the version I would put in a codebase. Read the code first, then the reasoning.

<button data-code="#include
#include
#include
#include
#include
#include
template
class SpscQueue {
static_assert(Capacity >= 2 && (Capacity & (Capacity – 1)) == 0,
"Capacity must be a power of two");
static_assert(std::atomic::is_always_lock_free);
static constexpr std::size_t kLine = 64;
static constexpr std::size_t kMask = Capacity – 1;
static_assert(alignof(T) ~T();
}
// Producer thread only.
template
bool try_emplace(Args&&… args) {
const auto t = tail_.load(std::memory_order_relaxed);
if (t – head_cache_ == Capacity) {
head_cache_ = head_.load(std::memory_order_acquire);
if (t – head_cache_ == Capacity) return false; // really full
}
::new (raw(t)) T(std::forward(args)…);
tail_.store(t + 1, std::memory_order_release);
return true;
}
bool try_push(const T& v) { return try_emplace(v); }
bool try_push(T&& v) { return try_emplace(std::move(v)); }
// Consumer thread only.
std::optional try_pop() {
const auto h = head_.load(std::memory_order_relaxed);
if (h == tail_cache_) {
tail_cache_ = tail_.load(std::memory_order_acquire);
if (h == tail_cache_) return std::nullopt; // really empty
}
T* p = obj(h);
std::optional out{std::move(*p)};
p->~T();
head_.store(h + 1, std::memory_order_release);
return out;
}
private:
void* raw(std::size_t i) noexcept { return buf_ + (i & kMask) * sizeof(T); }
T* obj(std::size_t i) noexcept { return std::launder(reinterpret_cast(raw(i))); }
// Consumer-owned line: written only by the consumer.
alignas(kLine) std::atomic head_{0};
std::size_t tail_cache_ = 0;
// Producer-owned line: written only by the producer.
alignas(kLine) std::atomic tail_{0};
std::size_t head_cache_ = 0;
alignas(kLine) std::byte buf_[Capacity * sizeof(T)];
};” data-toggle-ms=”1200″ aria-label=”Copy code” data-nosnippet=”” class=”code-copy-btn absolute right-3 top-3 size-8 p-1.5 flex items-center justify-center bg-black/50 text-white rounded-md transition-colors duration-200 cursor-pointer hover:bg-black/70″>

#include <atomic>
#include <cstddef>
#include <memory>
#include <new>
#include <optional>
#include <utility>
template <typename T, std::size_t Capacity>
class SpscQueue {
    static_assert(Capacity >= 2 && (Capacity & (Capacity - 1)) == 0,
                  "Capacity must be a power of two");
    static_assert(std::atomic<std::size_t>::is_always_lock_free);
    static constexpr std::size_t kLine = 64;
    static constexpr std::size_t kMask = Capacity - 1;
    static_assert(alignof(T) <= kLine);
public:
    SpscQueue() = default;
    SpscQueue(const SpscQueue&) = delete;
    SpscQueue& operator=(const SpscQueue&) = delete;
    ~SpscQueue() {                       // not thread-safe: both sides must be done
        auto h = head_.load(std::memory_order_relaxed);
        const auto t = tail_.load(std::memory_order_relaxed);
        for (; h != t; ++h) obj(h)->~T();
    }
    // Producer thread only.
    template <typename... Args>
    bool try_emplace(Args&&... args) {
        const auto t = tail_.load(std::memory_order_relaxed);
        if (t - head_cache_ == Capacity) {
            head_cache_ = head_.load(std::memory_order_acquire);
            if (t - head_cache_ == Capacity) return false;   // really full
        }
        ::new (raw(t)) T(std::forward<Args>(args)...);
        tail_.store(t + 1, std::memory_order_release);
        return true;
    }
    bool try_push(const T& v) { return try_emplace(v); }
    bool try_push(T&& v)      { return try_emplace(std::move(v)); }
    // Consumer thread only.
    std::optional<T> try_pop() {
        const auto h = head_.load(std::memory_order_relaxed);
        if (h == tail_cache_) {
            tail_cache_ = tail_.load(std::memory_order_acquire);
            if (h == tail_cache_) return std::nullopt;       // really empty
        }
        T* p = obj(h);
        std::optional<T> out{std::move(*p)};
        p->~T();
        head_.store(h + 1, std::memory_order_release);
        return out;
    }
private:
    void* raw(std::size_t i) noexcept { return buf_ + (i & kMask) * sizeof(T); }
    T*    obj(std::size_t i) noexcept { return std::launder(reinterpret_cast<T*>(raw(i))); }
    // Consumer-owned line: written only by the consumer.
    alignas(kLine) std::atomic<std::size_t> head_{0};
    std::size_t tail_cache_ = 0;
    // Producer-owned line: written only by the producer.
    alignas(kLine) std::atomic<std::size_t> tail_{0};
    std::size_t head_cache_ = 0;
    alignas(kLine) std::byte buf_[Capacity * sizeof(T)];
};

#include <atomic>
#include <cstddef>
#include <memory>
#include <new>
#include <optional>
#include <utility>
template <typename T, std::size_t Capacity>
class SpscQueue {
    static_assert(Capacity >= 2 && (Capacity & (Capacity - 1)) == 0,
                  "Capacity must be a power of two");
    static_assert(std::atomic<std::size_t>::is_always_lock_free);
    static constexpr std::size_t kLine = 64;
    static constexpr std::size_t kMask = Capacity - 1;
    static_assert(alignof(T) <= kLine);
public:
    SpscQueue() = default;
    SpscQueue(const SpscQueue&) = delete;
    SpscQueue& operator=(const SpscQueue&) = delete;
    ~SpscQueue() {                       // not thread-safe: both sides must be done
        auto h = head_.load(std::memory_order_relaxed);
        const auto t = tail_.load(std::memory_order_relaxed);
        for (; h != t; ++h) obj(h)->~T();
    }
    // Producer thread only.
    template <typename... Args>
    bool try_emplace(Args&&... args) {
        const auto t = tail_.load(std::memory_order_relaxed);
        if (t - head_cache_ == Capacity) {
            head_cache_ = head_.load(std::memory_order_acquire);
            if (t - head_cache_ == Capacity) return false;   // really full
        }
        ::new (raw(t)) T(std::forward<Args>(args)...);
        tail_.store(t + 1, std::memory_order_release);
        return true;
    }
    bool try_push(const T& v) { return try_emplace(v); }
    bool try_push(T&& v)      { return try_emplace(std::move(v)); }
    // Consumer thread only.
    std::optional<T> try_pop() {
        const auto h = head_.load(std::memory_order_relaxed);
        if (h == tail_cache_) {
            tail_cache_ = tail_.load(std::memory_order_acquire);
            if (h == tail_cache_) return std::nullopt;       // really empty
        }
        T* p = obj(h);
        std::optional<T> out{std::move(*p)};
        p->~T();
        head_.store(h + 1, std::memory_order_release);
        return out;
    }
private:
    void* raw(std::size_t i) noexcept { return buf_ + (i & kMask) * sizeof(T); }
    T*    obj(std::size_t i) noexcept { return std::launder(reinterpret_cast<T*>(raw(i))); }
    // Consumer-owned line: written only by the consumer.
    alignas(kLine) std::atomic<std::size_t> head_{0};
    std::size_t tail_cache_ = 0;
    // Producer-owned line: written only by the producer.
    alignas(kLine) std::atomic<std::size_t> tail_{0};
    std::size_t head_cache_ = 0;
    alignas(kLine) std::byte buf_[Capacity * sizeof(T)];
};

Now the reasoning, one decision at a time.

Why the loads of your own index are relaxed. tail_ is written by exactly one thread, the producer. When the producer reads it back, it is reading its own most recent write, and program order plus the coherence of a single variable guarantee it sees that value. No other thread is publishing anything through that read, so there is nothing to synchronize with. The same holds for the consumer and head_.

Why tail_.store(..., release) is the publication point. The producer constructs the element, which is a bunch of ordinary non-atomic writes into the buffer, and only then stores the new tail. The release ordering promises that those constructor writes cannot be reordered past the store. So anyone who observes the new tail value also observes a fully constructed element.

Why the consumer’s tail_.load(acquire) is the matching half. The consumer reads the tail. If it sees the producer’s new value, that load synchronizes-with the producer’s release store, and the element becomes safely readable. If the consumer used relaxed here, it could observe the new tail and still read stale bytes from the slot. That is the bug from Attempt 0, resurrected.

Why there is a second handshake going the other way. Slots get reused. Before the producer overwrites slot i, it must be sure the consumer has finished reading and destroying whatever was there. The consumer finishes with the slot, then does head_.store(..., release). The producer’s head_.load(acquire) pairs with it. That gives a happens-before edge from the consumer’s last read of the slot to the producer’s next write into it. Without this pair, the producer could scribble over an element the consumer is still moving out. It is the same pattern, mirrored.

Why indices only ever grow. We never reduce head_ or tail_ modulo the capacity. They are free-running counters, and we mask only when indexing the buffer. The queue is empty when head == tail and full when tail - head == Capacity, and there is no “one slot wasted” trick needed to tell the cases apart. Unsigned wraparound is well defined, and because the capacity is a power of two it divides 2^N for the width of size_t, so the subtraction and the mask stay consistent even when the counters wrap. On a 64-bit platform you will not see a wrap in your lifetime, and on a 32-bit one it still works.

Cache lines: where the real time goes

If you take one thing from this section, take this: the cost of a lock-free queue is mostly not the atomic instructions. It is cache coherence traffic.

A core can only write to a cache line it owns exclusively. When two cores take turns writing to the same line, ownership bounces between them, and each bounce costs on the order of tens to hundreds of cycles depending on topology. That is why the code above puts head_ and tail_ on separate cache lines with alignas(kLine). If they shared a line, the producer updating tail_ would keep invalidating the consumer’s copy of head_ even though the two threads never touch each other’s variable. This is false sharing, and it can silently eat most of the speedup you thought lock-free would give you.

A note on the constant. C++17 added std::hardware_destructive_interference_size, and in theory it is the right thing to use. In practice GCC warns when you use it in a header because the value can differ between translation units compiled with different flags, so many codebases hardcode 64. Be aware that some CPUs effectively behave as if the line were 128 bytes, either because the line really is that large, as on Apple’s M-series chips, or because the hardware prefetches adjacent lines in pairs. If you ship to those targets, use 128.

The cached indices are the second optimization, and they are worth understanding. Without them, every try_emplace would perform an acquire load of head_, pulling the consumer’s cache line over to the producer on every single push. With them, the producer keeps a private copy of the last head_ value it saw, and only goes to the shared variable when its stale copy says the queue looks full. In a healthy pipeline where the consumer keeps up, the producer reads head_ once every Capacity pushes instead of every push. The consumer does the same trick with tail_. Both cached values live next to the variable their owner writes, so they cost nothing in extra line traffic.

One honest caveat. I am not going to quote a throughput number, because it depends heavily on whether the two threads share an L2, sit on different chiplets, or live on different sockets. Pin your threads, run it on your own hardware, and compare against the seq_cst baseline. The direction is reliable. The magnitude is yours to measure.

Does seq_cst actually cost anything here?

It depends on the architecture, and the answer is more interesting than “yes, it is slower”.

On x86–64, loads are already acquire and stores are already release at the instruction level, because the hardware memory model (total store order) is strong. So acquire loads and release stores compile to plain mov instructions. A seq_cst store, however, needs an extra full barrier, typically emitted as an xchg or a mov followed by mfence. So on x86, relaxing the stores from seq_cst to release removes a real fence from the hot path of every push and pop.

On AArch64, the picture flips. Sequentially consistent loads and stores are implemented with the ldar and stlr instructions, and release stores use stlr as well. The difference between seq_cst and acquire/release for simple loads and stores is small to nonexistent on modern ARM cores. You would be doing the work for correctness and clarity of intent, not speed.

That second point is worth sitting with. Choosing the weakest correct ordering is not only an optimization. It is documentation. When a reader sees release on a store and acquire on the load, they know exactly which handshake you intended. When they see seq_cst everywhere, they know nothing about what you were thinking.

Proving it, or at least trying to

Lock-free code is the area where “it passed my tests” means the least. Here is the minimum I would insist on.

First, a stress test that checks ordering and completeness, not just absence of crashes. The producer sends the integers 0..N, and the consumer verifies it receives exactly that sequence.

<button data-code="#include
#include
#include
int main() {
SpscQueue q;
constexpr std::uint64_t N = 20'000'000;
std::thread producer([&] {
for (std::uint64_t i = 0; i < N;) {
if (q.try_push(i)) ++i; // spin when full
}
});
std::uint64_t expected = 0;
while (expected

#include <cstdint>
#include <cstdio>
#include <thread>
int main() {
    SpscQueue<std::uint64_t, 1024> q;
    constexpr std::uint64_t N = 20'000'000;
    std::thread producer([&] {
        for (std::uint64_t i = 0; i < N;) {
            if (q.try_push(i)) ++i;          // spin when full
        }
    });
    std::uint64_t expected = 0;
    while (expected < N) {
        if (auto v = q.try_pop()) {
            if (*v != expected) {
                std::printf("out of order: got %llu, expected %llun",
                            (unsigned long long)*v, (unsigned long long)expected);
                return 1;
            }
            ++expected;
        }
    }
    producer.join();
    std::puts("ok");
}

#include <cstdint>
#include <cstdio>
#include <thread>
int main() {
    SpscQueue<std::uint64_t, 1024> q;
    constexpr std::uint64_t N = 20'000'000;
    std::thread producer([&] {
        for (std::uint64_t i = 0; i < N;) {
            if (q.try_push(i)) ++i;          // spin when full
        }
    });
    std::uint64_t expected = 0;
    while (expected < N) {
        if (auto v = q.try_pop()) {
            if (*v != expected) {
                std::printf("out of order: got %llu, expected %llun",
                            (unsigned long long)*v, (unsigned long long)expected);
                return 1;
            }
            ++expected;
        }
    }
    producer.join();
    std::puts("ok");
}

Second, run it under ThreadSanitizer: g++ -std=c++20 -O2 -fsanitize=thread -g test.cpp -pthread. TSan understands std::atomic and the happens-before edges it creates, so if you downgrade an ordering that was actually needed, it will usually tell you. Drop N to a couple of million when you do, because TSan makes everything several times slower.

Third, and this is the one people skip, test on a weakly ordered CPU. x86 will forgive many ordering bugs, because the hardware already provides acquire/release behavior for ordinary loads and stores. Code that is subtly wrong can run clean for a decade on a Xeon and fall over the first week it runs on an ARM server or a phone. A small ARM instance in the cloud, or an Apple Silicon laptop, is cheap insurance. Be aware that even on x86 the compiler still reorders, so the bug is not always invisible there, only less likely to be.

If the queue is going into something that matters, formal-ish tools such as Relacy or CDSChecker explore interleavings and weak-memory behaviors systematically. They are not fun to set up. They are also the only things that find the bugs that appear once in ten billion operations.

Things that will bite you

It is single-producer and single-consumer, and nothing enforces that. Call try_emplace from two threads and you have two writers of tail_ and a race that no ordering can fix. If your design might violate the contract, wrap the queue in a type that makes misuse awkward, or assert on thread ids in debug builds.

Non-trivial element types need more thought than they appear to. The code above handles construction, move-out, and destruction correctly, and it returns the element by value via std::optional<T>. If T has a throwing move constructor, try_pop leaves the element in the slot and does not advance head_, so the queue stays consistent, but the caller sees the exception. For large objects, consider a try_pop(T& out) overload to avoid the extra move.

The destructor assumes quiescence. It walks the live range and destroys leftover elements, which is only safe once both threads have stopped. Document that, or make the owner join first.

Spinning is not free. The test above burns a core while waiting. That is fine for a benchmark and wrong for most production code. If the consumer should sleep when idle, C++20 gives you std::atomic::wait and notify_one, which you can layer on top of tail_. Keep the fast path lock-free and only block after a bounded spin.

Capacity is a performance parameter, not just a safety one. A ring that is far larger than your working set pushes the buffer out of cache. A ring that is too small makes the producer stall on head_ constantly and defeats the cached-index trick. Size it to absorb your burstiness, and keep it a power of two.

When you should not write this yourself

If you need multiple producers or multiple consumers, stop. That is a different, much harder problem, and you should reach for a battle-tested implementation. For SPSC itself, boost::lockfree::spsc_queue, folly::ProducerConsumerQueue, and rigtorp::SPSCQueue are all solid and have been run on far more hardware than your test lab.

The honest argument for writing your own is not performance. It is that you want the exact semantics, such as a batch-pop API, a specific allocation strategy, or a zero-copy interface, and that you now know how to verify them. Even then, write the seq_cst version first, get it correct, measure, and only then tighten the orderings with a reason attached to each one.

What to take away

The whole mental model fits in a few sentences. Atomics are not about flushing caches, they are about building happens-before edges between threads. A release store paired with an acquire load of the same variable is the basic handshake, and everything written before the store is visible after the load. A queue is two of those handshakes in opposite directions: one saying “the data is ready”, the other saying “the slot is free”. The loads of your own index can be relaxed because nobody publishes through them. And after correctness comes the physical layer, where false sharing and cache-line ping-pong cost more than any instruction you will ever micro-optimize.

The next time you see memory_order_relaxed in a code review, do not ask whether it is faster. Ask which handshake it is not part of, and what would break if it were. If the author can answer in one sentence, the code is probably fine. If they cannot, you have found the real bug, and it was never about performance.