Write an SPSC Queue from Scratch

Memory Layout

Intuitive layout

Let’s start designing the data structure and layout without considering hardware effects such as false sharing, cache coherence, and MESI.

Cache line matters

False sharing between producer and consumer

The data members in the structure, especially read_idx_ and write_idx_, may end up in the same cache line. The cache line will be modified by the producer thread on core 1, then by the consumer thread on core 63. This ping-pong of cache-line ownership keeps the bus busy and makes the existence of cache lines meaningless.

We need the data members laid out in different cache lines. The alignas keyword can help us do that.

static constexpr size_t kCacheLine =
      std::hardware_destructive_interference_size;
  alignas(kCacheLine) size_t capacity_{0};
  alignas(kCacheLine) std::atomic<size_t> read_idx_{0};
  alignas(kCacheLine) std::atomic<size_t> write_idx_{0};

False sharing with other threads

The alignas keyword can avoid false sharing between different data members, but false sharing can still happen between the memory area referred to by slot_ and other variables adjacent to the head and tail of that area.

Allocating redundant memory space is the best way to avoid this false sharing. The extra slots should take up at least kCacheLine bytes, and the formula below calculates the exact number of slots, rounded up.

kPadding = (kCacheLine - 1) / sizeof(T) + 1

Why does this formula round up correctly? Let’s walk through an example: kCacheLine = 16, sizeof(T) = 6.

Integer division rounds down. To round up instead, we use the identity ceil(a / b) = (a - 1) / b + 1 for any a ≥ 1: subtracting 1 makes an exact multiple of b fall into the group below, the division counts the groups, and adding 1 rounds the result back up.

MESI state machine

To explain the next part, let’s first review the MESI states and how the transitions between them happen.

• Modified: dirty data, exclusive, R/W access

• Exclusive: clean data, exclusive, R/W access

• Shared: clean data, non-exclusive (>1 owner), read-only

• Invalid: not present, unknown, unavailable

There are five different bus signals: BusRd, BusRdX, BusUpgr, Flush, Shared.

• BusUpgr

  The copy is already in the Shared state; this signal invalidates all other copies.

• Shared

  Shared is the shared signal line on the snooping bus. Any cache that holds a valid copy of the block asserts Shared during the transaction.

  • I → S on PrRd / BusRd(S), where the shared line was asserted

  • I → E on PrRd / BusRd(S̄), where the shared line was not asserted

This is exactly the piece MSI doesn’t need. In MSI, a read miss always goes to S, so the requester never needs to know whether other copies exist. If another cache holds the block in the Modified state, it flushes the dirty data back to memory on receiving the BusRd, and its state is downgraded to Shared.

Adding the E state is what requires the extra signal. Now the requester’s state does depend on what others hold: E if nobody has it, S otherwise. That dependency is what creates the need for the Shared signal. The signal carries only one bit: “does anyone else have it?”

Transitions triggered by the local processor

The processor itself issues two types of requests, depending on the running code: PrRd and PrWr.

Transitions triggered by other caches’ bus signals

Cache coherence on the cursors

On the producer’s side, the thread needs to read read_idx_ to check whether the queue is full, and also needs to write write_idx_ to publish the element and move forward.

On the consumer’s side, the thread needs to read write_idx_ to check whether the queue is empty, and also needs to write read_idx_ to consume the element and move forward.

Here is a scary scenario: if the two threads advance at the same speed and their operations interleave, every write needs the line in an exclusive state and every read needs it in a shared state, so the copy cached on each core is invalidated almost immediately.

The solution is to keep a cached copy of write_idx_ on the consumer’s core, and a cached copy of read_idx_ on the producer’s core. It’s a lazy-loading mechanism: each thread only loads the newest value and refreshes its cache when the queue looks full or empty from its “cached view”.

Low-latency memory layout

template <typename T, typename AllocatorT = std::allocator<T>>
struct MYSPSC {

private:
  static constexpr size_t kCacheLine =
      std::hardware_destructive_interference_size;
  static constexpr size_t kPadding = (kCacheLine - 1) / sizeof(T) + 1;
  alignas(kCacheLine) size_t capacity_{0};
  alignas(kCacheLine) T *slot_{nullptr};
  [[no_unique_address]] AllocatorT allocator_;
  // Consumer's core
  alignas(kCacheLine) std::atomic<size_t> read_idx_{0};
  alignas(kCacheLine) size_t cached_write_idx_{0};
  // Producer's core
  alignas(kCacheLine) std::atomic<size_t> write_idx_{0};
  alignas(kCacheLine) size_t cached_read_idx_{0};
};

Member functions

Constructor

The main job of the constructor is to allocate appropriate memory for slot_. The size of slot_ should be in the range [1, SIZE_MAX].

The lower bound is 1, because the queue needs one empty slot to distinguish the empty condition from the full condition.

The upper bound is SIZE_MAX, including the 2 * kPadding extra slots, which make sure no other thread shares a cache line with the elements.

static constexpr size_t kMaxLen =
    std::numeric_limits<size_t>::max() - 2 * kPadding;
static constexpr size_t trunc_capacity(size_t capacity) {
  if (capacity == 0) {
     capacity = 1;
  }
  return capacity >= kMaxLen ? kMaxLen : capacity + 1;
}
explicit MYSPSC(const size_t capacity, AllocatorT allocator = AllocatorT())
    : capacity_(trunc_capacity(capacity)), allocator_(allocator) {
  slot_ =
      std::allocator_traits<AllocatorT>::allocate(allocator_, capacity_ + 2 * kPadding);
}

The queue owns the memory behind slot_, so a copy would free the same buffer twice. Copying must be disabled:

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

Producer’s functions

// Blocking function
template <typename... P>
void
emplace(P &&...args) noexcept(std::is_nothrow_constructible_v<T, P &&...>) {
  static_assert(std::is_constructible_v<T, P &&...>,
                "T must be constructible with P&&...");
  const size_t write_idx = write_idx_.load(std::memory_order_relaxed);
  size_t next_write_idx = write_idx + 1;
  if (next_write_idx == capacity_) [[unlikely]] {
    next_write_idx = 0;
  }
  while (next_write_idx == cached_read_idx_) [[unlikely]] {
    cached_read_idx_ = read_idx_.load(std::memory_order_acquire);
  }
  new (&slot_[kPadding + write_idx]) T(std::forward<P>(args)...);
  write_idx_.store(next_write_idx, std::memory_order_release);
}

Forwarding reference

Unlike an rvalue reference, a forwarding reference occurs only when the type is deduced from the call to a function template.

It only takes the form T&& or auto&&; even const T&& is not a forwarding reference. And T must be a template parameter of the function template itself. In a class template like ours, void push(T&& v) is just an rvalue reference, because T was fixed when the class was instantiated. That’s why emplace declares its own template <typename... P>.

• Rvalue reference

void foo(std::string&& s)
{
    std::cout << s << '\n';
}

int main()
{
    std::string str = "hello";

    foo(std::string("world"));   // OK
    foo(std::move(str));         // OK
    // foo(str);                 // Error: lvalue
}

• Forwarding reference

template <typename U>
void bar(U&& u)                  // U is deduced at each call
{
    baz(std::forward<U>(u));     // keeps the value category of the argument
}

int main()
{
    std::string str = "hello";

    bar(str);                    // OK: U = std::string&,  u is an lvalue reference
    bar(std::string("world"));   // OK: U = std::string,   u is an rvalue reference
}

Pack / variadic template

The general rule: when declaring a pack, ... goes to the left of the name; when expanding a pack, ... goes to the right of the pattern.

template <typename... P>                 // ① declare a type pack P
void emplace(P &&...args)                // ② declare a function parameter pack args, with type pattern P&&
    noexcept(std::is_nothrow_constructible_v<T, P &&...>)  // ③ expand the type pack
{
    new (...) T(std::forward<P>(args)...);  // ④ expand an expression pack
}

Where you put ... determines the scope of the pattern, which is the most common source of mistakes:

f(g(args)...);   // → f(g(a1), g(a2), g(a3))   call g on each argument
f(g(args...));   // → f(g(a1, a2, a3))         pass all arguments to one g call

Type traits

1. Whether T can be constructed at all: static_assert(std::is_constructible_v<T, P&&...>). This is a hard compile-time requirement. If T can’t be constructed from these arguments, compilation stops with a readable error message, instead of a long template error pointing at the placement-new line.

2. Whether that construction can throw (conditional noexcept): noexcept(std::is_nothrow_constructible_v<T, P&&...>).

Why you can’t keep just one

“Constructible” and “nothrow-constructible” are different sets; the second is a subset of the first. For example:

std::string s("hello");   // constructible from const char*, but may throw std::bad_alloc

For T = std::string, P = const char*:

• is_constructible_v is true

• is_nothrow_constructible_v is false

Memory order

const size_t write_idx = write_idx_.load(std::memory_order_relaxed);

write_idx_ is only written by the producer core, so its load doesn’t need a fence to prevent reordering.

while (next_write_idx == cached_read_idx_) [[unlikely]] {
  cached_read_idx_ = read_idx_.load(std::memory_order_acquire);
}

read_idx_ is updated by the consumer thread/core. We need the acquire memory order to build the synchronizes-with relationship with the consumer’s release store, so that the consumer has finished reading and destroying the element in a slot before the producer overwrites it.

write_idx_.store(next_write_idx, std::memory_order_release);

write_idx_ needs to be read on the consumer’s core. Releasing it builds the synchronizes-with relationship between the threads, so the constructed element is visible before the new index is.

Consumer’s functions

Below is a usage example on the consumer’s side:

while (q.front()) {
  std::cout << *q.front() << std::endl;
  q.pop();
}

There are two functions on the consumer’s side: front() and pop().

// non-blocking function
  T* front() noexcept {
    const size_t read_idx = read_idx_.load(std::memory_order_relaxed);
    if (read_idx == cached_write_idx_) [[unlikely]] {
      cached_write_idx_ =  write_idx_.load(std::memory_order_acquire);
      if (read_idx == cached_write_idx_) {
        return nullptr;
      }
    }
    return &slot_[kPadding + read_idx];
  }

  void pop() noexcept {
    const size_t read_idx = read_idx_.load(std::memory_order_relaxed);
    // emptiness has already been checked by front()
    assert(write_idx_.load(std::memory_order_acquire) != read_idx &&
           "Can only call pop() after front() has returned a non-nullptr");
    slot_[kPadding + read_idx].~T();
    size_t next_read_idx = read_idx + 1;
    if (next_read_idx == capacity_) {
      next_read_idx = 0;
    }
    read_idx_.store(next_read_idx, std::memory_order_release);
  }

Memory order

read_idx_ is only written by the consumer thread, so its load can be std::memory_order_relaxed.

The std::memory_order_acquire load of write_idx_ pairs with the std::memory_order_release store in the producer thread.

The benefit of using noexcept

Landing pads disappear

https://godbolt.org/z/PnWdeG4YK

Generic code can choose faster algorithms

This is the big one. Library and generic code query noexcept at compile time and pick a different strategy:

if constexpr (noexcept(q.emplace(std::declval<Args>()...))) {
    // fast path: no need for rollback / backup copies
} else {
    // safe path: extra work to keep the strong exception guarantee
}

The classic example is std::vector reallocation: it moves elements into the new buffer only if the move constructor is noexcept; otherwise it copies them, because a throw halfway through a move would leave both buffers damaged. The same idea applies to anything built on top of your queue, like a wrapper that batches items, a container of queues, or code that uses std::move_if_noexcept. Without the noexcept specification, all of these would have to assume the worst and take the slow path.

This is exactly why the specification is conditional here: for T = int, callers get the “can’t throw” fast path; for T = std::string, they get an honest “may throw” and stay correct.

[[likely]]

https://godbolt.org/z/rG3qq6c8G

int fast(int);   // defined elsewhere
int slow(int);   // defined elsewhere

int hint_unlikely(int x) {
    int r;
    if (x < 0) [[unlikely]] r = slow(x);
    else                    r = fast(x);
    return r + 1;
}

int hint_likely(int x) {
    int r;
    if (x < 0) [[likely]] r = slow(x);
    else                  r = fast(x);
    return r + 1;
}

hint_unlikely(int):
        push    rax
        test    edi, edi
        js      .LBB0_1
        call    fast(int)@PLT
.LBB0_3:
        inc     eax
        pop     rcx
        ret
.LBB0_1:
        call    slow(int)@PLT
        jmp     .LBB0_3

hint_likely(int):
        push    rax
        test    edi, edi
        jns     .LBB1_2
        call    slow(int)@PLT
.LBB1_3:
        inc     eax
        pop     rcx
        ret
.LBB1_2:
        call    fast(int)@PLT
        jmp     .LBB1_3

What the hint actually changed:

The compiler puts the path you said is likely right after the branch, and moves the other one away. This helps in a few ways:

• No taken branch on the hot path. The common case runs straight down: test, not-taken branch, call, inc, ret. Taken jumps cost a bit more in the CPU front end.
• Better instruction-cache use. Hot code is packed together, and cold code sits elsewhere.
• Static prediction. Some CPUs, when they have no branch history, guess that forward branches are not taken. That guess matches the layout.

Others

~MYSPSC() {
    while (front()) {
      pop();
    }
    std::allocator_traits<AllocatorT>::deallocate(allocator_, slot_,
                                                  capacity_ + 2 * kPadding);
  }

  size_t size() const noexcept {
    std::ptrdiff_t diff =
        static_cast<std::ptrdiff_t>(
            write_idx_.load(std::memory_order_acquire)) -
        static_cast<std::ptrdiff_t>(read_idx_.load(std::memory_order_acquire));
    if (diff < 0) {
      diff += capacity_;
    }
    return diff;
  }