The single-producer single-consumer ring buffer

Most of the difficulty in concurrent queues comes from several threads competing to update the same index. With exactly one producer and one consumer, there is no competition: the producer is the only thread that writes the tail, the consumer the only one that writes the head. Each thread reads the other's index to know how far it may go. No compare-and-swap, no locks, no retries.

• A fixed array of slots, allocated once, with a capacity that is a power of two so that wrapping an index is a mask instead of a division.
• tail: the next slot the producer will write. Written only by the producer.
• head: the next slot the consumer will read. Written only by the consumer.
• The queue is empty when head == tail and full when tail - head == capacity. Using indices that increase for ever and masking them on access (rather than wrapping the indices themselves) makes that distinction free; 64-bit indices will not overflow in the life of the process.

template <class T, std::size_t N>
class SpscRing {
    static_assert((N & (N - 1)) == 0, "capacity must be a power of two");
    std::array<T, N> slots_;
    alignas(64) std::atomic<std::uint64_t> tail_{0};    // producer writes
    alignas(64) std::atomic<std::uint64_t> head_{0};    // consumer writes
public:
    bool push(const T& v) {
        const auto t = tail_.load(std::memory_order_relaxed);          // our own index
        if (t - head_.load(std::memory_order_acquire) == N) return false;   // full
        slots_[t & (N - 1)] = v;
        tail_.store(t + 1, std::memory_order_release);                 // publish the slot
        return true;
    }
    bool pop(T& out) {
        const auto h = head_.load(std::memory_order_relaxed);          // our own index
        if (h == tail_.load(std::memory_order_acquire)) return false;  // empty
        out = slots_[h & (N - 1)];
        head_.store(h + 1, std::memory_order_release);                 // free the slot
        return true;
    }
};

• The producer reads its own tail_ relaxed: no other thread writes it.
• The producer's release store of tail_ publishes the slot it just wrote. The consumer's acquire load of tail_ pairs with it, so when the consumer sees the new tail, the slot's contents are visible. This is the publication pattern from the previous lesson.
• The consumer's release store of head_ says "I have finished reading this slot". The producer's acquire load of head_ pairs with it, so the producer never overwrites a slot the consumer is still reading.

Separate cache lines. head_ and tail_ are written by different threads. If they shared a 64-byte line, every push would invalidate the consumer's copy of the line and every pop the producer's, even though neither thread writes the other's variable. That is false sharing (Module 5). alignas(64) puts each on its own line. Some implementations use 128 bytes because some Intel prefetchers pull in adjacent pairs of lines; std::hardware_destructive_interference_size names the value where the library provides it.

Cache the other side's index. Each push loads head_, a line the consumer keeps writing, so the load usually misses. But the producer only needs the exact head when the queue looks full. Keep a private copy and refresh it only then:

// producer side, inside push:
if (t - head_cache_ == N) {                                   // looks full: refresh
    head_cache_ = head_.load(std::memory_order_acquire);
    if (t - head_cache_ == N) return false;                   // really full
}

The consumer does the same with a cached tail. Now in the common case each side touches only its own lines, and the shared lines move between cores only when the other side has made progress. This one change is often worth more than everything else.

Batch. A consumer that drains several items and then publishes the head once, or a producer that publishes the tail once per burst, moves the shared lines less often.

Avoid copying large items. For big messages, write them in place: T* claim() returns the next slot for the producer to fill, commit() publishes it. The consumer reads in place in the same way.

The producer has three options and the right one depends on what it is:

• Return false and let the caller decide, as above. A strategy sending orders should know.
• Drop and count. A market-data producer that cannot slow the exchange down may drop and record a gap, forcing a resynchronisation (Module 7).
• Overwrite the oldest, for data where only the latest matters, which turns the queue into a different structure with its own synchronisation.

Spinning until there is space is wrong for a feed handler: the network will not wait.