待機時間に上限を持つ高速MPMCキューを自作した話
Girls Just Wanna Have Fast MPMC Queues with Bounded Waiting
著者がロックフリー/ウェイトフリーの並行データ構造に挑戦し、チケットロック方式に基づく境界付きMPMCキューを実装した。CASループを避け、キャッシュ競合を最小限に抑えつつ、スレッドの停止や失敗を除けば待機時間に上限があることを保証する。理論から実装、ベンチマークまでを解説し、ソースコードも公開している。なお、当初はウェイトフリーと主張していたが、実際には要件を満たさないため訂正している。
短いスレッドの停止や失敗を除けば、この構造に対するどの操作にも、かかる時間の上限があります。つまり、どのコンシューマーやプロデューサーも飢餓状態に陥らず、すべてのエンキューとデキュー操作が最終的に完了することを保証します。