SPSCQueue下载 - SPSCQueue源码下载

SPSCQueue

C/C++

Increased throughput

下载

SPSC队列.h

用 C++11 编写的单生产者单消费者无等待、无锁固定大小队列。此实现比boost::lockfree::spsc和folly::ProducerConsumerQueue更快。

例子

SPSCQueue< int > q ( 1 );
auto t = std::thread([&] {
  while (!q. front ());
  std::cout << *q. front () << std::endl;
  q. pop ();
});
q.push( 1 );
t.join();

有关完整示例，请参阅src/SPSCQueueExample.cpp 。

用法

SPSCQueue<T>(size_t capacity);
创建一个SPSCqueue保存类型为T capacity为容量的项目。容量至少需要为 1。
void emplace(Args &&... args);
使用就地构造对项目进行排队。如果队列已满则阻塞。
bool try_emplace(Args &&... args);
尝试使用就地构造对项目进行排队。成功则返回true ，如果队列已满则返回false 。
void push(const T &v);
使用复制构造对项目进行排队。如果队列已满则阻塞。
template <typename P> void push(P &&v);
使用移动构造对项目进行排队。仅当std::is_constructible<T, P&&>::value == true时才参与重载决策。如果队列已满则阻塞。
bool try_push(const T &v);
尝试使用复制构造将项目排队。成功则返回true ，如果队列已满则返回false 。
template <typename P> bool try_push(P &&v);
尝试使用移动构造将项目排队。成功则返回true ，如果队列已满则返回false 。仅当std::is_constructible<T, P&&>::value == true时才参与重载决策。
T *front();
返回指向队列前面的指针。如果队列为空，则返回nullptr 。
void pop();
将队列的第一项出队。调用 pop 之前必须确保队列非空。这意味着front()在每次调用pop()之前必须返回一个非nullptr 。需要std::is_nothrow_destructible<T>::value == true 。
size_t size();
返回队列中可用的项目数。
bool empty();
如果队列当前为空，则返回 true。

只有单个写入线程可以执行入队操作，并且只有单个读取线程可以执行出队操作。任何其他用途均无效。

大页面支持

除了通过标准自定义分配器接口支持自定义分配之外，该库还支持标准提案 P0401R3 在分配器接口中提供大小反馈。这允许方便地使用大页面，而不会浪费任何分配的空间。仅当启用 C++17 时才支持使用大小反馈。

该库当前不包含大页面分配器，因为用于分配大页面的 API 依赖于平台，并且大页面大小的处理和 NUMA 感知是特定于应用程序的。

下面是 Linux 大页分配器的示例：

# include < sys/mman.h >

template < typename T> struct Allocator {
  using value_type = T;

  struct AllocationResult {
    T *ptr;
    size_t count;
  };

  size_t roundup ( size_t n) { return (((n - 1 ) >> 21 ) + 1 ) << 21 ; }

  AllocationResult allocate_at_least ( size_t n) {
    size_t count = roundup ( sizeof (T) * n);
    auto p = static_cast <T *>( mmap ( nullptr , count, PROT_READ | PROT_WRITE,
                                   MAP_PRIVATE | MAP_ANONYMOUS | MAP_HUGETLB,
                                   - 1 , 0 ));
    if (p == MAP_FAILED) {
      throw std::bad_alloc ();
    }
    return {p, count / sizeof (T)};
  }

  void deallocate (T *p, size_t n) { munmap (p, roundup ( sizeof (T) * n)); }
};

有关如何在 Linux 上使用大页面的完整示例，请参阅src/SPSCQueueExampleHugepages.cpp 。

执行

底层实现基于环形缓冲区。

我们已采取谨慎措施，确保避免出现任何虚假共享问题。头索引和尾索引对齐并填充到错误共享范围（缓存行大小）。此外，槽缓冲区在开头和结尾处填充了错误共享范围，这可以防止与任何相邻分配发生错误共享。

通过分别在写入器和读取器中本地缓存头索引和尾索引，该实现比典型的并发环形缓冲区具有更高的吞吐量。缓存通过减少缓存一致性流量来提高吞吐量。

要了解其工作原理，首先考虑没有缓存的情况下的读取操作：需要更新头索引（读取索引），从而将该缓存行以独占状态加载到 L1 缓存中。需要读取尾部（写索引）以检查队列是否为空，从而以共享状态加载到 L1 缓存中。由于队列写入操作需要读取头索引，因此写入操作可能需要一些缓存一致性流量才能将头索引缓存行恢复为独占状态。在最坏的情况下，每次读写操作都会有一个高速缓存行从共享到独占的转换。

接下来考虑一个缓存尾部索引的队列读取器：如果缓存的尾部索引表明队列为空，则将尾部索引加载到缓存的尾部索引中。如果队列非空，则进行多次读取操作，直到缓存的尾部索引可以完成，而不会窃取写入者的尾部索引缓存行的独占状态。因此减少了缓存一致性流量。可以对队列写操作进行类似的论证。

此实现允许任意非两个容量的幂，而不是分配额外的队列槽来指示已满队列。如果您不想浪费额外队列槽的存储空间，则应该使用不同的实现。

参考：