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 快取中。由於佇列寫入操作需要讀取頭索引，因此寫入操作可能需要一些快取一致性流量才能將頭索引快取行還原為獨佔狀態。在最壞的情況下，每次讀寫操作都會有一個高速緩存行從共享到獨佔的轉換。

接下來考慮一個快取尾部索引的佇列讀取器：如果快取的尾部索引顯示佇列為空，則將尾部索引載入到快取的尾部索引中。如果佇列非空，則進行多次讀取操作，直到快取的尾部索引可以完成，而不會竊取寫入者的尾部索引快取行的獨佔狀態。因此減少了快取一致性流量。可以對隊列寫入操作進行類似的論證。

此實作允許任意非兩個容量的冪，而不是分配額外的佇列槽來指示已滿佇列。如果您不想浪費額外佇列槽的儲存空間，則應該使用不同的實作。

參考：