SPSCQueueダウンロード - SPSCQueueソースコードのダウンロード

SPSCQueue

C/C++

Increased throughput

ダウンロード

SPSCQueue.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);
容量capacityを持つタイプTの項目を保持するSPSCqueueを作成します。容量は少なくとも 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 キャッシュにロードされます。キュー書き込み操作ではヘッドインデックスを読み取る必要があるため、書き込み操作ではヘッドインデックスキャッシュラインを排他状態に戻すためにある程度のキャッシュコヒーレンシトラフィックが必要になる可能性があります。最悪の場合、読み取りおよび書き込み操作ごとに 1 つのキャッシュラインが共有から排他に移行することになります。

次に、末尾インデックスをキャッシュするキューリーダーを検討します。キャッシュされた末尾インデックスがキューが空であることを示している場合、末尾インデックスをキャッシュされた末尾インデックスにロードします。キューが空ではなかった場合、キャッシュされた末尾インデックスまでの複数の読み取り操作は、ライターの末尾インデックスキャッシュラインの排他状態を盗むことなく完了できます。したがって、キャッシュコヒーレンシのトラフィックが減少します。キュー書き込み操作についても同様の議論を行うことができます。

この実装では、キューがいっぱいであることを示すために追加のキュースロットを割り当てる代わりに、任意の 2 のべき乗以外の容量が可能になります。追加のキュースロットのためにストレージを無駄にしたくない場合は、別の実装を使用する必要があります。

参考文献: