爆速MPMCキューを実装したい！待ち時間制約付きで実現するモダンなアプローチ

マルチプロデューサー・マルチコンシューマー（MPMC）キューにおいて、高いパフォーマンスを維持しつつ、各スレッドの待ち時間に制約（Bounded Waiting）を設けるにはどうすればよいでしょうか？高負荷な並行処理環境でもストレスフリーなキューを実現するための設計戦略を考察します。

免責事項：この記事の以前のバージョンで、この構造はウェイトフリーであると主張していましたが、これは誤りです。ウェイトフリーであるためには、あるスレッドの失敗や中断が他のスレッドの失敗や中断を引き起こさないことが求められます。実際、このキューはその要件を満たしていません。キュー操作のウェイト境界について論じているメインセクションはこれを反映するように修正されましたが、記事の他の部分は修正されていません。そのため、本文中にこれをウェイトフリーなキューとして言及している箇所が残っている可能性がありますが、実際は違います。投稿後に記事を大幅に書き直すことを避けるため、それらのセクションはそのままにしました。Redditユーザーのmatthieumさん、訂正してくれてありがとう！

素敵な免責事項だね！matthieumさんの（長文の）Redditコメントも読む価値があるよ：https://www.reddit.com/r/rust/comments/1up0uhg/girls_just_wa... (https://www.reddit.com/r/rust/comments/1up0uhg/girls_just_wanna_have_fast_waitfree_mpmc_queues/ovx8yfz/)

見落としていたかもしれないけど、N個の個別のデータスロット間でのフォールスシェアリングについての議論が見当たらないね。各スロットをキャッシュラインの幅にパディングする（あるいは、少なくとも1ラインあたりのスロット数を減らす）、そして/またはスロット検索に何らかの全単射ハッシュを使用して、連続するチケットが隣接するスロットにアクセスしないようにするのは有益かもしれない。

ロックフリーデータ構造の話題なら、SPSCについてのこれもかなり興味深かったよ。https://david.alvarezrosa.com/posts/optimizing-a-lock-free-r... (https://david.alvarezrosa.com/posts/optimizing-a-lock-free-ring-buffer/) 秒間1200万から3億500万オペレーションまで高速化してる。

このアプローチを使った、広く使われている自分のC++実装を置いておくよ：https://github.com/rigtorp/MPMCQueue (https://github.com/rigtorp/MPMCQueue)

美しい、ハッキングの警告が出るなんて最悪の展開だな