ロックフリーのデータ構造。 キュー分析

ロックフリーコンテナの寿命の前の投稿から多くの時間が経過しました。 キューの論文の続きをすぐに書くことを期待していましたが、問題がありました。何を書くべきかは知っていましたが、C ++ではこれらのアプローチがありませんでした。 「自分で試しなかったと書くのは良くありません」と思い、その結果、 libcdsに新しいキューアルゴリズムを実装しようとしました 。

今、議論のサイクルを続けることができる時が来ました。 この記事はキューで終わります。



中断した場所を簡単に思い出してください。 ロックフリーキューのいくつかの興味深いアルゴリズムが検討され、カーテンはいくつかの合成テストでの作業の結果を示しています。 主な結論は、すべてが悪いということです！ マジックコンペアアンドスワップ（CAS）のロックフリーアプローチが線形ではないにしても、少なくともスレッド数の増加に伴うパフォーマンスの向上が得られるという期待は実現しませんでした。 キューはスケーリングしません。 理由は何ですか？..



この質問に対する答えは、最新のプロセッサのアーキテクチャにあります。 CASプリミティブはかなり重い命令であり、キャッシュと内部同期プロトコルを大量にロードします。 同じキャッシュライン上でCASを積極的に使用することで、プロセッサは主にキャッシュの一貫性を維持することに専念しています 。PaulMcKenney教授は私の助けを借りて詳細に書いています 。



スタックとキューは、エントリポイントの数が少ないため、データ構造のロックフリーアプローチには非常に不向きです。 スタックの場合、そのようなポイントは1つだけです-スタックの最上部、キューの場合、ヘッドとテールの2つがあります。 CASはこれらのポイントへのアクセスを求めて競合しますが、プロセッサの使用率が100％になるとパフォーマンスが低下します。 何にも似ていませんか？..これは古典的なスピンロックです！ CASのロックフリーアプローチでは、ミューテックスによる外部同期がなくなりましたが、プロセッサ命令レベルで内部同期が得られ、ほとんど勝ちませんでした。





競争力のあるキューの効果的な実装の問題は、研究者にとって依然として関心のあるものです。 近年、「額に」ロックフリーキューを実装する際のさまざまなトリックが期待される結果をもたらさないという理解が高まっており、他のアプローチを検討する必要があります。 さらに、それらのいくつかを検討します。

フラット結合

スタックに関する記事でこの方法を説明しましたが、フラット結合は普遍的な方法であるため、キューに適用できます。 ロシアのC ++ User Groupでの プレゼンテーションのビデオに読者を送ります。このビデオは、フラット結合の実装専用です。

キューの配列

表面にあるが、多くの落とし穴があるにもかかわらず実装がかなり難しいアプローチが2013年に「スケーラブルなロックフリーキューを実装するための競合を協力に置き換える」というタイトルの記事で提案されました。 。

アイデアはとてもシンプルです。 単一のキューの代わりに、サイズKの配列が作成され、その各要素はロックフリーキューであり、単純に接続されたリストで表されます。 配列の次の（モジュロK）スロットに新しい要素が追加されます。 したがって、キューのテールでの混雑は平準化されます。テールが1つではなく、テールがK個あるため、K個の並列フローまで線形のスケーラビリティが得られることが期待できます。 もちろん、配列スロットへの各挿入を多重化するには、特定の一般的なアトミック単調増加プッシュ操作カウンターが必要です。 当然、このカウンターは、すべてのプッシュストリームの単一の「スティッキングポイント」になります。 しかし、著者は、x86アーキテクチャxadd



アトミック加算（この場合はインクリメント）のxadd



命令はCASよりもわずかに高速であると主張しています（私の観察によれば、それは不合理ではありません）。 したがって、x86では勝つことが期待できます。 他のアーキテクチャでは、atomic fetch_add



CASによってエミュレートされるため、ゲインはそれほど顕著ではありません。

キューから要素を削除するためのコードは似ています。削除された要素のアトミックカウンター（ポップカウンター）があり、それに基づいてKを法として配列スロットが選択されます。 キューのメインプロパティの違反を排除するために-FIFO-各要素には追加の負荷（ ticket



）-要素を追加したときのプッシュカウンターの値、実際には要素のシリアル番号が含まれます。 スロットで削除する場合、 ticket



=を持つ要素がポップカウンターの現在の値を検索します。見つかった要素はpop()



操作の結果です。

空のキューから削除する問題を解決する興味深い方法。 このアルゴリズムでは、削除カウンター（ポップカウンター）のアトミックインクリメントの後に、対応するスロットでの検索が最初に続きます。 スロットが空である可能性があります。 これは、キュー全体が空であることを意味します。 ただし、ポップカウンタは既にインクリメントされており、それ以上使用するとFIFOに違反し、要素が失われることさえあります。 ロールバック（デクリメント）することはできません。突然、他のスレッドが要素を追加または削除します（一般的に、「back-play-not-impossible」はロックフリーアプローチの不可欠な特性です）。 したがって、空のキューからpop()



状況が発生すると、配列は無効であると宣言され、次に要素が挿入されたときに、新しいプッシュカウンターとポップカウンターを持つ新しい配列が作成されます。



残念ながら、著者はメモリを解放するという問題を（スペースの不足のために）気にしませんでした。アルゴリズムへのハザードポインタースキームの適用の表面的な説明を含むいくつかの提案を与えました。 ヒントをまだ解読できていないので、 libcds



ライブラリにはこの興味深いアルゴリズムの実装はありません。 さらに、キューが空にならない場合、つまり配列が無効にされない場合、アルゴリズムは配列スロットリストから要素を削除することを意図していないため、削除された要素の無制限の蓄積の対象となります。 pop()



は、対応するスロットで現在のticket



を持つ要素を検索するだけですが、配列全体が無効化されるまで、リストからの要素の物理的な除外は発生しません。



要約すると、私たちは言うことができます：アルゴリズムは興味深いですが、メモリ管理は十分に明確に説明されていません。 さらなる研究が必要です。

セグメント化されたキュー

キューのスケーラビリティを向上させる別の方法は、プライマリの先入れ先出しプロパティ（FIFO）に違反することです。 それは本当に怖いですか？それはタスクに依存します：ある人にとっては、FIFOの厳格な順守が必須であり、他の人にとっては-特定の制限内では完全に受け入れられます。

もちろん、メインのFIFOプロパティに根本的に違反したくはありません。この場合、プールと呼ばれるデータ構造を取得します。この構造では、順序はまったく観察されませんpop()



オペレーションは要素を返します。 これはもはやターンではありません。 FIFO違反のあるキューの場合、この違反をいくつか保証したいと思います。たとえば、 pop()



操作は最初のK要素の1つを返します。 K = 2の場合、これは、要素A、B、C、D、...を持つキューの場合、 pop()



AまたはB pop()



返すことを意味します。このようなキューは、Kファクター-FIFO違反制限の値を強調するためにセグメント化またはK セグメント化と呼ばれます。 明らかに、厳密な（公正な）FIFOキューの場合、K = 1です。

私が知る限り、初めて、最も単純なセグメント化されたキューが、ロックフリーのデータ構造に課せられる要件の許容できる緩和に専念する作業で2010年に詳細に検討されました。 キューの内部構造は非常に単純です（上記の記事の図、K = 5）：



キューは単純に接続されたセグメントのリストであり、各セグメントはサイズがK個の要素の配列です。 Head



とTail



は、それぞれリストの最初と最後のセグメントを示します。 push()



操作は、テールセグメントの任意の空きスロットに新しい要素を挿入し、 pop()



操作は、ヘッドセグメントの任意の占有スロットから要素を抽出します。 このアプローチでは、Kセグメントのサイズが小さいほど、FIFOプロパティの違反が少なくなることは明らかです。 K = 1の場合、厳密キューを取得します。 したがって、Kを変えることにより、FIFOの違反の程度を制御できます。

説明したアルゴリズムでは、セグメントの各スロットは、空き、ビジー（要素を含む）、および「ガベージ」（要素がスロットから読み取られた）の3つの状態のいずれかになります。 pop()



操作はスロットを「ゴミ箱」状態にします。これは「空き」状態とは異なります。「ゴミ箱」状態はスロットの最終状態であり、そのようなスロットへの値の書き込みは許可されません。 これはアルゴリズムの欠点です。「ガベージ」状態のスロットは再利用できず、交互のpush() / pop()



などの典型的な操作シーケンスでも新しいセグメントの配布につながります。 この欠陥は別の作業で修正されましたが、コードはかなり複雑になりました。

探検

そのため、libcdには、キュー用の2つの新しいアルゴリズムFCQueueとSegmentedQueueの実装があります。 彼らのパフォーマンスを見て、それらに対処する価値があるかどうかを理解してみましょう。

残念ながら、前の記事のテストを実行したサーバーに他のタスクが読み込まれ、その後クラッシュしました。 あまり強力ではない別のサーバーでテストを実行する必要がありました-Linuxを実行する64Gのメモリを搭載した2 x 12コアAMD Opteron 1.5GHz（ほとんど無料）-95％でアイドル状態。



結果の視覚化を変更しました-Y軸に沿ったテスト実行時間の代わりに、1秒あたりのメガ操作の数（Mop / s）を延期しました。 このテストは古典的なプロデューサー/コンシューマーであるということを思い出させてください：2,000万回の操作-ペイロードエミュレーションなしの10Mプッシュと10Mポップ、つまり愚かなキューイング。 すべてのロックフリーキューテストは、ハザードポインターを使用してメモリを安全に解放します。







まず、余談：私たちは何のために努力していますか？ スケーラビリティについて何を得たいですか？



鉄が物理的に非常に多くのスレッドをサポートしている場合、理想的なスケーリングはスレッド数の増加に伴うMop / sの線形増加です。 本当に良い結果は、Mop / sがいくらか増加し、対数のようになります。 スレッド数の増加に伴ってパフォーマンスが低下した場合、アルゴリズムはスケーラブルではないか、またはいくつかの制限に対してスケーラブルです。



侵入型キューの結果（侵入型コンテナーは、STLのように、データのコピーではなく、データ自体へのポインターを含むという事実によって特徴付けられます。したがって、ロックフリーの世界ではマナーが悪いと考えられている要素のコピーにメモリを割り当てる必要はありません）。



Flat Combiningは無駄に実装されていないことがわかります。この手法は、他のアルゴリズムに対して非常に良い結果を示しています。 はい、それは生産性を向上させませんが、重大な沈下もありません。 さらに、重要なボーナスは、実際にプロセッサをロードしないことです。常に1つのコアのみが動作します。 他のアルゴリズムは、多数のスレッドで100％のCPU使用率を示します。

セグメント化されたキューは部外者であることがわかります。 おそらく、これは実装アルゴリズムの仕様によるものです：セグメントのメモリ割り当て（このテストでは、セグメントサイズは16）、永続的な割り当てにつながるセグメントスロットを再利用できない、boost :: intrusive :: slist on lockに基づくセグメントのリストの実装（2種類のロック-スピンロックとstd :: mutexを試しました。結果は実質的に同じです）。

私は、主なブレーキが偽りの共有であるという希望を持っていました。 セグメント化されたキューの実装では、セグメントは要素へのポインタの配列でした。 セグメントサイズが16の場合、セグメントは16 * 8 = 128バイト、つまり2つのキャッシュラインを占有します。 最初と最後のセグメントのフローが常に一定であるため、偽共有は完全に成長していることがわかります。 そのため、アルゴリズムに追加のオプション-必要なパディングを導入しました。 パディング=キャッシュラインサイズ（64バイト）の場合、セグメントサイズは16 * 64 = 1024バイトに増加しますが、この方法で誤った共有を排除します。 残念ながら、パディングがSegmentedQueueのパフォーマンスに実質的に影響を与えないことが判明しました。 おそらく、この理由は、セグメントセル検索アルゴリズムが確率的であるため、ビジーセルを読み取ろうとする試みが多く失敗する、つまり、再び誤った共有が行われるためです。 または、偽共有はこのアルゴリズムの主な障害ではなく、真の理由を探す必要があります。



損失にもかかわらず、興味深い観測が1つあります。スレッド数が増加しても、SegmentedQueueはパフォーマンスの低下を示しません。 これは、このクラスのアルゴリズムにある種の視点があるという希望を与えます。 それらを別々に、より効率的に実装する必要があります。



STLのようなキューの場合、要素のコピーを作成すると、同様の図が表示されます。





最後に、楽しみのために、制限付きキューの結果を示します。これは、配列に基づくDmitry Vyukovアルゴリズム、侵入型の実装です。



スレッド数= 2（リーダー1つとライター1つ）の場合、このキューには32 MOp / sが表示されますが、これはチャートに収まりませんでした。 スレッドの数が増えると、パフォーマンスの低下も観察されます。 言い訳として、Vyukovのキューの場合、偽共有も非常に重要な抑制要因になる可能性がありますが、キャッシュラインに沿ったパディングを含むオプションはまだlibcdsにありません。







結論として、私は興味深い観察結果に注目したいと思います。 上記のテストでは、リーダーとライターのペイロードはありません。目標は、キューをプッシュしてそこから読み取ることです。 実際のタスクでは、常に何らかの種類の負荷が発生します。キューから読み取ったデータを使用して何かを行い、キューに入れる前にデータを準備します。 ペイロードはパフォーマンスの低下につながるように思われますが、実際には、これは常にそうではないことが示されています。 ペイロードがMOp / s オウムの著しい増加につながることを繰り返し観察しました。 理由は、内部キャッシュ同期プロトコルをアンロードしているように思えます。P.McKenneyをもう一度参照してください。 結論は、実際のタスクでテストする必要があることを示唆しています。





この記事では、キューに専念する作業のごく一部に触れ、動的（無制限）のみ、つまり要素数を制限することなく触れました。 先ほど言ったように、キューは研究者にとってお気に入りのデータ構造の1つです。 他の多くの作品が残っています-限られた（制限された）キュー、タスクスケジューラで使用されるワークスティールキュー、単一のコンシューマーまたは単一のプロデューサーキューについて-そのようなキューのアルゴリズムは1人のライターまたはリーダーによって大幅に研ぎ澄まされており、したがって、多くの場合よりシンプルで/またははるかに生産的-など など



大きなタイムラグにもかかわらず、キューとスタックの話を論理的な終わりに持っていくことができてうれしいです。これらはロックフリーのアプローチや最新のプロセッサのデータ構造にとって最も友好的ではなく、私にとってあまり興味深いものではないからです。

私たちの前にはもっとエキサイティングな構造があります-連想コンテナ（セット/マップ）、特に美しいマップを持つハッシュマップ、そしてスケーラビリティの点でもっと感謝しています。

続きが続くと思います...