优化环形缓冲区的吞吐量

单生产者单消费者（SPSC）环形缓冲区是最典型的 wait-free 队列。尽管概念简单，朴素实现会因缓存一致性的瓶颈而受限，在现代硬件上吞吐量大约只有每秒 550 万次操作。本文展示一次结构性改动如何把它提升到 1.12 亿次/秒 —— 20 倍的改善，同时胜过 boost::lockfree::spsc_queue 和 folly::ProducerConsumerQueue。

完整的优化实现可见 SPSCQueue.h。

数据结构

队列把元素放在一个连续数组里。两个原子索引分别标记读写位置。布局上的关键是这两个索引必须位于不同的缓存行，以防”伪共享（false sharing）”：

struct ringbuffer {
  std::vector<int> data_;
  alignas(64) std::atomic<size_t> readIdx_{0};
  alignas(64) std::atomic<size_t> writeIdx_{0};

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

alignas(64) 匹配 x86-64 和 ARM 上的缓存行宽度。更可移植的做法是使用 C++17 引入的 std::hardware_destructive_interference_size。

会浪费一个槽位以区分”满”和”空”：当 (writeIdx + 1) % capacity == readIdx 时队列为满。

这个布局与 Linux 内核中的 io_uring 环结构本质一致：

struct io_uring {
  u32 head ____cacheline_aligned_in_smp;
  u32 tail ____cacheline_aligned_in_smp;
};

push 与 pop

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

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

元素类型用 int（4 字节），把队列本身的开销与”拷贝大元素”的代价隔离开。对大元素而言，优化队列本身的收益会递减。

基线性能

基准：通过容量为 100,000 的队列在两个线程间传递 1 亿个整数。在 AMD Ryzen 9 3900X 上用 -O3 -march=native -std=c++20 编译，每个线程绑定到不同的 CCX。

5,513,850 ops/s

Performance counter stats for './a.out 1 11':
  349,857,603 cache-misses:u   # 占所有 cache refs 的 91.228%
  383,497,078 cache-references:u
    6,673,242 l2_request_g1.change_to_x:u

18.137 seconds time elapsed

1 亿次传输、3.5 亿次缓存未命中 —— 每一来回大约 3.5 次 miss。这与 boost::lockfree::spsc_queue 和 folly::ProducerConsumerQueue 吞吐相当，后两者存在同样的结构性问题。

为什么这么多缓存未命中？

MESI 协议允许多核同时在 Shared 状态下持有一条缓存行，但写之前必须先取得 Exclusive 所有权。每一次从 Shared 到 Exclusive 的转换都是一次 cache miss。

看每次 push 会发生什么：

writer 加载 writeIdx（自己的变量）—— 很可能命中。
writer 加载 readIdx 检查是否满 —— 这条缓存行在 reader 那边是 Exclusive，writer 必须请求所有权，产生一次 miss。
writer 写新的 writeIdx —— reader 立刻就要看到这个值，下一次 reader 会请求 Exclusive，再产生一次 miss。

每次操作 3 次缓存未命中，每次都需要跨核互联通信一次（在多 CCX 的 Ryzen 上是几百纳秒）。

修复：在本地缓存对端的索引

每个线程读取对端的索引，仅仅是为了判断队列是否空/满。绝大多数情况 —— 队列既不空也不满 —— 那次”远端读”是没必要的。把最后一次看到的对端索引值缓存下来，只有当缓存值表明队列到了边界时才刷新：

struct ringbuffer2 {
  std::vector<int> data_{};
  alignas(64) std::atomic<size_t> readIdx_{0};
  alignas(64) size_t writeIdxCached_{0};   // reader 缓存的 writeIdx
  alignas(64) std::atomic<size_t> writeIdx_{0};
  alignas(64) size_t readIdxCached_{0};    // writer 缓存的 readIdx

  ringbuffer2(size_t capacity) : data_(capacity, 0) {}
};

每个缓存变量独占一条缓存行，并且只被写入它的那个线程拥有。

bool push(int val) {
  auto writeIdx = writeIdx_.load(std::memory_order_relaxed);
  auto nextWriteIdx = (writeIdx + 1) % data_.size();

  if (nextWriteIdx == readIdxCached_) {
    readIdxCached_ = readIdx_.load(std::memory_order_acquire);
    if (nextWriteIdx == readIdxCached_) return false;
  }

  data_[writeIdx] = val;
  writeIdx_.store(nextWriteIdx, std::memory_order_release);
  return true;
}

bool pop(int &val) {
  auto readIdx = readIdx_.load(std::memory_order_relaxed);

  if (readIdx == writeIdxCached_) {
    writeIdxCached_ = writeIdx_.load(std::memory_order_acquire);
    if (readIdx == writeIdxCached_) return false;
  }

  val = data_[readIdx];
  readIdx_.store((readIdx + 1) % data_.size(), std::memory_order_release);
  return true;
}

跨核的 acquire/release 配对现在只在”生产者追上消费者、反之亦然”时才发生。在稳态下 —— 生产者比消费者领先几个槽位 —— 热循环只碰本地持有的缓存行。

优化后的性能

112,287,037 ops/s

Performance counter stats for './a.out 1 11':
  15,010,392 cache-misses:u   # 占所有 cache refs 的 32.55%
  46,110,663 cache-references:u
   6,781,273 l2_request_g1.change_to_x:u

0.892 seconds time elapsed

指标	优化前	优化后	提升
吞吐量	5.5M ops/s	112M ops/s	20 倍
缓存未命中	350M	15M	减少 95%
用时	18.1 s	0.9 s	20 倍

进一步的优化

批处理。 每次同步点读写多个元素能进一步摊薄 acquire/release 对的代价。Linux 的 io_uring 提交环和完成环就是这样设计的。

大页（huge pages）。 对于大队列，数据数组的 TLB 压力会变得显著。用自定义 allocator 或 madvise(MADV_HUGEPAGE) 把 data_ 用 2 MiB 大页来后备，能大幅减少 TLB 未命中。

2 的幂容量。 把容量限定为 2 的幂，能用按位与代替求模，省掉每次索引前进的一次除法。