atomic_queue
1.0.0
C ++ 14円形バッファーとstd::atomicに基づく複数のプロデューサー - マルチプレーズ - 消費者ロックフリーキュー。
1つのスレッド間のレイテンシを最小限に抑えることを目標に設計し、要素をキューに押し込み、別のスレッドがキューからポップします。
Linuxで開発、テスト、ベンチマークされていますが、 std::atomic実装するC ++ 14のプラットフォームをサポートする必要があります。 Windowsと互換性があると報告されていますが、GitHubがホストする連続統合は現在、Ubuntu-20.04およびUbuntu-22.04のx86_64プラットフォームのみで設定されています。他のアーキテクチャやプラットフォームで実行するための継続的な統合を拡張するためのリクエストをプルすることを歓迎します。
レイテンシを最小限に抑える場合、良いデザインは、追加するものが何も残っていない場合ではなく、これらのキューが例示するように、削除するものが残っていない場合です。
遅延を最小化すると、自然にスループットが最大化されます。理想的な数学的および実用的なエンジニアリングの意味では、低潜伏期相互が高く、高視力があります。低レイテンシーは、異なるスレッドによって1つのキューに押し込まれたイベントのオリジナル（ハードウェア）のグローバル時間順序を破壊する遅延やバッチングと互換性がありません。一方、スループットの最大化は、複数の更新を遅らせてバッチすることにより、遅延を犠牲にして実行できます。
これらのキューが続く主なデザインの原則はミニマリズムであり、次のようなデザインの選択をもたらします。
push / pop上でコピー/移動することを意味します。キュー内の要素への参照/ポインターは取得できません。これらの小さなデザインの選択のそれぞれがそれ自体に与える影響はほとんど測定できませんが、それらの全体的な影響は、成分の影響の単純な合計、つまり超大型の複合または相乗効果よりもはるかに大きくなります。これらの小さなデザインの選択肢の複数を組み合わせることから生じる相乗効果は、CPUが最も妨げられていないピーク能力で実行できるようにするものです。
これらの設計の選択も制限です。
超低遅延アプリケーションはそれだけでなく、それ以上は必要ありません。ミニマリズムは報われます。スループットとレイテンシーのベンチマークをご覧ください。
他のいくつかの十分に確立された人気のスレッドセーフコンテナが、ベンチマークの参照に使用されます。
std::mutex -std std::mutexを備えた固定サイズのリングバッファー。pthread_spinlock pthread_spinlock_tを備えた固定サイズのリングバッファー。boost::lockfree::spsc_queueブーストライブラリからの待ち時間のないシングルプロデューサーシングル - 消費者キュー。boost::lockfree::queueブーストライブラリからのロックフリーのマルチプロデューサー - マルチ - マルチ - 消費者キュー。moodycamel::ConcurrentQueue - 消費者キュー。このキューは、レイテンシを犠牲にしてスループットを最大化し、異なるスレッドによって1つのキューに押し込まれた要素のグローバルな時間順序を避けるように設計されています。この点でベンチマークされた他のキューと同等ではありません。moodycamel::ReaderWriterQueue非ブロッキングモードで使用されるロックフリーのシングルプロデューサーシングル - 消費者キュー。xenium::michael_scott_queueとスコットが提案したロックフリーのマルチプロデューサー - マルチ - 消費者キュー（このキューは、同じ提案にも基づいてboost::lockfree::queueに似ています）。xenium::ramalhete_queueラマルヘテとコレイアが提案したロックフリーマルチプロデューサー - マルチ - 消費者キュー。xenium::vyukov_bounded_queue Vyukovが提案したバージョンに基づいた境界のあるマルチプロデューサー - マルチ - 消費者キュー。tbb::spin_mutex -Intelスレッドビルディングブロックからのtbb::spin_mutex備えたロックされた固定サイズのリングバッファー。tbb::concurrent_bounded_queueインテルスレッドビルディングブロックから非ブロッキングモードで使用される同名のキュー。提供されるコンテナは、ヘッダーのみのクラステンプレートであり、建物/インストールは必要ありません。
git clone https://github.com/max0x7ba/atomic_queue.git
atomic_queue/include directory（フルパスを使用）をビルドシステムのパスに含めます。#include <atomic_queue/atomic_queue.h> C ++ソース。 vcpkg install atomic-queue
コナンパッケージの消費方法に関する公式チュートリアルに従ってください。このライブラリに固有の詳細は、Conancenterで入手できます。
提供されるコンテナは#include <atomic_queue/atomic_queue.h>のみを必要とするヘッダーのみのクラステンプレートです。建物/インストールは必要ありません。
テストとベンチマークを実行するには、建物が必要です。
git clone https://github.com/cameron314/concurrentqueue.git
git clone https://github.com/cameron314/readerwriterqueue.git
git clone https://github.com/mpoeter/xenium.git
git clone https://github.com/max0x7ba/atomic_queue.git
cd atomic_queue
make -r -j4 run_benchmarks
ベンチマークでは、Intel TBBライブラリを利用可能にする必要があります。 /usr/local/includeおよび/usr/local/libにインストールされていると想定しています。他の場所にインストールされている場合は、 cppflags.tbbおよびldlibs.tbb Makefileで変更することができます。
AtomicQueue原子要素用の固定サイズのリングバッファー。OptimistAtomicQueue空またはいっぱいに忙しいアトミック要素のためのより速い固定サイズのリングバッファー。 try_push / try_popの代わりにpush / popで使用されるAtomicQueueです。AtomicQueue2非原子要素用の固定サイズのリングバッファー。OptimistAtomicQueue2空またはいっぱいに忙しい非原子的要素のためのより速い固定サイズのリングバッファー。 try_push / try_popの代わりにpush / popで使用されるAtomicQueue2です。これらのコンテナには、バッファサイズがコンストラクターへの引数として指定されている、対応するAtomicQueueB 、 OptimistAtomicQueueB 、 AtomicQueueB2 、 OptimistAtomicQueueB2バージョンがあります。
完全に順序付けられたモードがサポートされています。このモードでは、消費者はメッセージが投稿されたのと同じFIFO注文でメッセージを受信します。このモードは、 pushおよびpop機能のためにサポートされていますが、 try_バージョンではありません。 Intel X86では、2019年の時点で、完全に順序付けられたモードのコストは0です。
シングルプロデューサーシングル消費者モードがサポートされています。このモードでは、高価なアトミックRead-Modify-Modify-Write CPU命令は必要ありません。最も安い原子荷重とストアのみが必要です。これにより、キュースループットが大幅に向上します。
ムーブのみのキュー要素タイプが完全にサポートされています。たとえば、 std::unique_ptr<T>要素のキューはAtomicQueue2B<std::unique_ptr<T>>またはAtomicQueue2<std::unique_ptr<T>, CAPACITY>です。
キュークラステンプレートは、次のメンバー関数を提供します。
try_pushキューの最後に要素を追加します。キューがいっぱいになったときにfalseを返します。try_popキューの前面から要素を削除します。キューが空の場合にfalseを返します。push （Optimist） - キューの最後に要素を追加します。キューがいっぱいになったときに忙しい待機。キューがいっぱいになっていないときのtry_pushよりも速い。オプションのFIFOプロデューサーキューイングと総注文。pop （Optimist） - キューの前面から要素を削除します。キューが空のときに忙しい待機。キューが空になっていない場合のtry_popよりも速い。オプションのFIFO消費者キューイングと総注文。was_sizeコール中に消費されていない要素の数を返します。状態は、返品値が検討されるまでに変更された可能性があります。was_emptyコール中にコンテナが空であった場合にtrueを返します。状態は、返品値が検討されるまでに変更された可能性があります。was_fullコール中にコンテナがいっぱいだった場合、 trueを返します。状態は、返品値が検討されるまでに変更された可能性があります。capacity - キューが保持できる要素の最大数を返します。アトミック要素は、 std::atomic<T>{T{}}.is_lock_free()がtrueを返すものであり、C ++ 17の機能が利用可能な場合、 std::atomic<T>::is_always_lock_freeコンパイル時にtrueを評価します。言い換えれば、CPUはそのような要素を原子的にネイティブにロード、保存、比較して交換できます。 X86-64では、そのような要素はすべてC ++標準算術およびポインタータイプです。
アトミック要素のキューは、空の要素マーカーNILとして機能するために1つの値を留保し、そのデフォルト値は0です。 NIL値をキューに押し込んではならず、 push機能にはデバッグモードビルドでガードするためのassertステートメントがあります。リリースモードでNIL要素をキューに押し込むと、デッドロックや失われたキュー要素などの未定義の動作が構築されます。
楽観主義は、キュータイプではなく、キュー変更操作制御フローの選択であることに注意してください。ほとんどの場合、キューがいっぱいでない場合、キューがいっぱいではない場合、楽観主義者のpop push最速です。ほとんどの場合、キューが空になっていない場合。楽観的であり、そうではない操作は、制限なしで混合できます。ベンチマーク内のOptimistAtomicQueueプッシュpush popのみを使用しています。
使用例については、example.ccを参照してください。
push and try_push操作は、同じキューオブジェクトの後続のpopまたはtry_pop操作を使用して（ std::memory_orderで定義されています）と同期します。それを意味します：
push / try_push memory_order::release過去に並べ替えられません。 std::mutex::unlockのメモリ順序と同じメモリ順序。pop / try_popの前に非原子の負荷 /ストアは並べ替えられません。これはmemory_order::acquire操作です。 std::mutex::lockのメモリ順序と同じメモリ順序。push / try_pushが消費者のスレッドで表示されるようになり、その特定の要素がpop / try_pop表示されます。 ここで利用可能なキューは、要素を保存するためにリングバッファーアレイを使用します。キューの容量は、コンパイル時間または建設時間に固定されています。
プロダクションでは、複数のプロデューサー - マルチプレーズと消費者のシナリオでは、リングバッファ容量を最大予想キューサイズに設定する必要があります。リングバッファがいっぱいになると、消費者が要素を十分に速く消費できないことを意味します。その修正は次のいずれかです。
pushおよびpopコールは常にいくつかの高価なCPUサイクルが発生し、他のスレッドに関してアトミック/一貫した/孤立したファッションにおけるキュー状態の完全性を維持し、これらのコストはキューの競合が増加するにつれて非常に直線的に増加します。 1つのイベントから生じる複数の小さな要素または1つのキューメッセージへの要素をバッチするプロデューサーは、多くの場合、合理的な解決策です。Power-of-2リングバッファーアレイサイズを使用すると、いくつかの重要な最適化が可能になります。
% SIZEを使用して、リングバッファアレイインデックスにマッピングされます。残りのバイナリ演算子%通常、安価ではない分割CPU命令を生成しますが、Power-2サイズを使用すると、その残りのオペレーターが1つの安価なバイナリand CPU命令になり、それが得られるほど速いです。M消費者と一緒にNプロデューサーの代わりに、1人の消費者と競合する1人の生産者のみです（CPUの数が1つのキャッシュラインに収まる要素の数よりも大きくない場合）。この最適化は、生産者と消費者の数、および要素のサイズにより、より良く拡大します。この最適化を無効にすると、生産者と消費者が少ない（それぞれ最大2つ）がスループットが向上する（ただし、ラン全体でより高い分散）。コンテナは、サイズと内部インデックスにunsignedタイプを使用します。 x86-64のプラットフォームでは、 unsigned幅は32ビットですが、 size_tは64ビット幅です。 64ビット命令は、追加のバイト命令プレフィックスを使用して、CPU命令キャッシュとフロントエンドにわずかに圧力をかけます。したがって、パフォーマンスを最大化するために、32ビットunsignedインデックスが使用されます。これにより、キューサイズは4,294,967,295の要素に制限されます。これは、多くのアプリケーションにとって合理的な厳しい制限と思われます。
アトミックキューは、任意の可動要素タイプ（ std::unique_ptrを含む）で使用できますが、最高のスループットとpopのためにpushキュー要素はコピーしてロックフリー（ unsignedまたはT*など）を安くする必要があります。
概念的には、 pushまたはpop操作は2つの原子ステップを実行します。
headインデックスを増加させ、消費者はtailインデックスを増やします。各スロットには、1つのプロデューサーと1つの消費者スレッドのみがアクセスします。NILに変わり、スロットから消費者の積み込みは状態をNILに変えます。スロットは、1つのプロデューサーと1つの消費者スレッドのスピンロックです。これらのキューはpushまたはpopを実行するスレッドがステップ1を完了し、ステップ2を完了する前に先制することができると予想しています。
システム全体の進捗が保証されている場合、アルゴリズムはロックフリーです。これらのキューは、次のプロパティによるシステム全体の進捗状況を保証します。
pushは、前のpushとは無関係です。 1つのプロデューサースレッドによる不完全な（先制） push 、他のスレッドのpushに影響しません。pop 、前のpopから独立しています。 1つの消費者スレッドによる不完全な（先制） pop 、他のスレッドのpop影響しません。push 、この特定のキュースロットから要素をpop消費者スレッドが1つだけ影響します。他のすべてのスレッドpopは影響を受けません。pop 、この特定のキュースロットに要素をpush 1つの生産者スレッドのみに影響し、プロデューサーがリングpop全体を包み込んでいないかなりありそうもないシナリオで、この特定のキュースロットになりました。他のすべてのスレッドpush 、 popが影響を受けません。 Linuxタスクスケジューラスレッドプリエンプションは、ユーザースペースプロセスが影響を与えたり脱出したりすることができないものではありません。
それでも、自分のミッションクリティカルアプリケーションスレッドの先制を最小限に抑えるためにできることがいくつかあります。
chrt --fifo 50 <app>のリアルタイムSCHED_FIFOスケジューリングクラスを使用します。優先度の高いSCHED_FIFOスレッドまたはカーネル割り込みハンドラーは、 SCHED_FIFOスレッドを先取りできます。SCHED_OTHERを使用すると、これらのキューを使用する目的は無効になります。SCHED_FIFOリアルタイムスレッドがスロットルされないようにします。tasksetを備えたこれらの分離コアに明示的に配置する必要があります。人々はしばしばstd::this_thread::yield() / sched_yield / pthread_yieldへの後続の呼び出しで忙しいものを制限することを提案します。ただし、 sched_yield 、OSカーネルにスレッドが待っているものを通信しないため、ロックするための間違ったツールです。そのため、OSスレッドスケジューラは、共有状態が変更されたときに適切なタイミングで再開するように呼び出しスレッドをスケジュールすることはできません（このCPUコアで実行できる他のスレッドがない限り、発信者がすぐに再開されるように）。詳細については、 man sched_yieldのメモセクションとsched_yieldとSpinLocksに関するLinuxカーネルスレッドを参照してください。
Linuxには、Mutex TypeのPTHREAD_MUTEX_ADAPTIVE_NPがあります。これは、ロックされたミューテックスを多数の反復に忙しくし、その後、標準をカーネルにブロックして待っているスレッドを破壊します。ベンチマークでは、最悪のパフォーマンスがあり、パフォーマンスを向上させる方法を見つけることができませんでした。それがベンチマークに含まれていない理由です。
Intel CPUでは、4つのデバッグ制御レジスタを使用してスピンロックメモリ領域を監視し、 select （およびその友人）またはsigwait （ perf_event_open and uapi/linux/hw_breakpoint.hを参照）を使用してselect（およびその友人）またはsigwaitを使用できます。スピンロックウェイターは、スピンロック状態が更新されるまで、 selectまたはsigwaitで自分自身を中断することができました。しかし、これらのレジスタのうち4つしかないため、そのような解決策は拡大しません。
スループットとレイテンシーのベンチマークチャートを表示します。
ベンチマークを複雑にするOSの動作がいくつかあります。
SCHED_FIFO Priority 50を回避するために、スケジューラ時間量子容量を無効にし、優先度の低いプロセス/スレッドでスレッドを非償還するために使用されます。benchmarksの効果を最小限に抑えるために、実行可能ファイルは少なくとも33回実行されます。ベンチマークチャートには平均値が表示されます。チャートツールチップには、標準偏差、最小値と最大値も表示されます。シングルプロデューサーシングル - 消費者キューのベンチマークパフォーマンスboost::lockfree::spsc_queue 、 moodycamel::ReaderWriterQueueおよびこれらのキューは、同じ原子負荷と貯蔵命令を使用してまったく同じアルゴリズムを実装するため、単一プロデューサー - シングル消費者モードで同一である必要があります。 boost::lockfree::spsc_queue実装は、当時ベンチマークされていたため、生成されたアセンブリコードでのみ顕著な微妙な問題からのL1Dキャッシュの競合、コールドブランチの誤評価、またはパイプラインストールを最小化するための最適化がありませんでした。
数x86-64マシンのみにアクセスできます。さまざまなハードウェアにアクセスできる場合はscripts/run-benchmarks.shの出力ファイルをお気軽に送信してください。shでは、ベンチマークページに結果を含めます。
巨大なページが利用可能な場合、ベンチマークは、TLBミスを最小限に抑えるために、キューに1x1GBまたは16x2MBの巨大なページを使用します。巨大なページを有効にするには、次のいずれかを実行します。
sudo hugeadm --pool-pages-min 1GB:1
sudo hugeadm --pool-pages-min 2MB:16
または、システム内の透明な巨大なページを有効にし、TCMALLOCなどの巨大な手頃なアロケーターを使用することをお勧めします。
デフォルトでは、Linuxスケジューラは、CPUの100％を消費することでリアルタイムスレッドをスロットルするため、ベンチマークに有害です。詳細については、リアルタイムグループのスケジューリングをご覧ください。リアルタイムスレッドスロットリングを無効にするには：
echo -1 | sudo tee /proc/sys/kernel/sched_rt_runtime_us >/dev/null
nプロデューサーのスレッドは、4バイトの整数を同じキューに押し込み、n消費者スレッドはキューから整数をポップします。すべての生産者は、合計1,000,000のメッセージを投稿しています。すべてのメッセージを送信および受信する合計時間が測定されます。ベンチマークは、1人の生産者と1人の消費者から(total-number-of-cpus / 2)生産者 /消費者まで実行され、異なるキューのスケーラビリティを測定します。
あるスレッドは、整数を1つのキューに別のスレッドに投稿し、別のキューからの返信を待ちます（合計2つのキュー）。ベンチマークは、10ランの最高の100,000ピンポンの合計時間を測定します。ここでは、最小限のレイテンシを達成および測定できるようにするために、ここでは最小限です（1プロデューサー-1消費者、キューの1つの要素）。平均往復時間を報告します。
貢献は大歓迎です。 .editorconfigおよび.clang-format使用して、コードのフォーマットを自動的に一致させることができます。
マルチスレッドプログラミングの主題に関するいくつかの本は、私が非常に有益だと感じました：
Copyright（c）2019 Maxim Egorushkin。 MITライセンス。ファイルライセンスの完全なライセンスを参照してください。
