Lock-Free Queues & Ring Buffers in C++

TL;DR

Lock-free queues replace mutexes with atomic operations and careful memory ordering. The simplest and fastest is an SPSC ring buffer (single producer, single consumer) — it uses only two atomics and is the backbone of HFT market data pipelines. MPMC (multi-producer, multi-consumer) requires more synchronization but still beats mutexes for throughput.

Why lock-free?

A mutex call can take 100ns–10µs depending on contention and OS scheduler behavior. In HFT, the entire processing pipeline may need to complete in 1µs. Mutexes are simply off the table for the hot path.

Lock-free queues replace std::mutex with std::atomic operations — the CPU handles synchronization at the hardware level, without OS involvement.

SPSC ring buffer

Single Producer, Single Consumer — the simplest lock-free queue. No contention, no CAS loop — just one atomic load and one atomic store per operation.

cpp

Godbolt

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

template<typename T, size_t N>
class SPSCQueue {
    static_assert((N & (N - 1)) == 0, "N must be a power of 2");

public:
    bool push(const T& val) {
        const size_t head = head_.load(std::memory_order_relaxed);
        const size_t next = (head + 1) & (N - 1);

        if (next == tail_.load(std::memory_order_acquire))
            return false;  // full

        buffer_[head] = val;
        head_.store(next, std::memory_order_release);
        return true;
    }

    std::optional<T> pop() {
        const size_t tail = tail_.load(std::memory_order_relaxed);

        if (tail == head_.load(std::memory_order_acquire))
            return std::nullopt;  // empty

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

    bool empty() const {
        return head_.load(std::memory_order_acquire) ==
               tail_.load(std::memory_order_acquire);
    }

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

Why alignas(64)? head_ and tail_ are on separate cache lines — preventing false sharing where the producer and consumer invalidate each other's cache lines.

Why power-of-2 size? The modulo % N becomes a cheap bitwise AND: & (N-1).

Memory ordering explanation

push: writes buffer_[head], then does release store on head_ — guarantees consumer sees the write to buffer_ before the updated head_.
pop: does acquire load on head_ — establishes happens-before with the producer's release store.
relaxed loads on own index — only this thread writes it, no sync needed.

MPMC ring buffer

Multi-producer, multi-consumer requires CAS (compare-and-swap) to claim slots:

cpp

Godbolt

template<typename T, size_t N>
class MPMCQueue {
    static_assert((N & (N - 1)) == 0);

    struct Slot {
        std::atomic<size_t> sequence;
        T data;
    };

public:
    MPMCQueue() {
        for (size_t i = 0; i < N; ++i)
            slots_[i].sequence.store(i, std::memory_order_relaxed);
        head_.store(0, std::memory_order_relaxed);
        tail_.store(0, std::memory_order_relaxed);
    }

    bool push(const T& val) {
        size_t pos = head_.load(std::memory_order_relaxed);
        for (;;) {
            Slot& slot = slots_[pos & (N - 1)];
            size_t seq = slot.sequence.load(std::memory_order_acquire);
            intptr_t diff = static_cast<intptr_t>(seq) - static_cast<intptr_t>(pos);

            if (diff == 0) {
                // Slot ready — try to claim it
                if (head_.compare_exchange_weak(pos, pos + 1, std::memory_order_relaxed))
                    break;
            } else if (diff < 0) {
                return false;  // queue full
            } else {
                pos = head_.load(std::memory_order_relaxed);
            }
        }
        slots_[pos & (N - 1)].data = val;
        slots_[pos & (N - 1)].sequence.store(pos + 1, std::memory_order_release);
        return true;
    }

    std::optional<T> pop() {
        size_t pos = tail_.load(std::memory_order_relaxed);
        for (;;) {
            Slot& slot = slots_[pos & (N - 1)];
            size_t seq = slot.sequence.load(std::memory_order_acquire);
            intptr_t diff = static_cast<intptr_t>(seq) - static_cast<intptr_t>(pos + 1);

            if (diff == 0) {
                if (tail_.compare_exchange_weak(pos, pos + 1, std::memory_order_relaxed))
                    break;
            } else if (diff < 0) {
                return std::nullopt;  // empty
            } else {
                pos = tail_.load(std::memory_order_relaxed);
            }
        }
        T val = slots_[pos & (N - 1)].data;
        slots_[pos & (N - 1)].sequence.store(pos + N, std::memory_order_release);
        return val;
    }

private:
    alignas(64) std::atomic<size_t> head_;
    alignas(64) std::atomic<size_t> tail_;
    alignas(64) std::array<Slot, N> slots_;
};

The ABA problem

ABA is a classic lock-free pitfall: a CAS succeeds incorrectly because a value was changed from A → B → A.

cpp

Godbolt

Thread 1: reads head = 0x1000 (node A)
Thread 2: pops A, pushes B, pops B, pushes A — same address
Thread 1: CAS(head, 0x1000, next) succeeds — but the queue state is wrong

Ring buffers with sequence numbers (above) are immune to ABA because the sequence strictly increases — the same slot never has the same sequence twice.

For pointer-based lists, use tagged pointers or hazard pointers.

Production alternatives

Don't write your own in production — use battle-tested implementations:

cpp

Godbolt

// Folly's MPMC queue — Facebook production tested
#include <folly/MPMCQueue.h>
folly::MPMCQueue<Order> queue(1024);
queue.blockingWrite(order);
queue.blockingRead(result);

// Boost.Lockfree
#include <boost/lockfree/spsc_queue.hpp>
boost::lockfree::spsc_queue<MarketUpdate, boost::lockfree::capacity<8192>> q;
q.push(update);
MarketUpdate u;
q.pop(u);

// moodycamel::ConcurrentQueue (header-only, excellent performance)
#include "concurrentqueue.h"
moodycamel::ConcurrentQueue<Order> cq;
cq.enqueue(order);
cq.try_dequeue(result);

Benchmark guidance

Measure with realistic workloads:

cpp

Godbolt

// Pin threads to cores to avoid scheduler interference
cpu_set_t cpuset;
CPU_ZERO(&cpuset);
CPU_SET(3, &cpuset);
pthread_setaffinity_np(pthread_self(), sizeof(cpuset), &cpuset);

// Use rdtsc for nanosecond timing
uint64_t start = __rdtsc();
queue.push(item);
uint64_t cycles = __rdtsc() - start;

Expect SPSC push/pop at ~10-20ns on a modern CPU; MPMC at ~30-50ns per operation under contention.