In the , we solved the physical bottlenecks of traditional queues by eliminating data movement. By bending a contiguous array into a circle and manipulating Head and Tail indices, we built a fast, zero-allocation data pipeline.

But our implementation had a serious limitation: it was only safe if executed on a single thread.

When we use queues for data flow, we are almost always moving data between independent systems running on different CPU cores. For example, a dedicated networking thread fetches packets from a socket, and a dedicated simulation thread reads those packets to update the game state.

If we simply share our standard RingBuffer between two threads, both threads will attempt to read and write to the same memory addresses simultaneously, resulting in torn data, corrupted indices, and an inevitable crash.

The instinctual solution is to wrap the queue in a std::mutex. But as we learned in our , relying on the operating system to put threads to sleep creates huge latency spikes. If our audio thread gets put to sleep because the network thread is holding the lock, our users will hear a glaring audio pop.

In this lesson, we will rebuild our ring buffer from the previous lesson into a Single-Producer Single-Consumer (SPSC) Lock-Free Queue. We will use raw silicon mechanics to move data safely across CPU cores without ever triggering an OS context switch.

The Two-Core Pipeline

An SPSC architecture is one of the simplest and most useful concurrency patterns to implement. It allows us to easily and safely split work across two threads, each assigned to a specific role:

The Producer thread is the only thing allowed to write/push payload data, and it is the only thing allowed to update the Tail index.
The Consumer thread is the only thing allowed to read/pop the payload data, and it is the only thing allowed to update the Head index.

If we strictly follow these rules, we do not need complex compare_exchange_weak() (CAS) loops.

We'll implement a more complex Multiple-Producer Multiple-Consumer (MPMC) queue in the next lesson that does use CAS, but for now, to safely share the Head and Tail across two cores, we just need to upgrade them from standard integers like size_t to atomics like std::atomic<size_t>.

Other than that key difference, the member variables we'll need and the constructor are identical to the RingBuffer from the previous lesson:

dsa_core/include/dsa/SpscQueue.h

1#pragma once
2#include <vector>
3#include <cstdint>
4#include <bit>
5#include <stdexcept>
6#include <atomic> 
7
8template <typename T>
9class SpscQueue {
10private:
11  std::vector<T> Buffer;
12  size_t Capacity;
13  size_t Mask;
14
15  std::atomic<size_t> Head{0}; 
16  std::atomic<size_t> Tail{0}; 
17  
18public:
19  SpscQueue(size_t RequestedCapacity) {
20    if (!std::has_single_bit(RequestedCapacity)) {
21      throw std::invalid_argument(
22        "Capacity must be a power of 2"
23      );
24    }
25    Capacity = RequestedCapacity;
26    Mask = Capacity - 1;
27    Buffer.resize(Capacity);
28  }
29};

This code is thread-safe, but this memory layout will introduce a notable performance bottleneck. In our , we introduced the silent performance killer known as false sharing.

The CPU loads memory into its L1 cache in chunks called cache lines, which are 64 bytes on most modern systems (or 128 bytes on Apple Silicon). Because Head and Tail are declared right next to each other, they will almost certainly be packed into the same physical cache line, meaning our two cores will try to share the same block of memory.

Every time a core updates the cache line, it needs to notify the other core that its copy is now stale and invalid. This constant fight over the same cache line causes pipeline stalls and saturates the internal memory bus with these invalidation messages. This is called cache ping-pong, and it massively degrades performance.

Padding

To fix this, we force the compiler to inject dead padding bytes between our atomics, spacing them out enough to guarantee they land on separate physical cache lines.

We can do this using the alignas keyword combined with the: std::hardware_destructive_interference_size constant. This constant queries the target CPU architecture and returns the exact cache line size required to prevent false sharing:

dsa_core/include/dsa/SpscQueue.h

1// ...
2// for std::hardware_destructive_interference_size
3#include <new> 
4
5template <typename T>
6class SpscQueue {
7private:
8  std::vector<T> Buffer;
9  size_t Capacity;
10  size_t Mask;
11  
12  // Extract the exact cache line size for
13  // the target machine
14  static constexpr size_t CacheLineSize = 
15    std::hardware_destructive_interference_size; 
16
17  // Force Head to the start of a fresh cache line
18  std::atomic<size_t> Head{0}; 
19  alignas(CacheLineSize) std::atomic<size_t> Head{0}; 
20
21  // Force Tail to the start of the NEXT cache line
22  std::atomic<size_t> Tail{0}; 
23  alignas(CacheLineSize) std::atomic<size_t> Tail{0}; 
24
25  // ...
26};

Core A (running the producer) can now take exclusive ownership of the cache line containing the Tail variable, never to be harassed by another core wanting to share it. Meanwhile, Core B (running the consumer) gets the Head cache line all to itself.

The Synchronization Contract

With our physical layout secured, we can implement the logic. We need to translate our single-threaded Push() and Pop() from the previous lesson into a lock-free Publisher-Consumer contract. Now that Head and Tail are atomics, we can do this using the load() and store() methods provided by the std::atomic API that .

We do that below, but first, let's also review the we want to use when loading and storing these values. By default, load() and store() enforces sequential consistency, represented in the standard library as std::memory_order_seq_cst. This works, but forces the compiler will inject full memory fences that flush the entire CPU pipeline on every operation, reducing performance.

We know how our Head and Tail will be used, and we know that we'll be enforcing the SPSC restriction, so we can interject here and improve upon the default. By relaxing the memory ordering constraints to only what we need, we give the CPU's out-of-order execution engine more room to optimize and improve our system's performance.

Implementing `Push()`

When the producer calls Push(), three things must happen:

It must read the consumer's Head to ensure the buffer isn't full.
It must write the payload data to the Buffer array in RAM.
It must update the Tail to publish the new data.

If the CPU or the compiler reorders step 3 to happen before step 2, the Tail increments before the payload actually reaches RAM. The consumer might wake up, see the new Tail, read the array, and consume uninitialized garbage.

We should therefore use a release fence when storing the Tail. This guarantees that all memory writes (our payload) sitting physically above the store() instruction are committed to RAM before the index is updated:

dsa_core/include/dsa/SpscQueue.h

1// ...
2
3template <typename T>
4class SpscQueue {
5  // ...
6
7public:
8  // ...
9  
10  // This is called ONLY by the Producer thread
11  bool Push(const T& Value) {
12    // Because WE (the producer) own the Tail, we
13    // are the only thread modifying it. Therefore,
14    // reading it can be relaxed
15    size_t CurrentTail = Tail.load(
16      std::memory_order_relaxed
17    );
18
19    // We do NOT own the Head. We must acquire the
20    // latest value written by the Consumer to ensure
21    // we don't overwrite a payload they are currently
22    // reading
23    size_t CurrentHead = Head.load(
24      std::memory_order_acquire
25    );
26
27    // Check if the queue is full (sacrificing 1 slot
28    // as before)
29    if (((CurrentTail + 1) & Mask) == CurrentHead) {
30      return false;
31    }
32
33    // Write the payload to standard, non-atomic
34    // RAM.  We (the producer) are the only thing
35    // allowed to do this
36    Buffer[CurrentTail] = Value;
37
38    // Publish the Tail
39    // The release fence ensures the payload write
40    // is fully visible to other threads before the
41    // Tail index is updated
42    Tail.store(
43      (CurrentTail + 1) & Mask,
44      std::memory_order_release
45    );
46
47    return true;
48  }
49};

Notice the care taken with our load() operations. Because this is an SPSC queue, the single producer thread has exclusive rights to update the Tail. It can read its own variable using memory_order_relaxed, which translates to raw assembly with zero fence overhead.

Implementing `Pop()`

The consumer executing Pop() sits on the other side of this contract.

It must check the Tail to ensure there is data to read. It must use an acquire fence to synchronize with the producer's release. This guarantees that if the consumer sees the new Tail, the CPU is forbidden from reading the payload data from cache until the producer's payload writes have fully traversed the memory bus.

dsa_core/include/dsa/SpscQueue.h

1// ...
2
3template <typename T>
4class SpscQueue {
5  // ...
6
7public:
8  // ...
9  
10  // This is called ONLY by the Consumer thread
11  bool Pop(T& OutValue) {
12    // We (the consumer) own the Head, so reading
13    // it is totally safe and relaxed
14    size_t CurrentHead = Head.load(
15      std::memory_order_relaxed
16    );
17
18    // We do NOT own the Tail. We must acquire
19    // it to synchronize with the Producer's
20    // release fence
21    size_t CurrentTail = Tail.load(
22      std::memory_order_acquire
23    );
24
25    // Check if the queue is empty
26    if (CurrentHead == CurrentTail) {
27      return false;
28    }
29
30    // Read the payload from standard RAM
31    OutValue = Buffer[CurrentHead];
32
33    // Publish the Head
34    // The release fence guarantees our read
35    // is fully complete before the Producer
36    // is allowed to overwrite this slot
37    Head.store(
38      (CurrentHead + 1) & Mask,
39      std::memory_order_release
40    );
41
42    return true;
43  }
44};

Let's walk through the sequence of a producer pushing data to the queue, and the consumer then popping that data:

Usage Example

We can now safely split our production and consumption of data across two cores. Below, we have a thread producing audio samples, another thread consuming the samples, and our lock-free SpscQueue acting as a buffer between them.

This is almost identical to the usage example in the previous lesson - we've just replaced our RingBuffer container with our new SpscQueue, and our producer and consumer are now running concurrently, on different threads:

dsa_app/main.cpp

1#include <print> // C++23
2#include <mutex>
3#include <thread>
4
5#include <dsa/RingBuffer.h>
6#include <dsa/SpscQueue.h>
7
8int main() {
9  RingBuffer<int> AudioStream(1024);
10  SpscQueue<int> AudioStream(1024);
11
12  auto audio_producer = [&]() {
13    for (int i = 1; i <= 5; ++i) {
14      std::println("Producing sample {}", i);
15      while (!AudioStream.Push(i)) {}
16    }
17  };
18
19  auto audio_consumer = [&]() {
20    int sample;
21    int count = 0;
22
23    while (count < 5) {
24      if (AudioStream.Pop(sample)) {
25        std::println("Playing sample {}", sample);
26        ++count;
27      }
28    }
29  };
30  
31  audio_producer(); 
32  audio_consumer(); 
33
34  std::thread t1(audio_producer); 
35  std::thread t2(audio_consumer); 
36  t1.join(); 
37  t2.join(); 
38}

1Producing sample 1
2Playing sample 1
3Producing sample 2
4Playing sample 2
5Producing sample 3
6Producing sample 4
7Playing sample 3
8Producing sample 5
9Playing sample 4
10Playing sample 5

Benchmarking

We have successfully built a lock-free pipeline. It requires no OS involvement, no dynamic memory allocation, and isolates cache lines.

Let's pit it against a traditional multithreaded queue. We will wrap the standard library's std::queue in a std::mutex. We will then spawn two asynchronous threads: one pushing 10 million integers, and one pulling 10 million integers:

benchmarks/main.cpp

1#include <benchmark/benchmark.h>
2#include <queue>
3#include <mutex>
4#include <thread>
5#include <dsa/SpscQueue.h>
6
7// A thread-safe wrapper around std::queue
8template <typename T>
9class MutexQueue {
10  std::queue<T> Q;
11  std::mutex Mtx;
12public:
13  void Push(const T& val) {
14    std::lock_guard<std::mutex> lock(Mtx);
15    Q.push(val);
16  }
17  bool Pop(T& out) {
18    std::lock_guard<std::mutex> lock(Mtx);
19    if (Q.empty()) return false;
20    out = Q.front();
21    Q.pop();
22    return true;
23  }
24};
25
26static void BM_MutexQueue(benchmark::State& state) {
27  for (auto _ : state) {
28    MutexQueue<int> MQ;
29
30    auto producer = [&]() {
31      for (int i = 0; i < 10'000'000; ++i) {
32        MQ.Push(i);
33      }
34    };
35
36    auto consumer = [&]() {
37      int count = 0;
38      int val;
39      while (count < 10'000'000) {
40        if (MQ.Pop(val)) {
41          count++;
42          benchmark::DoNotOptimize(val);
43        }
44      }
45    };
46
47    std::thread t1(producer);
48    std::thread t2(consumer);
49    t1.join();
50    t2.join();
51  }
52}
53BENCHMARK(BM_MutexQueue)->Unit(benchmark::kMillisecond);
54
55static void BM_LockFreeSpsc(benchmark::State& state) {
56  for (auto _ : state) {
57    // Capacity must be a power of 2
58    SpscQueue<int> LFQ(1024 * 1024);
59
60    auto producer = [&]() {
61      for (int i = 0; i < 10'000'000; ++i) {
62        // Spin if full
63        while (!LFQ.Push(i)) {}
64      }
65    };
66
67    auto consumer = [&]() {
68      int count = 0;
69      int val;
70      while (count < 10'000'000) {
71        if (LFQ.Pop(val)) {
72          count++;
73          benchmark::DoNotOptimize(val);
74        }
75      }
76    };
77
78    std::thread t1(producer);
79    std::thread t2(consumer);
80    t1.join();
81    t2.join();
82  }
83}
84BENCHMARK(BM_LockFreeSpsc)->Unit(benchmark::kMillisecond);

1-----------------------------------
2Benchmark            Time       CPU
3-----------------------------------
4BM_MutexQueue      441 ms   4.69 ms
5BM_LockFreeSpsc   80.3 ms   1.41 ms

The std::mutex version causes the operating system to constantly intervene. Core A grabs the lock. Core B tries to read, hits the locked mutex, and is forcefully put to sleep by the OS. Core A releases the lock, and the OS burns thousands of cycles waking Core B back up.

Our SpscQueue completely bypasses the operating system. The cores communicate strictly by syncing L1 cache lines over the internal hardware bus via our acquire/release fences. It processes the 10 million items over 5 times faster in these tests.

Preview: MPMC Queues

Our SpcsQueue is fast, but what happens if we break the SPSC rule? What if we have a pool of three network threads, and they are all trying to Push() packets into our queue simultaneously?

Let's walk through the exact hardware execution path if Thread 1 and Thread 2 both call Push() at the same nanosecond:

The queue has lost data, but it doesn't know it. The Tail successfully incremented from 4 to 5, so the consumer will happily read the corrupted payload and continue, oblivious to the fact that a packet was permanently erased.

To build a Multi-Producer Multi-Consumer (MPMC) queue, standard atomic load() and store() operations are no longer sufficient. If multiple threads are fighting over the same index, they must "claim" the index before they are allowed to write to the payload array.

We will explore how to solve this exact collision using Compare-and-Swap (CAS) loops and Sequence Tickets in the next lesson.

Complete Code

Here is the complete implementation of our thread-safe, lock-free SpscQueue:

Files

dsa_core

dsa_app

Select a file to view its content

Summary

In this lesson, we created a lock-free pipeline to safely stream data across independent CPU cores.

We introduced the single-producer single-consumer model, which prevents multiple threads from attempting to modify the same index at the same time.
We defeated false sharing by padding our Head and Tail atomics using alignas, isolating them onto separate physical cache lines to prevent MESI invalidation ping pong.
We improved the publisher-consumer contract using half-fences (acquire and release) to guarantee our memory writes were fully visible without stalling the pipeline with full seq_cst flushes.
We acknowledged the problem with this implementation when multiple producers or multiple consumers try to use our ring buffer concurrently

SPSC Lock-Free Queues

The Two-Core Pipeline

dsa_core/include/dsa/SpscQueue.h

Padding

dsa_core/include/dsa/SpscQueue.h

The Synchronization Contract

Implementing `Push()`

dsa_core/include/dsa/SpscQueue.h

Implementing `Pop()`

dsa_core/include/dsa/SpscQueue.h

Usage Example

dsa_app/main.cpp

Benchmarking

benchmarks/main.cpp

Preview: MPMC Queues

Complete Code

Files

Summary

Practical DSA

SPSC Lock-Free Queues

The Two-Core Pipeline

dsa_core/include/dsa/SpscQueue.h

False Sharing

Padding

dsa_core/include/dsa/SpscQueue.h

The Synchronization Contract

Implementing Push()

dsa_core/include/dsa/SpscQueue.h

Implementing Pop()

dsa_core/include/dsa/SpscQueue.h

Usage Example

dsa_app/main.cpp

Benchmarking

benchmarks/main.cpp

Preview: MPMC Queues

Complete Code

Files

Summary

Implementing `Push()`

Implementing `Pop()`