Building a SPSC Queue in C++

Table of Contents

• Minimize Synchronization
• Use a Power-of-Two Buffer Size
• Avoid False Sharing
• Cache Remote Indices Locally
• Respect Memory Ordering

Minimize Synchronization

A Single-Producer Single-Consumer (SPSC) queue is a particularly useful case for a lock-free data structure. We know that exactly one thread produces data and exactly one thread consumes it. This gives us an important property: each index has a single owner.

The producer is the only thread that modifies tail, while the consumer is the only thread that modifies head. Neither thread needs to compete with another thread when updating its own index.

This means we can avoid mutexes entirely and use atomics only when one thread needs to observe the other thread's progress. The key idea is simple:

The queue therefore maintains two indices:

1std::atomic<size_t> head_{0};
2std::atomic<size_t> tail_{0};
3
4std::array<T, Capacity> buffer_;

The producer writes to the buffer and advances tail. The consumer reads from the buffer and advances head.

Because there is only one producer and one consumer, we do not need a CAS loop to update these indices. Each thread owns its own index and simply increments it.

Use a Power-of-Two Buffer Size

The queue uses a circular buffer, so once an index reaches the end of the array, it needs to wrap back around to the beginning.

The straightforward implementation uses the modulo operator:

1size_t index = position % capacity;

If the capacity is restricted to a power of two, we can instead use a bitwise AND:

1size_t index = position & (capacity - 1);

For example, if the capacity is 1024, thencapacity - 1 is1023, whose binary representation contains all ones in the lower bits.

This allows the CPU to perform the circular-buffer indexing using a simple bitwise operation. More importantly, it gives the compiler a very predictable indexing pattern for this extremely hot path.

Avoid False Sharing

Even though the producer and consumer operate on different variables, they can still interfere with each other through the CPU cache hierarchy.

CPUs move memory between cores in cache lines, typically 64 bytes on modern x86 processors. If head and tail happen to occupy the same cache line, updating one can invalidate the cache line containing the other.

This is known as false sharing. The two threads are modifying completely independent variables, but the hardware still has to move and invalidate the cache line between cores.

1alignas(64) std::atomic<size_t> head_{0};
2alignas(64) std::atomic<size_t> tail_{0};

By separating the two indices onto different cache lines, the producer and consumer can update their local state without unnecessarily invalidating the other thread's cache line.

Cache Remote Indices Locally

The producer owns tailand the consumer owns head. However, each thread occasionally needs to inspect the other thread's index.

For example, the producer needs to know how far the consumer has progressed before deciding whether the queue is full. The consumer similarly needs to know the producer's position before deciding whether the queue is empty.

Instead of repeatedly reading these remote atomics, we can maintain cached copies:

1size_t head_local = 0;
2size_t tail_local = 0;
3
4size_t head_cached = 0;
5size_t tail_cached = 0;

The thread only refreshes its cached copy when it actually needs fresh information. For example, the producer does not need to read the consumer's head on every push. It can continue using its cached value until the queue appears to be full.

This reduces the number of atomic loads and therefore reduces the amount of cache-coherence traffic between the two cores.

Respect Memory Ordering

Avoiding locks is only useful if the queue is still correct. The producer and consumer must agree on when data in the buffer becomes visible to the other thread.

Consider the producer:

1buffer[index] = value;
2tail.store(next_tail, std::memory_order_release);

The producer first writes the data into the buffer and only then publishes the new tail position using a release store.

The consumer observes that publication using an acquire load:

1size_t tail = tail_.load(std::memory_order_acquire);
2value = buffer[index];

The release/acquire pair establishes a happens-before relationship. Once the consumer observes the producer's published tail value, it is guaranteed to see the writes to the buffer that happened before that release operation.

Putting It Together

Combining these ideas gives us a compact SPSC queue. The important properties are that each index has a single writer, the circular buffer uses power-of-two indexing, the indices are separated to avoid false sharing, and acquire/release ordering is used to publish data safely between the two threads.

1#include <array>
2#include <atomic>
3#include <cstddef>
4#include <utility>
5
6template <typename T, size_t Capacity>
7class SPSCQueue
8{
9    static_assert(
10        Capacity > 0 && (Capacity & (Capacity - 1)) == 0,
11        "Capacity must be a power of two"
12    );
13
14private:
15    alignas(64) std::atomic<size_t> head_{0};
16    alignas(64) std::atomic<size_t> tail_{0};
17
18    std::array<T, Capacity> buffer_;
19
20    static constexpr size_t MASK = Capacity - 1;
21
22public:
23    bool push(const T &item)
24    {
25        size_t tail = tail_.load(std::memory_order_relaxed);
26        size_t head = head_.load(std::memory_order_acquire);
27
28        if (tail - head >= Capacity)
29        {
30            return false;
31        }
32
33        buffer_[tail & MASK] = item;
34
35        tail_.store(
36            tail + 1,
37            std::memory_order_release
38        );
39
40        return true;
41    }
42
43    bool pop(T &item)
44    {
45        size_t head = head_.load(std::memory_order_relaxed);
46        size_t tail = tail_.load(std::memory_order_acquire);
47
48        if (head == tail)
49        {
50            return false;
51        }
52
53        item = std::move(buffer_[head & MASK]);
54
55        head_.store(
56            head + 1,
57            std::memory_order_release
58        );
59
60        return true;
61    }
62
63    size_t size() const
64    {
65        size_t tail =
66            tail_.load(std::memory_order_acquire);
67
68        size_t head =
69            head_.load(std::memory_order_acquire);
70
71        return tail - head;
72    }
73
74    bool empty() const
75    {
76        return size() == 0;
77    }
78};

Final Takeaway

A high-performance SPSC queue is not primarily about using atomics. The real performance comes from taking advantage of the constraints of the problem.

Because there is only one producer and one consumer, we can assign ownership of each index, eliminate locks and CAS loops, minimize atomic operations, organize the data structure around cache lines, and use precise memory ordering instead of relying on heavyweight synchronization.