// SPSC ring buffer vs mutex queue, and false sharing vs padded counters.
#include <algorithm>
#include <atomic>
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <mutex>
#include <queue>
#include <thread>
#include <vector>

constexpr size_t kLine = 128;  // Apple M1 cache line (sysctl hw.cachelinesize); 64 on most x86

template <class T, size_t Cap>
class Spsc {
  static_assert((Cap & (Cap - 1)) == 0, "capacity must be a power of two");
  alignas(kLine) std::atomic<size_t> head_{0};   // written by consumer
  alignas(kLine) size_t cached_tail_ = 0;        // consumer's private copy of tail
  alignas(kLine) std::atomic<size_t> tail_{0};   // written by producer
  alignas(kLine) size_t cached_head_ = 0;        // producer's private copy of head
  alignas(kLine) T buf_[Cap];
 public:
  bool push(const T& v) {
    const size_t t = tail_.load(std::memory_order_relaxed);
    if (t - cached_head_ == Cap) {
      cached_head_ = head_.load(std::memory_order_acquire);
      if (t - cached_head_ == Cap) return false;   // full
    }
    buf_[t & (Cap - 1)] = v;
    tail_.store(t + 1, std::memory_order_release);   // publish the slot
    return true;
  }
  bool pop(T& out) {
    const size_t h = head_.load(std::memory_order_relaxed);
    if (h == cached_tail_) {
      cached_tail_ = tail_.load(std::memory_order_acquire);
      if (h == cached_tail_) return false;            // empty
    }
    out = buf_[h & (Cap - 1)];
    head_.store(h + 1, std::memory_order_release);    // free the slot
    return true;
  }
};

template <class T>
class MutexQueue {
  std::mutex m_; std::queue<T> q_;
 public:
  bool push(const T& v) { std::lock_guard<std::mutex> g(m_); q_.push(v); return true; }
  bool pop(T& out) { std::lock_guard<std::mutex> g(m_); if (q_.empty()) return false; out = q_.front(); q_.pop(); return true; }
};

template <class Q> double transfer(Q& q, uint64_t n) {
  uint64_t sum = 0;
  auto t0 = std::chrono::steady_clock::now();
  std::thread prod([&] { for (uint64_t i = 1; i <= n; ++i) while (!q.push(i)) {} });
  std::thread cons([&] { uint64_t v; for (uint64_t i = 0; i < n; ++i) { while (!q.pop(v)) {} sum += v; } });
  prod.join(); cons.join();
  double s = std::chrono::duration<double>(std::chrono::steady_clock::now() - t0).count();
  if (sum != n * (n + 1) / 2) std::printf("CHECKSUM MISMATCH\n");
  return n / s / 1e6;
}

struct Packed { std::atomic<uint64_t> a{0}, b{0}; };
struct Padded { alignas(kLine) std::atomic<uint64_t> a{0}; alignas(kLine) std::atomic<uint64_t> b{0}; };

template <class C> double counters(uint64_t n) {
  C c;
  auto t0 = std::chrono::steady_clock::now();
  std::thread x([&] { for (uint64_t i = 0; i < n; ++i) c.a.fetch_add(1, std::memory_order_relaxed); });
  std::thread y([&] { for (uint64_t i = 0; i < n; ++i) c.b.fetch_add(1, std::memory_order_relaxed); });
  x.join(); y.join();
  return std::chrono::duration<double, std::nano>(std::chrono::steady_clock::now() - t0).count() / n;
}

template <class F> double median5(F f) { std::vector<double> r; for (int i = 0; i < 5; ++i) r.push_back(f()); std::sort(r.begin(), r.end()); return r[2]; }

// Round trip: A pushes to q1, B pops and echoes on q2, A waits for the echo.
template <class Q> std::vector<double> pingpong(uint64_t n) {
  auto* q1 = new Q(); auto* q2 = new Q();
  std::vector<double> rtt; rtt.reserve(n);
  std::thread echo([&] { uint64_t v; for (uint64_t i = 0; i < n; ++i) { while (!q1->pop(v)) {} while (!q2->push(v)) {} } });
  uint64_t v;
  for (uint64_t i = 0; i < n; ++i) {
    auto a = std::chrono::steady_clock::now();
    while (!q1->push(i)) {}
    while (!q2->pop(v)) {}
    rtt.push_back(std::chrono::duration<double, std::nano>(std::chrono::steady_clock::now() - a).count());
  }
  echo.join(); delete q1; delete q2;
  std::sort(rtt.begin(), rtt.end());
  return rtt;
}

int main(int argc, char** argv) {
  if (argc > 1) {  // quick correctness run (used under ThreadSanitizer)
    auto* q = new Spsc<uint64_t, 64>(); std::printf("tsan transfer: %.2f M/s\n", transfer(*q, 200000)); delete q; return 0;
  }
  for (int which = 0; which < 2; ++which) {
    auto r = which ? pingpong<MutexQueue<uint64_t>>(1'000'000) : pingpong<Spsc<uint64_t, 1024>>(1'000'000);
    auto P = [&](double p) { return r[std::min(r.size() - 1, (size_t)(p * r.size()))]; };
    std::printf("round trip %-6s p50=%.0fns p99=%.0fns p99.9=%.0fns\n", which ? "mutex" : "spsc", P(.5), P(.99), P(.999));
  }
  const uint64_t N = 20'000'000;
  std::printf("SPSC ring   : %6.1f M msgs/s\n", median5([&] { auto* q = new Spsc<uint64_t, 4096>(); double r = transfer(*q, N); delete q; return r; }));
  std::printf("mutex queue : %6.1f M msgs/s\n", median5([&] { MutexQueue<uint64_t> q; return transfer(q, N / 4); }));
  const uint64_t M = 50'000'000;
  std::printf("same line   : %6.2f ns/increment\n", median5([&] { return counters<Packed>(M); }));
  std::printf("padded      : %6.2f ns/increment\n", median5([&] { return counters<Padded>(M); }));
  std::printf("sizeof Packed=%zu Padded=%zu\n", sizeof(Packed), sizeof(Padded));
}
