Add RingBuffer benchmarkHEADmaster

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.

1 files changed, 135 insertions, 0 deletions

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 <new>
+#include <array>
+#include <atomic>
+#include <cstddef>
+
+#include <benchmark/benchmark.h>
+
+enum class Alignment: std::size_t {
+    Default = alignof(std::atomic<std::size_t>),
+    Cacheline = std::hardware_destructive_interference_size
+};
+
+template <typename T,
+          Alignment Align = Alignment::Default,
+          std::size_t Size = 1024>
+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<std::size_t> writer_{0};
+    alignas(Align) std::atomic<std::size_t> reader_{0};
+    alignas(Align) std::array<T, Size> buffer_;
+};
+
+// See: https://rigtorp.se/ringbuffer
+template <typename T,
+          Alignment Align = Alignment::Default,
+          std::size_t Size = 1024>
+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<std::size_t> writer_{0};
+    alignas(Align) std::size_t cached_reader_{0};
+
+    alignas(Align) std::atomic<std::size_t> reader_{0};
+    alignas(Align) std::size_t cached_writer_{0};
+
+    alignas(Align) std::array<T, Size> buffer_;
+};
+
+static bool IsPusherThread(benchmark::State& state) {
+    return state.thread_index() == 0;
+}
+
+template <typename RingBuffer>
+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<RingBuffer<int>>(state);
+}
+BENCHMARK(BM_PushPopNoAlign)->Threads(2);
+
+static void BM_PushPopCachelineAlign(benchmark::State& state) {
+    DoPushPop<RingBuffer<int, Alignment::Cacheline>>(state);
+}
+BENCHMARK(BM_PushPopCachelineAlign)->Threads(2);
+
+static void BM_PushPopCachedNoAlign(benchmark::State& state) {
+    DoPushPop<CachedRingBuffer<int>>(state);
+}
+BENCHMARK(BM_PushPopCachedNoAlign)->Threads(2);
+
+static void BM_PushPopCachedCachelineAlign(benchmark::State& state) {
+    DoPushPop<CachedRingBuffer<int, Alignment::Cacheline>>(state);
+}
+BENCHMARK(BM_PushPopCachedCachelineAlign)->Threads(2);
+
+BENCHMARK_MAIN();