From e74880552a4f332e3b50967469bad80751e0b0b3 Mon Sep 17 00:00:00 2001 From: Dmitry Ilvokhin Date: Thu, 8 Oct 2026 14:59:19 +0000 Subject: Add RingBuffer benchmark I stumbled across a curious blog post by Erik Rigtorp and decided to verify results myself. https://rigtorp.se/ringbuffer/ On AMD Ryzen 7 8700G I got around following 50% speedup for cached version with all member fields alignment. $ bin/ring_buffer --benchmark_min_time=2s ------------------------------------------------------ Benchmark Time ------------------------------------------------------ BM_PushPopNoAlign/threads:2 7.66 ns BM_PushPopCachelineAlign/threads:2 9.57 ns BM_PushPopCachedNoAlign/threads:2 6.82 ns BM_PushPopCachedCachelineAlign/threads:2 5.07 ns As a side note, it is interesting to see writer/reader indexes alignment for simple implementation is a regression, not an improvement on this hardware. This fact is mentioned in Low Latency Trading Insights by Henrique Bucher. The explanation from the book is following: in case when L3 is shared between cores there is not much false sharing going on, but there are more L3 fetches. This explanation sounds plausible and I also was able to verify it experimentally. $ perf stat \ -e l1-dcache-loads \ -e l2_cache_req_stat.dc_access_in_l2 \ -e ls_dmnd_fills_from_sys.local_ccx \ bin/ring_buffer \ --benchmark_min_time=100000000x \ --benchmark_filter=BM_PushPopNoAlign ------------------------------------------------------ Benchmark Time ------------------------------------------------------ BM_PushPopNoAlign/threads:2 7.47 ns ------------------------------------------------------ Value Counter ------------------------------------------------------ 2707584731 l1-dcache-loads:u 119412724 l2_cache_req_stat.dc_access_in_l2:u 75608672 ls_dmnd_fills_from_sys.local_ccx:u $ perf stat \ -e l1-dcache-loads \ -e l2_cache_req_stat.dc_access_in_l2 \ -e ls_dmnd_fills_from_sys.local_ccx \ bin/ring_buffer \ --benchmark_min_time=100000000x \ --benchmark_filter=BM_PushPopCachelineAlign ------------------------------------------------------ Benchmark Time ------------------------------------------------------ BM_PushPopCachelineAlign/threads:2 9.50 ns ------------------------------------------------------ Value Counter ------------------------------------------------------ 4066582808 l1-dcache-loads:u 216776537 l2_cache_req_stat.dc_access_in_l2:u 117305061 ls_dmnd_fills_from_sys.local_ccx:u ------------------------------------------------------ Counter Delta ------------------------------------------------------ l1-dcache-loads +33.4% l2_cache_req_stat.dc_access_in_l2 +44.9% ls_dmnd_fills_from_sys.local_ccx +35.5% Same hypothesis is also confirmed, when benchmark is pinned to the cores. When threads are running on diferent physical cores there is not a lot of difference in time. $ taskset --cpu-list 0,1 \ bin/ring_buffer \ --benchmark_min_time=3s ------------------------------------------------------ Benchmark Time ------------------------------------------------------ BM_PushPopNoAlign/threads:2 7.76 ns BM_PushPopCachelineAlign/threads:2 7.64 ns But when threads are running on the same physical core (hyperhthreading) there a noticable slowdown due more cache fetches from all levels. $ taskset --cpu-list 0,8 \ bin/ring_buffer \ --benchmark_min_time=3s ------------------------------------------------------ Benchmark Time ------------------------------------------------------ BM_PushPopNoAlign/threads:2 3.42 ns BM_PushPopCachelineAlign/threads:2 5.13 ns On Apple M4 difference is much more noticeable. ------------------------------------------------------ Benchmark Time ------------------------------------------------------ BM_PushPopNoAlign/threads:2 50.7 ns BM_PushPopCachelineAlign/threads:2 43.7 ns BM_PushPopCachedNoAlign/threads:2 7.76 ns BM_PushPopCachedCachelineAlign/threads:2 2.04 ns Unfortunately, there are much less observability tools available for macOS, so I was unable to dig deeper into results. --- src/ring_buffer.cpp | 135 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 135 insertions(+) create mode 100644 src/ring_buffer.cpp (limited to 'src') diff --git a/src/ring_buffer.cpp b/src/ring_buffer.cpp new file mode 100644 index 0000000..c62ce63 --- /dev/null +++ b/src/ring_buffer.cpp @@ -0,0 +1,135 @@ +#include +#include +#include +#include + +#include + +enum class Alignment: std::size_t { + Default = alignof(std::atomic), + Cacheline = std::hardware_destructive_interference_size +}; + +template +class RingBuffer { +public: + __attribute__((noinline)) bool Push(const T& value) { + const std::size_t writer = writer_.load(std::memory_order_relaxed); + const std::size_t next_writer = (writer + 1) % Size; + + if (next_writer == reader_.load(std::memory_order_acquire)) + return false; + + buffer_[writer] = value; + writer_.store(next_writer, std::memory_order_release); + return true; + } + + __attribute__((noinline)) bool Pop(T& value) { + const std::size_t reader = reader_.load(std::memory_order_relaxed); + const std::size_t next_reader = (reader + 1) % Size; + + if (reader == writer_.load(std::memory_order_acquire)) + return false; + + value = buffer_[reader]; + reader_.store(next_reader, std::memory_order_release); + return true; + } + +private: + alignas(Align) std::atomic writer_{0}; + alignas(Align) std::atomic reader_{0}; + alignas(Align) std::array buffer_; +}; + +// See: https://rigtorp.se/ringbuffer +template +class CachedRingBuffer { +public: + __attribute__((noinline)) bool Push(const T& value) { + const std::size_t writer = writer_.load(std::memory_order_relaxed); + const std::size_t next_writer = (writer + 1) % Size; + if (next_writer == cached_reader_) { + cached_reader_ = reader_.load(std::memory_order_acquire); + if (next_writer == cached_reader_) + return false; + } + + buffer_[writer] = value; + writer_.store(next_writer, std::memory_order_release); + return true; + } + + __attribute__((noinline)) bool Pop(T& value) { + const std::size_t reader = reader_.load(std::memory_order_relaxed); + const std::size_t next_reader = (reader + 1) % Size; + if (reader == cached_writer_) { + cached_writer_ = writer_.load(std::memory_order_acquire); + if (reader == cached_writer_) + return false; + } + + value = buffer_[reader]; + reader_.store(next_reader, std::memory_order_release); + return true; + } + +private: + alignas(Align) std::atomic writer_{0}; + alignas(Align) std::size_t cached_reader_{0}; + + alignas(Align) std::atomic reader_{0}; + alignas(Align) std::size_t cached_writer_{0}; + + alignas(Align) std::array buffer_; +}; + +static bool IsPusherThread(benchmark::State& state) { + return state.thread_index() == 0; +} + +template +static void DoPushPop(benchmark::State& state) { + // Make ring_buffer static to share it between threads. + static RingBuffer ring_buffer; + + if (IsPusherThread(state)) { + int x = 0; + for (auto _ : state) { + while (!ring_buffer.Push(x)) + ++x; + } + } else { + for (int x = 0; auto _ : state) { + while (!ring_buffer.Pop(x)) {} + benchmark::DoNotOptimize(x); + } + } +} + +static void BM_PushPopNoAlign(benchmark::State& state) { + DoPushPop>(state); +} +BENCHMARK(BM_PushPopNoAlign)->Threads(2); + +static void BM_PushPopCachelineAlign(benchmark::State& state) { + DoPushPop>(state); +} +BENCHMARK(BM_PushPopCachelineAlign)->Threads(2); + +static void BM_PushPopCachedNoAlign(benchmark::State& state) { + DoPushPop>(state); +} +BENCHMARK(BM_PushPopCachedNoAlign)->Threads(2); + +static void BM_PushPopCachedCachelineAlign(benchmark::State& state) { + DoPushPop>(state); +} +BENCHMARK(BM_PushPopCachedCachelineAlign)->Threads(2); + +BENCHMARK_MAIN(); -- cgit v1.3.1