Optimizing a Ring Buffer for Throughput | Erik Rigtorp

Optimizing a ring buffer for throughput

2021-12-13

In this article I will take a look at the classic concurrent ring buffer and how<br>it can be optimized to increase throughput. I will show you how to significantly<br>increase throughput from 5.5M items/s to 112M items/s, beating the<br>Boost and Folly<br>implementations. If you need a ready implementation with these optimizations<br>checkout my SPSCQueue.h library.

The ringer buffer data structure is also referred to as a circular buffer or<br>single producer single consumer (SPSC) queue. It&rsquo;s a wait-free (hence also<br>lock-free) concurrency primitive. It has a lot of uses for example it&rsquo;s used to<br>communicate network packets between NICs and OS drivers and to receive I/O<br>completion events in the recently introduced<br>io_uring asynchronous I/O API.

The classic ring buffer

First let&rsquo;s start by implementing a simple ring buffer. In C++ it can be defined<br>like this:

struct ringbuffer {<br>std::vectorint> data_;<br>alignas(64) std::atomicsize_t> readIdx_{0};<br>alignas(64) std::atomicsize_t> writeIdx_{0};

ringbuffer(size_t capacity) : data_(capacity, 0) {}

In this implementation I chose to allow any queue size as opposed to allowing<br>only sizes that are a power-of-two. This means that at least one queue item is<br>unused in order to disambiguate between the empty queue and full queue state.<br>You can choose to require a power-of-two size to avoid this if memory is at a<br>premium.

Another important thing to note is that read (readIdx_) and write<br>(writeIdx_) indices are aligned to the size of a cache line (alignas(64)).<br>This is done to reduce cache coherency traffic. On AMD64 / x86_64 and ARM a<br>cache line is 64 bytes, on other CPUs you need to adjust to the appropriate<br>alignment, using<br>std::hardware_destructive_interference_size<br>is a good choice if it&rsquo;s available. It can also be interesting to try aligning<br>to a multiple of the cache line size in case adjacent cache lines are being<br>pre-fetched.

This is quite similar to how io_uring defines its ring buffer inside the Linux<br>kernel:

struct io_uring {<br>u32 head ____cacheline_aligned_in_smp;<br>u32 tail ____cacheline_aligned_in_smp;<br>};

boost::lockfree::spsc<br>also defines it&rsquo;s ring buffer in pretty much the same way.

We can now implement the push (or write) operation:

bool push(int val) {<br>auto const writeIdx = writeIdx_.load(std::memory_order_relaxed);<br>auto nextWriteIdx = writeIdx + 1;<br>if (nextWriteIdx == data_.size()) {<br>nextWriteIdx = 0;<br>if (nextWriteIdx == readIdx_.load(std::memory_order_acquire)) {<br>return false;<br>data_[writeIdx] = val;<br>writeIdx_.store(nextWriteIdx, std::memory_order_release);<br>return true;

Note how one item is left unused to indicate that the queue is full, when<br>writeIdx_ is one item behind readIdx_ the queue is full.

Next we implement the pop (or read) operation:

bool pop(int &val) {<br>auto const readIdx = readIdx_.load(std::memory_order_relaxed);<br>if (readIdx == writeIdx_.load(std::memory_order_acquire)) {<br>return false;<br>val = data_[readIdx];<br>auto nextReadIdx = readIdx + 1;<br>if (nextReadIdx == data_.size()) {<br>nextReadIdx = 0;<br>readIdx_.store(nextReadIdx, std::memory_order_release);<br>return true;

Again note that readIdx_ == writeIdx_ indicates that the queue is empty.

I chose a very small item size (sizeof(int) == 4) since for large item sizes<br>the performance will be dominated by the memory copying of the items and the<br>goal is not to measure the performance of memcpy(). This of course also means<br>that if you have large items you don&rsquo;t have much to gain from optimizing your<br>ring buffer.

Now lets analyze the performance of this queue. I wrote a simple benchmark<br>ringbuffer.cpp that pushes 100M items between 2 threads<br>through a ring buffer of size 100k. Measuring how long it takes until the reader<br>thread has read all items. Compile ringbuffer.cpp as<br>follows:

g++ -Wall -O3 -march=native -std=c++20 ringbuffer.cpp

I ran this on a AMD Ryzen 9 3900X 12-Core Processor<br>placing the two threads on different chiplets / core complexes (CCX):

$ perf stat -e cache-misses,cache-references,l2_request_g1.change_to_x ./a.out 1 11<br>5513850 ops/s

Performance counter stats for './a.out 1 11':

349,857,603 cache-misses:u # 91.228 % of all cache refs<br>383,497,078 cache-references:u<br>6,673,242 l2_request_g1.change_to_x:u

18.137421039 seconds time elapsed

36.140630000 seconds user<br>0.002986000 seconds sys

We see here that we achieved a throughput of 5.5M items per second. This is in<br>line with the performance you will see from libraries such as<br>boost::lockfree::spsc<br>and<br>folly::ProducerConsumerQueue.<br>The number of cache misses (~300M) seems to be proportional (3x) to the number<br>of items (100M) that were processed.

The optimized ring buffer

Why do we have 3 cache misses per read-write pair? Consider a read operation:<br>the read index needs to be updated and thus that cache line is loaded into the<br>L1 cache in exclusive state (see MESI<br>protocol). The write index...