Ring Buffers

In the previous lesson , we explored how decoupling producers and consumers allows data to flow efficiently through our applications. We looked at standard library tools like std::queue and saw how they act as adapters over underlying containers like std::deque.

However, we also exposed the physical hardware limitations of these standard containers. Arrays like std::vector force catastrophic memory shifts when pulling data from the front. Chunked arrays like std::deque solve the shifting problem, but still require dynamic allocations when chunks fill up.

We can solve this problem by changing our perspective. Instead of deleting things and moving data through the queue, we can keep the queue relatively static and instead move pointers over the data.

We start by pre-allocating a single, contiguous array. We will never resize this array, guaranteeing zero dynamic allocations during runtime.

We then establish two integer indices: a Head and a Tail. The Tail represents where we write new data. The Head represents where we read existing data.

When the program starts, both the Head and the Tail sit at index 0. When a producer wants to push data to the queue, it writes the payload into the array at the Tail index, and then increments the Tail by 1.

When a consumer wants to pop the next element from the queue, it looks at the Head index. It reads the payload, processes it, and then increments the Head by 1.

This achieves $O(1)$ reads and $O(1)$ writes, first-in-first-out ordering, zero allocations, and stable data positioning. But what happens when we reach the end of our array and run out of space to write?

Bending the Array

If our array has a capacity of 8, and our Tail index reaches 8, we are out of space. We cannot write any more data, even if the consumer has already processed the data at the indices 0, 1, and 2.

The solution is to bend the array into an infinite circle.

When the Tail or the Head increments past the physical boundary of the array, we snap the index back to 0. The pointers simply wrap around and begin overwriting the stale, already-consumed memory at the start of the array.

Because the pointers endlessly chase each other in a circle, the data structure is capable of moving an infinite amount of streaming data through a small, fixed-size physical footprint.

In this design, we also keep at least one slot free at all times. This means the Tail cannot "catch up" to the Head, except when the buffer is empty.

We'll explain why this is important later in the lesson, but the immediate implication is that it reduces our capacity by 1. For example, if we were to use an 8-slot array, our buffer could have up to 7 items waiting to be processed.

To implement this wrap-around behavior, we apply mathematical bounds to our indices every time we increment them. The standard, textbook way to implement wrap-around behavior is to use the modulo operator (%).

The modulo operator divides the left operand by the right operand and returns the remainder. If our Capacity is 8, using i % 8 whilst incrementing i gives us the exact wrap-around pattern we want:

1// Capacity = 8
2
3// Incrementing normally
40 % 8 // 0
51 % 8 // 1
6      // ...
76 % 8 // 6
87 % 8 // 7
9
10// The Wrap-Around
118 % 8 // 0 
129 % 8 // 1

However, the modulo operator is implemented in silicon using integer division instructions. Integer division is one of the most expensive fundamental operations the Arithmetic Logic Unit (ALU) can perform.

If we are pushing 10 million network packets per second through our buffer, forcing the ALU to perform 10 million division operations simply to wrap an index is an excessive waste.

The Bitwise Mask

We can eliminate this division penalty by using faster bitwise logic . To make this work, we first need to enforce a structural rule: the capacity of our ring buffer must always be a power of 2 (e.g., 8, 16, 256, 1024). As we saw previously, powers of 2 have a useful binary property - they have only a single bit set to 1.

For example, if our capacity is 8, its binary representation is 00001000. If we subtract 1 from this capacity, we get 7, which has the binary representation 00000111. Notice that subtracting 1 from 8 has perfectly flipped all the bits to the right from 0 to 1.

This is true for any power of two. If we set the capacity to 16 (00010000) and subtract 1, we get 15 (00001111).

By using this Capacity - 1 value as a mask, the bitwise AND operator & replicates the same pattern as the modulo operator, but at a fraction of the cost:

1// Capacity = 8 (00001000), Mask = 7 (00000111)
2
3// Incrementing normally
40 & 7 // 000 & 111 = 000 (0)
51 & 7 // 001 & 111 = 001 (1)
6      // ...
76 & 7 // 110 & 111 = 110 (6)
87 & 7 // 111 & 111 = 111 (7)
9
10// The Wrap-Around
118 & 7 // 1000 & 0111 = 0000 (0) 
129 & 7 // 1001 & 0111 = 0001 (1)

A bitwise AND executes in a single CPU cycle, whilst integer division generally requires at least 10, and even more for large types like size_t.

Let's begin implementing our RingBuffer. We will use a generic template parameter T for the payload type.

Because we require the capacity to be a power of 2 to support our bitwise mask optimization, we will use the std::has_single_bit function from the <bit> library to validate the user's requested capacity during construction:

1#pragma once
2#include <vector>
3#include <cstdint>
4#include <bit>
5#include <stdexcept>
6
7template <typename T>
8class RingBuffer {
9private:
10  std::vector<T> Buffer;
11  size_t Capacity;
12  size_t Mask;
13
14  // Both pointers start at 0
15  size_t Head{0};
16  size_t Tail{0};
17
18public:
19  RingBuffer(size_t RequestedCapacity) {
20    // Enforce the power-of-2 rule
21    if (!std::has_single_bit(RequestedCapacity)) {
22      throw std::invalid_argument(
23        "Capacity must be a power of 2"
24      );
25    }
26
27    Capacity = RequestedCapacity;
28
29    // Pre-calculate the bitmask
30    Mask = Capacity - 1;
31
32    // Pre-allocate the physical memory once
33    Buffer.resize(Capacity);
34  }
35};

As with all high-performance systems, we do the heavy lifting of allocating the std::vector exactly once in the constructor. The structure will never grow, and it will never trigger a reallocation spike.

Before we can implement Push() and Pop(), we need to solve an important logical puzzle of a ring buffer: how do we know if it is full or empty?

If the queue is empty, the Head and Tail point to the same index. The producer hasn't written anything new, and the consumer has caught up completely.

1bool IsEmpty() const {
2  return Head == Tail;
3}

But what happens when the queue is full? Imagine a buffer with a capacity of 8. The Head is at 0. The producer writes 8 items, wrapping the Tail all the way around the circle until it lands back on 0.

Now, the Head and Tail are pointing to the same index again. Because both the "Empty" state and the "100% Full" state result in Head == Tail, we cannot determine if there are 0 items available to read or 8 items available to read.

The "Always One Open" Strategy

There are two main ways to solve this ambiguity. The first approach is to add a Size counter to our class. When we push, we Size++. When we pop, we Size--. We can then just ask if (Size == 0) to determine if the buffer is empty, or if (Size == Capacity) to determine if it's full.

While this works in a single-threaded environment, it introduces a severe bottleneck when multithreading. As we will see in the next lesson, if one CPU core is pushing and another CPU core is popping, forcing both cores to constantly update the same Size integer creates massive cache-line contention, crippling our throughput.

The second approach is to deliberately sacrifice exactly one slot of physical memory. We do this by establishing a simple rule: the Tail is never allowed to catch up to the Head. If advancing the Tail by 1 would cause it to collide with the Head, we declare the buffer "Full" and refuse the write.

1bool IsFull() const {
2  // Check if the next theoretical step of the Tail
3  // (wrapped by our mask) hits the Head
4  return ((Tail + 1) & Mask) == Head;
5}

By sacrificing a single payload slot, we eliminate the ambiguity without the performance cost and thread contention of maintaining a Size variable. The Head == Tail state will always mean the buffer is empty.

We can still provide a GetSize() function if doing so would be useful in its own right. We would use arithmetic to track how far the Head is from the Tail, remembering that the tail may have wrapped around to be physically behind the head:

1size_t GetSize() const {
2  if (Tail >= Head) {
3    // The Tail is physically ahead of (or equal to) the Head
4    return Tail - Head;
5  } else {
6    // The Tail has wrapped around and is behind the Head
7    return Capacity - (Head - Tail);
8  }
9}

Implementing Push()

With our state checks in place, let's implement the core logic.

When pushing, we ensure the buffer is not full, write the payload to the Tail index, and increment the Tail using our bitmask. We return true if the push was successful, or false if it failed because the buffer is full:

1// ...
2
3template <typename T>
4class RingBuffer {
5  // ...
6
7public:
8  // ...
9
10  bool IsEmpty() const {
11    return Head == Tail;
12  }
13
14  bool IsFull() const {
15    return ((Tail + 1) & Mask) == Head;
16  }
17
18  bool Push(const T& Value) {
19    // Reject the write if the buffer is full
20    if (IsFull()) {
21      return false;
22    }
23
24    // Write the data to the current tail slot
25    Buffer[Tail] = Value;
26
27    // Advance the tail and wrap it
28    Tail = (Tail + 1) & Mask;
29
30    return true;
31  }
32};

Implementing Pop()

When popping, we ensure the buffer is not empty, read the payload from the Head index, and increment the Head using our bitmask. This function needs to provide two values to its caller - a boolean representing whether the read was successful and a T - the value itself.

We could define a new struct for this return value, or use a templated result type like std::expected which we cover in this lesson

However, to keep things simple, we'll return a bool and ask users to provide a memory address (a T&) of a variable that we will update if our function returns true:

1// ...
2
3template <typename T>
4class RingBuffer {
5  // ...
6
7public:
8  // ...
9
10  bool Pop(T& OutValue) {
11    // Reject the read if the buffer is empty
12    if (IsEmpty()) {
13      return false;
14    }
15
16    // Extract the data from the current head slot
17    OutValue = Buffer[Head];
18
19    // Advance the head and wrap it
20    Head = (Head + 1) & Mask;
21
22    return true;
23  }
24};

Below, we have split our workload across two functions - one for producing audio samples and one for consuming samples, with our RingBuffer between them.

The complex control flow around Push() and Pop() in this simple example is not strictly required, but it demonstrates a common pattern when working with queues in the real world:

• The queue might be full, so the producer keeps calling Push() until a consumer (running in another thread) creates some space by removing and processing one of the existing samples.
• The queue might be empty, so the consumer keeps calling Pop() until a producer (running in another thread) adds something to the buffer for it to work on.

1#include <print> // C++23
2#include <thread>
3#include <dsa/RingBuffer.h>
4
5int main() {
6  RingBuffer<int> AudioStream(1024);
7
8  auto audio_producer = [&]() {
9    // Produce and push 5 samples
10    for (int i = 1; i <= 5; ++i) {
11      std::println("Producing sample {}", i);
12      
13      // Keep trying to push the sample until the buffer
14      // accepts it - that is, until Push returns true)
15      while (!AudioStream.Push(i)) {
16        // Push returned false - buffer is
17        // currently full - try again
18      }
19    }
20  };
21
22  auto audio_consumer = [&]() {
23    int sample;
24    int count = 0;
25    
26    // Keep iterating until the buffer provides 5 samples
27    // - that is, until Pop returns true 5 times
28    while (count < 5) {
29      if (AudioStream.Pop(sample)) {
30        // Pop returned true - process the sample
31        std::println("Playing sample {}", sample);
32        count++;
33      } else {
34        // Pop returned false - buffer is currently
35        // empty - try again
36      }
37    }
38  };
39  
40  audio_producer();
41  audio_consumer();
42
43  return 0;
44}

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

This is sequential for now - we produce all the samples, and then we consume them. But in the next lesson, we'll update our RingBuffer to a thread-safe, lock-free container. This means we can direct two cores at the problem, letting us produce and consume samples concurrently.

We now have a continuous data pipeline that operates with $O(1)$ efficiency, uses no locks, triggers no allocations, and mathematically wraps its pointers in a single CPU cycle. Let's benchmark our circular queue against the standard library's std::queue, which relies on chunked heap allocations.

We will execute a loop that pushes 1,000 elements into each queue, and then pops them back out:

1#include <benchmark/benchmark.h>
2#include <queue>
3#include <dsa/RingBuffer.h>
4
5static void BM_StdQueue_Pipeline(benchmark::State& state) {
6  std::queue<int> pipeline;
7  for (auto _ : state) {
8    // Push 1000 items
9    for (int i = 0; i < 1000; ++i) {
10      pipeline.push(i);
11    }
12    // Pop 1000 items
13    for (int i = 0; i < 1000; ++i) {
14      int val = pipeline.front();
15      pipeline.pop();
16      benchmark::DoNotOptimize(val);
17    }
18  }
19}
20BENCHMARK(BM_StdQueue_Pipeline);
21
22static void BM_RingBuffer_Pipeline(benchmark::State& state) {
23  // Pre-allocate a power-of-2 buffer large enough for our burst
24  RingBuffer<int> pipeline(1024);
25
26  for (auto _ : state) {
27    // Push 1000 items
28    for (int i = 0; i < 1000; ++i) {
29      pipeline.Push(i);
30    }
31    // Pop 1000 items
32    for (int i = 0; i < 1000; ++i) {
33      int val;
34      pipeline.Pop(val);
35      benchmark::DoNotOptimize(val);
36    }
37  }
38}
39BENCHMARK(BM_RingBuffer_Pipeline);

1--------------------------------
2Benchmark                    CPU
3--------------------------------
4BM_StdQueue_Pipeline     3223 ns
5BM_RingBuffer_Pipeline   1765 ns

The std::deque underpinning the std::queue suffers from the overhead of managing its internal memory chunks, checking chunk boundaries, and sporadically calling the OS allocator when it needs more memory.

Our RingBuffer executes purely via index manipulation within a pre-allocated slab. It operates around 2 times faster than std::queue in this scenario, with zero risk of latency spikes caused by the global heap.

Our Push() and Pop() methods are efficient for moving single elements. But in the real world, data rarely arrives one integer at a time. If we are writing an audio driver, the operating system does not hand us one audio sample; it hands us an array of 512 samples. If we receive a UDP network packet, it contains 1,400 bytes of data.

We could loop over these arrays and call Push() 512 times. However, doing so forces the CPU to evaluate the IsFull() boundary check and apply the bitwise mask 512 individual times.

When we are dealing with bulk data, the fastest way to move it is to use the raw memory copy instruction, std::memcpy. This hardware-accelerated instruction can move massive blocks of contiguous memory in a fraction of a microsecond.

To support this, we will write a PushSpan() method. It will accept a std::span, which is a lightweight C++20 view over a contiguous block of data. We'll first calculate how many elements we need to write. This count will either be the size of the input, or the amount of physical space our buffer has available - whichever is smaller:

1// ...
2#include <cstring>  // for std::memcpy
3#include <span>    
4
5template <typename T>
6class RingBuffer {
7  // ...
8
9public:
10  // ...
11
12  // Calculate exactly how many items we can write
13  size_t AvailableWriteSpace() const {
14    if (Tail >= Head) {
15      return Capacity - (Tail - Head) - 1;
16    } else {
17      return (Head - Tail) - 1;
18    }
19  }
20
21  size_t PushSpan(std::span<const T> InputData) {
22    size_t WriteCount = std::min(
23      InputData.size(),
24      AvailableWriteSpace()
25    );
26
27    if (WriteCount == 0) return 0;
28
29    // Copying the data is done in the next section
30  }
31};

The Wrap-Around Split

The challenge with batch copying into a ring buffer is the physical boundary of the array.

If we want to write 10 items, but our Tail is sitting just 4 slots away from the end of the Capacity, we cannot execute a single std::memcpy of 10 items. The copy operation will spill out of our physical array and overwrite adjacent memory, instantly corrupting our application.

We must calculate how much contiguous physical space is remaining between the Tail and the end of the buffer.

If the contiguous space is large enough to hold the entire batch, we perform a single memcpy. If the batch is too large, we must split the write into two parts: one memcpy to fill the remaining space at the end of the array, and a second memcpy to wrap around and write the remaining data at the physical start of the array.

Let's complete our PushSpan() implementation by determining if we need to split the operation:

1// ...
2
3template <typename T>
4class RingBuffer {
5  // ...
6
7public:
8  // ...
9
10  size_t PushSpan(std::span<const T> InputData) {
11    size_t WriteCount = std::min(
12      InputData.size(),
13      AvailableWriteSpace()
14    );
15
16    if (WriteCount == 0) return 0;
17
18    // Calculate how much physical space exists
19    // before the array ends
20    size_t SpaceUntilWrap = Capacity - Tail;
21
22    if (WriteCount <= SpaceUntilWrap) {
23      // Scenario A: The data fits entirely within
24      // the physical bounds. We perform one clean
25      // memory copy
26      std::memcpy(
27        &Buffer[Tail],
28        InputData.data(),
29        WriteCount * sizeof(T)
30      );
31    } else {
32      // Scenario B: The data crosses the wrap boundary
33      // Fill the remaining space at the end of the buffer
34      std::memcpy(
35        &Buffer[Tail],
36        InputData.data(),
37        SpaceUntilWrap * sizeof(T)
38      );
39
40      // Wrap around and write the leftover data at the start
41      size_t Leftover = WriteCount - SpaceUntilWrap;
42      std::memcpy(
43        &Buffer[0],
44        InputData.data() + SpaceUntilWrap,
45        Leftover * sizeof(T)
46      );
47    }
48
49    // Update the Tail in a single operation
50    Tail = (Tail + WriteCount) & Mask;
51
52    return WriteCount;
53  }
54};

By batching our writes, the CPU prefetcher is fully engaged, and we bypass the loop overhead. This technique allows network buffers to swallow massive Ethernet frames essentially instantaneously.

We can implement a highly similar PopSpan() method to allow consumers to extract bulk data with the same dual-memcpy strategy. This is included in the Complete Code section below.

Here is the complete implementation of our high-performance, contiguous RingBuffer, including the bulk-processing PopSpan logic:

In this lesson, we solved the physical bottlenecks of traditional queues by completely eliminating data movement.

1. We bent a contiguous array into a circle to create a ring buffer, achieving zero-allocation, $O(1)$ stream processing where the data sits still and the pointers move.
2. We avoided the heavy CPU penalty of modulo division by enforcing a power-of-2 capacity, unlocking the ultra-fast bitwise mask for instantaneous index wrapping.
3. We solved the Head == Tail full/empty ambiguity by deliberately sacrificing one memory slot, eliminating the need for a highly contended Size counter.
4. We implemented batch processing via memcpy, splitting our writes across the physical array bounds to achieve maximum hardware throughput.

By removing the centralized Size counter, we have established a mechanical design where the producer thread only ever modifies the Tail index, and the consumer thread only ever modifies the Head index.

This separation is extremely helpful when we need to implement lock-free multithreading, which we will do in the next lesson by upgrading our buffer to support SPSC (Single-Producer Single-Consumer) concurrency.