2月27〜28日に開催された最初のC ++ 2015ロシア会議で講演するよう招待されたことを光栄に思います。 私は非常にwas慢だったので、本来あるべきものの代わりに2時間話すように頼み、最も興味のあるトピックである競争力のある連想コンテナについて述べました。 これらは、ハッシュセット/マップおよびツリーです。 オーガナイザーsermpは前進しました。
このような困難なテストパフォーマンスに備える方法 1つ目は、プレゼンテーション、つまり、できればトピックに近い写真の束を描くことです。 しかし、写真を2時間音声で伝える必要もあります。これをすべて覚えるにはどうすればよいでしょうか 思いやりのある「eeeemmmmm」、「here we see」、「this slide is shown」、ナレーションの一貫性のない飛躍、および母国語の所有という観点から話者をあまり良くない側面から特徴付けるその他のことを避ける方法-プレゼンテーションにコードはなく、写真のみ）？
もちろん、スライドを見て、考えを書き留める必要があります。 そして、何かが書かれていれば、公開するのは悪くないでしょう。 そして、あなたが公開するなら、ハブで
だから、 C ++ 2015ロシアをきっかけに！ 著者のプレゼンテーションは、著者の舌に縛られた舌がなく、いくつかの部分でイベントの前に書かれたトピックのカットや逸脱がないことを願っています。

C ++プログラマとして、コンテナ/ライブラリ/スタック/デッキ/リストではなく、連想コンテナ-ハッシュセット/マップ、std :: unordered_set / map、trees、つまりstd ::を使用しなければならなかったコンテナの標準ライブラリのほとんどすべてセット/マップ。 ご存じのように、C ++ 11標準では、このようなコンテナでのスレッドセーフな動作が保証されていますが、非常に弱い-読み取り専用で、変更はすべて-外部ロックでのみ可能です！ 実際には、このような保証はほとんどありません。読み取り専用マップがある場合、ソートされた配列を作成し、バイナリ検索を使用して検索する可能性が高いためです。いいね
外部同期を必要とせずに並行マップコンテナを実装することは可能ですか？ この質問を勉強しましょう。
ウォームアップするために、ハッシュマップの内部構造を見てみましょう。

ハッシュテーブル

衝突のリストを持つ最も単純なハッシュマップの内部構造は非常に原始的です。配列T[N] 、その各要素はリストです。 テーブルへのエントリ（インデックス）は、キーのハッシュ値です。 同じハッシュ（モジュロN ）を持つすべてのキーは、衝突リストと呼ばれる同じリストに分類されます。



一般的に、ここで最も重要なことはハッシュ関数の中に隠されています。 多くのキーに対して正しいハッシュ関数が選択されている場合にのみ、ハッシュマップは適切に機能します。 「修正」-これは、まず第一に、表のセル内の「十分に分散した」キーを意味します。 しかし、競争のレベルを高めるという観点からは、ハッシュ関数が内部にどのように配置されているかは問題ではないため、これ以上説明しません。
写真を見ると、通常のハッシュマップを競合させる方法をすぐに推測できます。ハッシュマップ全体へのアクセスをブロックする代わりに、テーブルT[N]の各セルのレベルでブロックできます。 したがって、衝突T[i]特定の各リストでの作業はシリアル化されますが、異なるリストT[i]およびT[j] （ i != j ）での作業は並行して実行できます。 この手法は、 M。HerlihyおよびNir ShavitのThe Art of Multiprocessor Programmingで説明されており、ストライピングと呼ばれます。

縞模様の地図

したがって、ストライピング手法では、 Lock[N]配列とT[N]ハッシュテーブル自体の2つの配列があります。 最初は、これら2つの配列のサイズは同じです（これは重要な要件であり、後で説明します）。 操作の内部アルゴリズムは単純です。任意の操作（挿入/消去/検索）で、 N法iキーのハッシュ値iを計算し、 Lock[i]ミューテックスをLock[i]し、リストT[i]操作を実行します。 しかし、1つの「しかし」があります。ハッシュテーブルは時々拡張する必要があります。 拡張の必要性の基準は、いわゆる負荷係数です：ハッシュマップの要素数とハッシュテーブルのサイズN比率。 テーブルを展開しない場合、コリジョンリストは非常に大きくなり、ハッシュマップのすべての利点はカボチャに変わります：操作の複雑さについてO（1）を評価する代わりに、O（S / N）を取得します。Sはテーブル内の要素の数です。 S >> Nおよび定数Nの場合、O（S）、つまり線形検索の複雑さと同等です。 これは受け入れられません。 この現象に対処するには、再ハッシュが必要です。負荷係数があるしきい値を超えた場合はNを増やし、新しいハッシュ値std::hash(key) % N'ハッシュテーブルを再構築します。
ストライプマップの再ハッシュアルゴリズムは次のとおりです。



まず、すべてのミューテックスを左から右にロックします。 次に、Nを整数回増やします（整数が重要です。以下を参照）。ハッシュテーブルを再構築し、最後に、すべてのミューテックスを右から左へ逆順にアンロックします。 デッドロックの主な理由は、いくつかのミューテックスのロック/ロック解除順序を遵守しないことであることを忘れないでください。

ここですべてのミューテックスをロックすることは重要です。 再ハッシュはかなり難しい操作であり、新しいテーブルT[N']のセル間でキーを再配布します。
上記のハッシュテーブルのサイズを増やすことについて話しましたが、 Lock[N]配列のサイズを増やすことについては何も言わなかったことに注意してください-それは偶然ではありません。事実はロック配列のサイズが変わらないということです。



Lock配列とT配列のサイズが異なる場合、原則として 、同じセルT[k]が異なるLock[i]およびLock[j]ミューテックスに対応する場合、状況は可能です。 これが受け入れられないためには、次のことが必要です。

1. 最初は、 Lock配列とT配列のサイズは一致し、 N等しくなります
2. 再ハッシュするときN'配列Tの新しいサイズN' N' = k * Nとして計算されます。ここで、 kは自然数（通常は2）です。

これらの条件下では、配列Tサイズは常にLock配列のサイズの倍数です（変更されません）。 算術モジュロの特性に基づいて、この場合、同じセルT[k] が異なるLock[i]およびLock[j]ミューテックスに対応できないことを証明するのは簡単です。

ストライピングアルゴリズムは、ツリーなどの他のデータ構造に簡単に拡張できます。



考え方は非常に単純ですLock[L] mutex配列の各要素はそのツリーを保護します。 Lock[L]への入力は、キーのハッシュ値（モジュロL ）です。 ロックLock[i]すると、対応するツリーにアクセスし、必要なアクションを実行します。

ストライピング技術は悪くありませんが、ロックフリーのデータ構造に関する一連の記事に関して重大な欠陥があります-ブロック可能です。 ハッシュマップのロックフリーアルゴリズムを考え出すことは可能ですか？..

ロックフリーの順序付きリスト

ハッシュマップの内部構造をもう一度見てみましょう。



再ハッシュの質問を残している限り、ハッシュテーブル内の要素の数をアプリオリに知っていて、キーのセットに対して適切なハッシュ関数を持っていると仮定します。 次に、ロックフリーハッシュマップを作成するには、ロックのない衝突のリストが少し必要です。 衝突のリストは、順序付けされた（キーによる）単純に接続されたリストにすぎません。 T. HarrisとM. Michaelの後、それを構築しようとします。
ロックフリーリストの検索は非常に簡単です。リストの先頭から順に直線的にウォークスルーします。 アトミック操作と安全な削除スキーム （ハザードポインター、 ユーザースペースRCUなど）の1つを使用することを考えると、検索アルゴリズムは順序付きリストでの通常の検索とそれほど変わりません（実際、コードを見ると強力ですが、これはロックフリーの料金です）。
新しい要素を挿入することも問題ではありません。



挿入位置を探し（順序付きリストがあることを思い出してください）、新しい要素を作成し、単一のCASプリミティブで挿入します（compare-and-swap、 std::compare_exchangeでもありstd::compare_exchange ）。
削除も非常に簡単です：



削除される要素を線形的に探し、CASによってアトミックに、先行要素から後続要素へのポインタをスローします。
問題は、これらすべてが同時に並行して行われたときに始まります。スレッドAはキー3の要素を削除し、スレッドBはキー4を挿入します。



スレッドAとBは同時に検索します。 同時に、削除（A）および挿入（B）で見つかった位置をローカル変数に記憶します。 次に、スレッドAがリストから3を安全に削除しました。たとえば、この時点でスレッドBは押し出されて飲まれました。 さらに、ストリームBはオペレーティングシステムによって計画され、キー4の挿入作業を続行します。リスト内のローカル変数（リスト内のiprevおよびinext位置が既にあり、要素を挿入するアトミックCASプリミティブを実行します。 リストからすでに除外されているキー3のアイテムの後！ （ハザードポインター/ RCUは、要素3がまだ物理的に削除されていないことを保証します。つまり、「ガベージアクセス」を受け取りませんが、3はスレッドAによってリストから既に削除されています）。 すべてがエラーなしで行われたため、キー4の要素が失われ、さらにメモリリークが発生しました。

T.ハリスは2001年にこの問題のエレガントな解決策を見つけました。 彼は、要素の2段階の削除を提案しました：第1段階- 論理削除 -要素をリストから除外せずに削除済みとしてマークし、第2段階- 物理的除外 -要素をリストから除外します（第3段階-物理削除 -安全なメモリ削除スキーム-ハザードポインターRCUまたは同様）。 論理削除の意味は、CAS が機能しないように、削除する要素にマークを付けることです。 Harrisは、 next要素ポインターの最下位ビットを使用することを提案しました。 実際、最新のアーキテクチャ（プロセッサとOSの両方）では、データは4（32ビットの場合）または8（64ビットの場合）バイトの境界に揃えられているため、ポインターの下位2または3ビットは常にゼロであり、ビットフラグとして使用できます。 このトリックには、 ポインターとマークされた独自の名前が付けられており、ロックフリープログラミングで広く使用されています。
マーク付きポインターを使用すると、並列挿入/削除は次のようになります。



スレッドAは、要素3を論理的にリモートとしてマークしますfound->nextポインターの下位ビットを1に設定します。 これで、3の後に4を挿入しようとするスレッドBは失敗します3.nextマークされていないと思われるため、CASは機能しません。
マークされたポインターメソッドの価格は、アイテムが削除されたときの追加のCAS呼び出しです。
上記のすべてが不要で、削除されたアイテムのnextポインターをnullptr設定するだけではるかに高速で簡単に思えます-挿入のCASは機能しません。 はい、簡単ですが、これらは2つの独立した操作です。1つは例外で、もう1つはnextゼロ化です。 また、2つの操作がある場合、誰かがそれらの間をくさび止めて、既に除外されている操作の後に新しい要素を挿入できます。 したがって、エラーの可能性を減らすだけで、除外することはしません。 ロックフリーのしかめっ面：すべてを可能な限りアトミックに実行する必要がありますが、いずれにしても、コンテナの内部構造に違反することはありません。



そのため、ロックフリーハッシュマップを実装できる順序付きリストのロックフリーアルゴリズムを分析しました。 このアルゴリズムの欠点は、再ハッシュが提供されないことです。つまり、このようなコンテナ内のS要素の推定数と最適な負荷係数を事前に知る必要があります。 次に、ハッシュテーブルのサイズN T[N]は、 S / load factor等しくなりS / load factor 。 それにもかかわらず、これらの制限にもかかわらず、むしろそれらのおかげで、そのようなアルゴリズムは再ハッシュのオーバーヘッドがないため、最も高速で最もスケーラブルなアルゴリズムの1つです。
私の実験の結果によると、適切な負荷係数は2〜4です。つまり、衝突のロックフリーリストにはそれぞれ平均2〜4個の要素が含まれています。 負荷係数= 1（衝突リストは平均で1つの要素で構成されます）の場合、結果はわずかに良くなりますが、実際に縮退した衝突リストのメモリオーバーヘッドが増えます。
次の記事では、元々再ハッシュをサポートし、ここで説明したロックフリーの順序付きリストに基づくアルゴリズムを検討します。