スレッドセーフstd ::ロックのないマップパフォーマンスを備えたマップ

使用例とスレッドセーフポインターと競合のない共有ミューテックスのテスト

この記事では、追加の最適化、使用例、および最適化された共有ミューテックスcontfree_safe_ptr <T>で開発したスレッドセーフポインターのテストの例を示します。これはsafe_ptr <T、contention_free_shared_mutex <>>と同等です。

最後に、スレッドセーフポインターのテストと、Intel Core i5 / i7、Xeon、2 x Xeonプロセッサ上のlibCDSの最高のロックフリーアルゴリズムのテストの比較グラフを示します。



関連する3つの記事：

1. オブジェクトをスレッドセーフにする
2. stdの高速化:: shared_mutexを10倍
3. スレッドセーフstd ::ロックのないマップパフォーマンスを備えたマップ

→ 私の英語の記事

→ 3つの記事すべての例とテスト



リンクでソリューションを比較するlibCDSライブラリを見つけることができます： github.com/khizmax/libcds

この記事のすべてのテストは、libCDSからの次のコミットを使用します。github.com/ khizmax / libcds / tree / 5e2a9854b0a8625183818eb8ad91e5511fed5898

異なる粒度のロック

最初に、テーブル（構造体の配列）を操作する例を使用して、共有ミューテックスを最適に使用する方法を示します。 産業用DBMSの経験を見てみましょう。 たとえば、MSSQL DBMSでは、さまざまな粒度のロックが使用されます。ロック：1つ以上の行、ページ、エクステント、テーブルの1つのセクション、インデックス、テーブル全体、データベース全体。 https://technet.microsoft.com/en-us/library/ms189849(v=sql.105).aspx



実際、長い間1つの行を操作しており、この時点で行が別のスレッドによって変更されないことが重要な場合、この時点でテーブル全体をロックする必要はありません-1行のみをロックするだけで十分です。

• 共有ロックでテーブル全体をロックします
• 目的の行または複数の行を探しています
• 次に、見つかった行をブロックします
• テーブルのロックを解除します
• ロックされた行での作業

その後、他のスレッドが残りの行を並行して処理できるようになります。

これまで、テーブルレベルのロックのみを使用しました。 1つ以上のテーブルをブロックしました。



または、式で使用されるすべてのテーブルは、完了するまで自動的にロックされていました。

(*safe_map_1)["apple"].first = "fruit"; // locked Table-1 (safe_map_1) // unlocked Table-1 safe_map_1->at("apple").second = safe_map_1->at("apple").second * 2; // locked Table-1 (safe_map_1) // unlocked Table-1 safe_map_1->at("apple").second = safe_map_2->at("apple").second*2; // locked Table-1(safe_map_1) and Table-2(safe_map_2) // unlocked Table-1 and Table-2
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

その他の場合、RAIIロックオブジェクトを使用して、これらのロックのブロックスコープが終了するまで（破棄されるまで）、1つ以上のテーブルを手動でブロックしました。

 { std::lock_guard<decltype(safe_map_1)> lock(safe_map_1); // locked Table-1 (safe_map_1) (*safe_map_1)["apple"].first = "fruit"; safe_map_1->at("apple").second = safe_map_1->at("apple").second * 2; // unlocked Table-1 } { lock_timed_any_infinity lock_all(safe_map_1, safe_map_2); // locked Table-1(safe_map_1) and Table-2(safe_map_2) safe_map_1->at("apple").second = safe_map_2->at("apple").second*2; //locked Table-1(safe_map_1) and Table-2(safe_map_2) safe_map_1->at("potato").second = safe_map_2->at("potato").second*2; //locked Table-1(safe_map_1) and Table-2(safe_map_2) // unlocked Table-1 and Table-2 }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

挿入するインデックスをランダムに選択し、次に4つの操作（挿入、削除、更新、読み取り）のいずれかをランダムに選択して、 contfree_safe_ptr <std :: map>型のスレッドセーフオブジェクトで実行する例を見てみましょう。



例：[37] coliru.stacked-crooked.com/a/5b68b65bf2c5abeb



この場合、テーブルに次のロックを課します。

• 挿入-排他的ロック
• 削除-排他的ロック
• 更新-排他的ロック
• 読み取り-共有ロック

更新または読み取り操作の場合、次のことを行います。

1. テーブル全体をロックします（更新の場合はxlock、読み取りの場合はslock）
2. 必要な行を検索し、読み取りまたは変更します
3. テーブルのロックを解除します

この例の1つの反復のコードは1です。

  int const rnd_index = index_distribution(generator); // 0 - container_size int const num_op = operation_distribution(generator);// insert_op, update_op, delete_op, read_op switch (num_op) { case insert_op: { safe_map->emplace(rnd_index, (field_t(rnd_index, rnd_index))); // insert with X-lock on Table break; } case delete_op: { size_t erased_elements = safe_map->erase(rnd_index); // erase with X-lock on Table } break; case update_op: { auto x_safe_map = xlock_safe_ptr(safe_map); // X-lock on Table auto it = x_safe_map->find(rnd_index); if (it != x_safe_map->cend()) { it->second.money += rnd_index; // still X-lock on Table (must necessarily be) } } break; case read_op: { auto s_safe_map = slock_safe_ptr(safe_map); // S-lock on Table auto it = s_safe_map->find(rnd_index); if (it != s_safe_map->cend()) { volatile int money = it->second.money; // still S-lock on Table (must necessarily be) // volatile here only to avoid optimization for unused money-variable } } break; default: std::cout << "\n wrong way! \n"; break; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここで、更新操作中にテーブルがロックロック（排他的）ではなく、読み取りロック（共有）によってロックされるようにします。 これにより、以前に開発した「書き込み競合のない共有ミューテックス」を使用する際の更新操作が大幅に加速されます。

この場合、多くのスレッドが同じテーブルで更新操作と読み取り操作を同時に実行できます。 たとえば、1つのスレッドが1行を読み取り、別のストリームが別の行を変更します。 しかし、あるスレッドが別のストリームが読み取るのと同じ行を変更しようとする場合、データ競合を回避するために、読み取り時および変更時に行自体をブロックする必要があります。



例：[38] coliru.stacked-crooked.com/a/89f5ebd2d96296d3



更新または読み取り操作の場合：

1. 共有ロックでテーブル全体をロックします
2. 目的の行または複数の行を探しています
3. 次に、見つかった行をブロックします（更新の場合はxlock、読み取りの場合はslock）
4. そして、ロックされた行（X / Sロック）とロックされたテーブル（Sロック）で作業します
5. ラインのロックを解除
6. テーブルのロックを解除します

Diff-変更点：







この例の1つの反復のコードは2です。

  int const rnd_index = index_distribution(generator); // 0 - container_size int const num_op = operation_distribution(generator);// insert_op, update_op, delete_op, read_op switch (num_op) { case insert_op: { safe_map->emplace(rnd_index, (field_t(rnd_index, rnd_index))); // insert with X-lock on Table break; } case delete_op: { size_t erased_elements = safe_map->erase(rnd_index); // erase with X-lock on Table } break; case update_op: { auto s_safe_map = slock_safe_ptr(safe_map); // S-lock on Table auto it = s_safe_map->find(rnd_index); if (it != s_safe_map->cend()) { auto x_field = xlock_safe_ptr(it->second); x_field->money += rnd_index; // X-lock on field, still S-lock on Table (must necessarily be) } } break; case read_op: { auto s_safe_map = slock_safe_ptr(safe_map); // S-lock on Table auto it = s_safe_map->find(rnd_index); if (it != s_safe_map->cend()) { auto s_field = slock_safe_ptr(it->second); volatile int money = s_field->money; // S-lock on field, still S-lock on Table (must necessarily be) // volatile here only to avoid optimization for unused money-variable } } break; default: std::cout << "\n wrong way! \n"; break; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここでは、スレッドセーフな文字列処理のために、safe_objを使用しました。 Safe_obj <T>には、safe_ptr <T>のように、タイプTのオブジェクトが含まれていますが、それへのポインタは含まれていません。 したがって、safe_objを使用する場合、safe_ptrで必要なように、オブジェクト自体にメモリを個別に割り当ててアトミック参照カウンターを変更する必要はありません。 したがって、safe_ptrを使用するよりもsafe_objを使用すると、挿入と削除の操作がはるかに速くなります。



safe_objをコピーするとき、コピーされるのはオブジェクトポインタではなく、オブジェクト自体がコピーされ、以前にソースと最終的なsafe_objがロックされていることに注意する価値があります。



注：厳密に言えば、行全体をブロックするのではなく、探している行インデックスを除く行のすべてのフィールドをブロックします。 したがって、行ではなくオブジェクトフィールドに名前を付けました。 また、この方法で強調するために、1つの行だけでなく、別々のsafe_obj-objectsに配置すると、1つの行のフィールドもブロックできます。 これにより、異なるスレッドが異なるフィールドをブロックし、それらを並行して処理できるようになります。



ここで、さまざまな操作に次のロックを使用します。







この例は、多数の短時間の操作に対して非常に高速です。 ただし、行（フィールド）の変更または読み取りのプロセスでは、テーブルの読み取りロック（共有）を保持しています。 また、テーブルの行に対してまれではあるが非常に長い操作がある場合は、これらすべてが長時間テーブル全体でロックされます。



ただし、タスクのロジックに従って、あるスレッドが行を削除できるかどうか、別のスレッドが同じ行を読み取りまたは変更している場合は、行検索の期間だけテーブルをロックするだけで十分です。 また、別のスレッドが行を削除したときに解放されたメモリにアクセスしないようにするには、std :: shared_ptr <T>-アトミックスレッドセーフ参照カウンターを持つポインターを使用する必要があります。 この場合、この行へのポインタを持つスレッドがない場合にのみ、メモリが解放されます。



safe_objの代わりに、safe_ptrを使用して文字列を保護します。 これにより、ポインタを文字列にコピーし、safe_ptrに含まれるstd :: shared_ptr <T>のスレッドセーフ参照カウンタを使用できます。



例：[39] coliru.stacked-crooked.com/a/f2a051abfbfd2716



更新または読み取り操作の場合：

1. 共有ロックでテーブル全体をロックします
2. 目的の行または複数の行を探しています
3. 次に、見つかった行をブロックします（更新の場合はxlock、読み取りの場合はslock）
4. テーブルのロックを解除します
5. そして、必要な限りロックされたライン（X / Sロック）を使用します
6. ラインのロックを解除

Diff-変更点：







例3：

  int const rnd_index = index_distribution(generator); // 0 - container_size int const num_op = operation_distribution(generator);// insert_op, update_op, delete_op, read_op safe_ptr_field_t safe_nullptr; switch (num_op) { case insert_op: { safe_map->emplace(rnd_index, (field_t(rnd_index, rnd_index))); // insert with X-lock on Table break; } case delete_op: { size_t erased_elements = safe_map->erase(rnd_index); // erase with X-lock on Table } break; case update_op: { auto pair_result = [&]() { auto s_safe_map = slock_safe_ptr(safe_map); // S-lock on Table auto it = s_safe_map->find(rnd_index); if (it != s_safe_map->cend()) return std::make_pair(it->second, true); // found else return std::make_pair(safe_nullptr, false); // null-value }(); // unlock Table if(pair_result.second) { auto x_field = xlock_safe_ptr(pair_result.first); // X-lock on field x_field->money += rnd_index; // if a long time is read } // unlock field } break; case read_op: { auto pair_result = [&]() { auto s_safe_map = slock_safe_ptr(safe_map); // S-lock on Table auto it = s_safe_map->find(rnd_index); if (it != s_safe_map->cend()) return std::make_pair(it->second, true); // found else return std::make_pair(safe_nullptr, false); // null-value }(); // unlock Table if(pair_result.second) { auto s_field = slock_safe_ptr(pair_result.first); // S-lock on field volatile int money = s_field->money; // if a long time is read // volatile here only to avoid optimization for unused money-variable } // unlock field } break; default: std::cout << "\n wrong way! \n"; break; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

適切に設計されたマルチスレッドプログラムは、共有オブジェクトへの短い呼び出しを使用するため、将来、短い読み取り操作の最後ではなく最後から2番目の例を使用します。

イディオム周辺の実行の短所

考えられる問題を見て、コードを批判しましょう。 前の章では、関数を使用して更新操作と読み取り操作のブロックタイプを明示的に設定する、かなり便利で高性能な例を検討しました。

• slock_safe_ptr（） -読み取り専用
• xlock_safe_ptr（） -読み取りおよび変更用

ここでは、これらの関数によって返されるlock_objオブジェクトの寿命が終了するまでロックが保持されます。auto lock_obj = slock_safe_ptr（sf_p）;

ただし、挿入および削除操作では、暗黙的なロックが使用されました。 safe_ptr <std :: map>オブジェクトは、Execute Around Pointerイディオムを使用して自動的にブロックされ、挿入または削除操作の完了後すぐにロック解除されました。



例：[40] coliru.stacked-crooked.com/a/89f5ebd2d96296d3



ただし、更新操作と読み取り操作で明示的なロックを使用することを忘れることがあります。 この場合、検索操作が完了した直後にsafe_ptr <std :: map>のロックが解除され、引き続き使用します：

1. 別のスレッドによって無効にできるイテレータが見つかりました
2. または、別のスレッドで削除できる見つかったアイテム

この問題を部分的に解決するには、safe_ptr <>およびsafe_obj <>の代わりにsafe_hide_ptr <>およびsafe_hide_obj <>を使用できます。これらはポインタの周囲で実行を使用せず、明示的なブロック後にのみクラスメンバーにアクセスできます：

  safe_hide_obj<field_t, spinlock_t> field_hide_tmp; //safe_obj<field_t, spinlock_t> &field_tmp = field_hide_tmp; // conversion denied - compile-time error //field_hide_tmp->money = 10; // access denied - compile-time error auto x_field = xlock_safe_ptr(field_hide_tmp); // locked until x_field is alive x_field->money = 10; // access granted
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

例：[41] coliru.stacked-crooked.com/a/d65deacecfe2636b



以前の場合、間違いを犯して次のように書くことができます- 間違ったコード：

  auto it = safe_map->find(rnd_index); // X-lock, find(), X-unlock if (it != s_safe_map->cend()) volatile int money = it->second ->money; // X-lock, operator=(), X-unlock
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これで、この呼び出しはコンパイルされず、オブジェクトの明示的なブロックが必要になります- 正しいコード：

  auto s_safe_map = slock_safe_ptr(safe_map); // S-lock on Table auto it = s_safe_map->find(rnd_index); if (it != s_safe_map->cend()) { auto s_field = slock_safe_ptr(it->second); volatile int money = s_field->money; // S-lock on field, still S-lock on Table // volatile here only to avoid optimization for unused money-variable } // S-unlock Table, S-unlock field
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ただし、ロックを一時オブジェクトとして使用する危険性はまだあります 。これは正しくありません 。

  auto it = slock_safe_ptr(safe_map)->find(rnd_index); // S-lock, find(), S-unlock if (it != s_safe_map->cend()) { volatile int money = slock_safe_ptr(it->second)->money; // S-lock, =, S-unlock }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次の選択肢があります。

• safe_ptrとsafe_objを使用して、オブジェクトを明示的または自動的に（イディオムの周囲で実行）ブロックできるようにします。
• または、 safe_hide_ptrとsafe_hide_objを使用して、オブジェクトを明示的にロックする機能のみを残します

何を選択するかはあなた次第です：

• 便利な自動ブロックを使用する（イディオム周辺で実行）
• または、オブジェクトを明示的にロックするように要求することにより、エラーの可能性をわずかに減らします

さらに、次の関数がstd :: map <>のC ++ 17標準に追加される予定です。

• insert_or_assign（） -要素があれば割り当て、そうでなければ挿入
• try_emplace（） -要素がない場合、要素を作成します
• merge（） -2つのマップを1にマージします
• extract（） -要素を取得し、マップから削除します

このような関数の導入により、イテレーターを使用せずに頻繁に使用される複合操作を実行できます。この場合、イディオムの実行を使用すると、これらの操作のスレッドセーフが常に保証されます。 一般に、すべてのコンテナ（std :: arrayおよびstd :: vector arrayを除く）のイテレータを避けることは、マルチスレッドプログラムを構築する上で大きな助けになります。 反復子を使用する頻度が少ないほど、このスレッドまたは別のスレッドによって無効にされている反復子にアクセスする可能性は低くなります。 ただし、イテレータの概念はマルチスレッドの概念と矛盾しません。たとえば、DBMS（Oracle、MSSQL）はカーソル （イテレータのアナログ）およびトランザクションの異なるレベルの分離（マルチスレッドの異なる整合性）をサポートします。



しかし、あなたが選ぶものは何でも：イディオムの周りで実行を使用し、 safe_hide_ptrに明示的なロックを使用し 、それらを拒否し、標準のstd :: mutexロックを使用します...または独自のロックフリーアルゴリズムを記述します-あなたは常に間違いを犯す多くのオプションがあります。

テーブルのパーティション-パフォーマンスをさらに向上させる

産業用リレーショナルDBMSの経験に戻りましょう。 たとえば、DBMSでは、テーブルパーティションを使用してパフォーマンスを向上させることができます。 この場合、テーブル全体ではなく、使用するパーティションのみをブロックできます： https : //technet.microsoft.com/en-us/library/ms187504(v=sql.105).aspx



削除および挿入操作のDBMSでは、テーブル全体は通常ロックされていませんが、削除操作の場合は常にそうです。 ただし、挿入操作の場合、データを非常に高速にテーブルに読み込むことができます。これは、排他的なテーブルロックが不可欠な条件です。

• MS SQL（dbcc traceon（610、-1））：INSERT INTO sales_hist WITH（ TABLOCKX ）
• Oracle：INSERT / * + APPEND * / INTO sales_hist
  
  https://docs.oracle.com/cd/E18283_01/server.112/e17120/tables004.htm#i1009887
  
  

  Direct-Path INSERTのロックに関する考慮事項
  
  ダイレクトパスINSERT中に、データベースはテーブル（またはパーティションテーブルのすべてのパーティション）の排他ロックを取得します。 その結果、ユーザーはテーブルに対して同時の挿入、更新、または削除操作を実行できなくなり、インデックスの同時作成および構築操作は許可されません。 ただし、同時クエリはサポートされていますが、クエリは挿入操作の前に情報のみを返します。

なぜなら 私たちのタスクは、最速のマルチスレッドコンテナーを作成することです。その後、挿入/削除操作でコンテナー全体をブロックしました。 しかし、今度はコンテナの一部のみをブロックしてみましょう。



独自のパーティション順序付き連想配列partition_mapを実装して、パフォーマンスがどれだけ向上するかを見てみましょう。 現在必要なセクションのみをブロックします。



意味は次のとおりです。std:: map <safe_ptr <std :: map <>>>

ここで、最初のstd ::マップは定数であり、セクション（サブテーブル）を含みます。

これは、セクション数がコンストラクターで設定され、それ以上変更されない非常に単純化された例です。



各セクションは、スレッドセーフな連想配列safe_ptr <std :: map <>>です。



最大のパフォーマンスを得るには、セクションの数とその範囲は、各セクションにアクセスする確率が同じになるようにする必要があります。 キー範囲が0〜1000000で、範囲の先頭への読み取り/更新/挿入/削除リクエストの確率が範囲の終わりよりも大きい場合、キー値が小さいセクションは大きく、範囲は小さくする必要があります。 たとえば、3つのセクション：[0-100000]、[100001-400000]、[400001-1,000,000]。



しかし、この例では、クエリキーが均一に分布していると仮定します。

セクション範囲は2つの方法で設定できます。

• safe_map_partitioned_t <std :: string、int> safe_map {"a"、 "f"、 "k"、 "p"、 "u"};

safe_map_partitioned_t <int、int>（0、100000、10000）;

//値0〜100000の境界と各セクション10000のステップを設定します



コンテナにアクセスするときに、キーがセクションの境界を超えた場合、リクエストは最も近いセクションに移動します-つまり プログラムは正常に動作します。



例：[42] coliru.stacked-crooked.com/a/fc148b08eb4b0580



また、最大のパフォーマンスを得るには、 safe_ptr <>内で以前に実装された「コンテンションフリーの共有ミューテックス」を使用する必要があります。 意味： std :: map <contfree_safe_ptr <std :: map <>>>

前の例のコードを使用して、前の章のcontfree_safe_ptrコードを追加します。

置換：safe_map_partitioned_t <std :: string、std :: pair <std :: string、int >>

To：safe_map_partitioned_t <std :: string、std :: pair <std :: string、int>、contfree_safe_ptr>

例：[43] coliru.stacked-crooked.com/a/23a1f7a3982063a1

このクラスsafe_map_partitioned_t <>は、「楽しみのためだけ」に作成しました。 実際のプログラムで使用することは推奨されません。 例を示しました-contfree_safe_ptr <>ポインターとcontention_free_shared_mutex <>ロックに基づいて独自のアルゴリズムを実装する方法。

使い方

まず、リポジトリのルートからsafe_ptr.hファイルをダウンロードします： github.com/AlexeyAB/object_threadsafe

次に、このファイルをcppファイルに含めます： #include "safe_ptr.h"

最適なユースケースとして、上記の例2に焦点を当てます-シンプルで生産性が高い：

 struct field_t { int money, time; field_t(int m, int t) : money(m), time(t) {} field_t() : money(0), time(0) {} }; typedef safe_obj<field_t, spinlock_t> safe_obj_field_t; // thread-safe ordered std::map by using execute around pointer idiom with contention-free shared-lock contfree_safe_ptr< std::map<int, safe_obj_field_t > > safe_map_contfree; bool success_op; switch (num_op) { case insert_op: slock_safe_ptr(test_map)->find(rnd_index); // find for pre-cache to L1 with temprorary S-lock test_map->emplace(rnd_index, field_t(rnd_index, rnd_index)); break; case delete_op: slock_safe_ptr(test_map)->find(rnd_index); // find for pre-cache to L1 with temprorary S-lock success_op = test_map->erase(rnd_index); break; case read_op: { auto s_safe_map = slock_safe_ptr(test_map); // S-lock on Table (must necessarily be) auto it = s_safe_map->find(rnd_index); if (it != s_safe_map->cend()) { auto x_field = xlock_safe_ptr(it->second); volatile int money = x_field->money; // get value x_field->money += 10; // update value } } break; default: std::cout << "\n wrong way! \n"; break; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

挿入と削除-マップの変更 ： 共有ロックslock_safe_ptr（）は可能な限り高速であるため、変更（insert_opまたはdelete_op）の前でも、find（）操作の直後にロック解除されるslock_safe_ptr（）を使用して、削除する必要がある要素または挿入する必要がある要素に最も近い要素を見つけます。 この操作の結果を直接使用するわけではありませんが、このアイドル操作は、後続のマップ変更のためにL1キャッシュにキャッシュする必要があるデータをプロセッサーに伝えます。 次に、test_map-> emplace（）を挿入するか、test_map-> erase（）を削除します。これらの操作は、実行中に排他ロックを自動的に呼び出します。 挿入/削除-ほぼすべてのデータが既にこのカーネルのキャッシュにあるため、すぐに発生しますが、大きなプラス-共有ロックを排他ロックに絶えず増やす必要はありませんプログラム）。



読み取りおよび更新-（マップの読み取り）および1つの要素の読み取りまたは変更 ：特定の例で読み取り（read_op）と呼ぶものは、マップから1つの要素を読み取り（マップから1行）変更します。 読み込む前に、マップに共有ロックslock_safe_ptr（）を課し、他のスレッドがマップ内の要素を削除または置換できないようにします。 s_safe_mapオブジェクトが存在する間、共有ロックを保持し、目的の要素を見つけて、この1つの要素のみに排他的なxlock_safe_ptr（）ロックを課し、それを読み取って変更します。 その後、スコープ{}を離れると、x_fieldオブジェクトが最初に破棄され、排他ロックが要素から削除されます。次に、s_safe_mapオブジェクトが破棄され、共有ロックがマップから削除されます。



コンパイラを使用すると、test_mapで任意の操作を実行できます-読み取りまたは変更し、そのメソッドを呼び出すことができます-この場合、排他ロックが自動的に適用されます。



ただし、コンパイラは、定数として宣言されたオブジェクト、または定数参照に割り当てられたオブジェクトの読み取りのみを許可しますauto const＆some_ptr = test_map; たとえば、 some_ptr-> find（）を呼び出すことができます。 共有ロックは式の実行時間全体に自動的に適用されますが、一定のリンクの場合、次のsome_ptr-> emplace（）を実行できません。 。 したがって、共有ロックによって自動的に保護されるまで、オブジェクトを変更することはできません。



slock_safe_ptr（test_map）を明示的にブロックする場合の同様の動作は、 slock_safe_ptr（test_map）-> find（）を実行できます。 しかし、slock_safe_ptr（test_map）-> emplace（）をコンパイルしようとすると; -間違いがあります。 これらはすべて、ロックの正しい自動選択とマルチスレッドプログラムの正しい操作を保証します。

このすべておよびさらに多くは、最初の記事で説明されています。

取得したsafe_ptr実装のパフォーマンス比較

中間結果を要約します。最適化により生産性がどれほど向上したかを見てみましょう。



パフォーマンスグラフは次のとおりです。1秒あたりの数百万の操作（MOps）の数と、変更操作の割合が0〜90％の場合です。変更中に、挿入、削除、更新の3つの操作のいずれかが同じ確率で実行されます（更新操作ではstd ::マップツリー自体は変更されませんが、行の1つのみが変更されます）。たとえば、15％の変更がある場合、これらは5％の挿入、5％の削除、5％の更新、85％の読み取りという操作になります。使用コンパイラ：g ++ 4.9.2（Linux Ubuntu）x86_64



このベンチマークは、Linux（GCC 4.9.2）およびWindows（MSVS2015）でダウンロードできます：github.com/AlexeyAB/object_threadsafe/tree/master/benchmark

LinuxでClang ++ 3.8.0でコンパイルするには、Makefileを変更する必要があります。



1つのサーバープロセッサIntel Xeon E5-2660 v3 2.6 GHzの16スレッドでテストする例を次に示します。まず最初に、安全な<map、contfree>＆rowlockというオレンジ色の行に興味があります。



複数のCPUがインストールされている場合、実行するコマンドラインは次の



とおり です。numactl --localalloc --cpunodebind = 0 ./benchmark 16



1つのCPUがインストールされている場合は、単に./benchmarkを実行します。





結論：

• 興味深いことに、contfree_safe_ptr <map>の共有contfreeロックは、safe_ptr <map、std :: shared_mutex>の一部としての標準std :: shared_mutexよりもはるかに高速です。
• , 15% std::mutex , std::shared_mutex ( safe_ptr<map,std::mutex> , safe_ptr<map,std::shared_mutex>)
• , 30% std:map – 1 thread contfree_safe_ptr<map>&rowlock. . - , .
• safe_map_partitioned<,,contfree_safe_ptr>, , «Just-for-fun» — .
• 15% , shared-mutex ( contfree_safe_ptr<map> & rowlock) 8.37 Mops, 10 , std::shared_mutex ( safe_ptr<map, std::shared_mutex>), 0.74 Mops.

「競合のない共有ミューテックス」ロックは、任意の数のスレッドで機能します。最初の70個のスレッドでは競合なし、後続のスレッドでは排他ロックとして機能します。グラフからわかるように、「排他ロック」のstd :: mutexでさえ、std :: shared_mutexよりも高速で、15％の変更があります。



また、遅延の中央値のグラフをマイクロ秒単位で示します。リクエストの半分には、この値より小さい遅延があります。



main.cppテストコードでは、次を設定する必要があります。const bool measure_latency = true;

実行するコマンドライン：numactl --localalloc --cpunodebind = 0 ./benchmark 16

• 興味深いことに、std :: map＆std :: mutexはsafe_ptr <map、std :: mutex>を中心に振動します。全体的に、safe_ptr <>を使用しても余分なオーバーヘッドは追加されず、パフォーマンスも低下しません。
• また、変更の60％から、contfree_safe_ptr <map>＆rowlockがcontfree_safe_ptr <map>よりも長い遅延を示すことも興味深いです。しかし、前のグラフから、変更操作の割合に関係なく、contfree_safe_ptr <map>およびrowlockの全体的なパフォーマンスが依然として高いことがわかりました。

contfree_safe_ptr <std :: map>と、異なるデスクトップCPU上のCDS-libのコンテナーのパフォーマンス比較

すべてのコアを使用した異なるデスクトップCPUでのパフォーマンス比較。

• 興味深いことに、ラップトップおよびデスクトップの場合、contfree_safe_ptr <map>は、CDS-libのロックフリーマップコンテナよりも優れたパフォーマンスを示します。
• «Just-for-fun» safe_map_partitioned<,,contfree_safe_ptr> 1.7 .

contfree_safe_ptr<std::map> CDS-lib server-CPU

異なる数のスレッドを使用した、1つのサーバーCPU上の異なるマルチスレッド連想配列のパフォーマンスの比較。



Linux（GCC 4.9.2）およびWindows（MSVS2015）の次のベンチマークをダウンロードできます。github.com/ AlexeyAB / object_threadsafe / tree / master / CDS_test

LinuxでClang ++ 3.8.0でコンパイルするには、Makefileを変更する必要があります。



同じマザーボード上に複数のXeonプロセッサがある場合、このテストの結果は、次のように実行することで再現できます



。numactl --localalloc --cpunodebind = 0 ./benchmark 16



1つのCPUがインストールされている場合は、単に./benchmarkを実行します

• , 16 , , lock-free CDS-lib , contfree_safe_ptr<map>. つまり lock-free . 16 , 8 , contfree_safe_ptr<map> , lock-free .
• «Just-for-fun»- safe_map_partitioned<,,contfree_safe_ptr> , , .

レイテンシの中央値は、リクエストの50％が実行された時間よりも速い時間です。



main.cppテストコードでは、次を設定する必要があります。const bool measure_latency = true;

実行するコマンドライン：numactl --localalloc --cpunodebind = 0 ./benchmark 16







contfree_safe_ptr <map>の遅延の中央値は、同時に競合するスレッドの最大8スレッドのロックフリーコンテナーの遅延とほぼ同じですが、競合する16スレッドでは悪化します。

実際のアプリケーションでのパフォーマンス。

実際のアプリケーションは、スレッド間のデータ交換だけで構成されているわけではありません。実際のアプリケーションの主な作業は各スレッドで個別に実行され、まれにしかスレッド間でデータが交換されません。



アプリケーションの実際の作業をシミュレートするには、最適化されていないforループを追加します（volatile int i = 0; i <9000; ++ i）;スレッドセーフコンテナへの各呼び出しの間。テストの開始時に、このサイクルを100,000回実行し、このサイクルを完了するのにかかる平均時間を測定します。 Intel XeonプロセッサE5-2686 v4 2.3 GHzでは、この実際の作業のシミュレーションには約20.5マイクロ秒かかります。



Linux（GCC 4.9.2）およびWindows（MSVS2015）のこのベンチマークは、次のリンクからダウンロードできます。github.com/ AlexeyAB / object_threadsafe / tree / master / Real_app_bench

LinuxでClang ++ 3.8.0でコンパイルするには、Makefileを変更する必要があります。



2プロセッササーバーでテストします：2 x Intel Xeon E5-2686 v4 2.3 GHz（Broadwell）、合計コア数：36物理コアと72論理コア（ハイパースレッディング）。



コンパイルして実行するには、次を実行します。

cd libcds

作る

cd ...

作る

./benchmark

• 標準std :: mutexおよびstd :: shared_mutexミューテックスを使用してstd :: mapを保護すると、最大16スレッドのロックフリーマップコンテナーに近いパフォーマンスが提供されます。しかし、その後、std :: mutex＆std :: mapおよびstd :: shared_mutex＆std :: mapのパフォーマンスは遅れ始め、32個のスレッドが低下し始めます。
• 最適化されたスレッドセーフポインターcontfree_safe_ptr <std :: map <>>を使用すると、1〜64の任意の数のスレッドでlibCDSライブラリのロックフリーマップコンテナーのパフォーマンスとほぼ同等のパフォーマンスが得られます。フロー間の交換は、平均で20マイクロ秒以下に1回行われます。

遅延の中央値を測定するには、main.cppテストコードで以下を設定する必要があります。const bool measure_latency = true;



Linuxで実行するには、次のように入力します。./benchmark

• 興味深いことに、64スレッドでは、std :: mutexはstd :: shared_mutexよりもパフォーマンスとメディアン遅延の両方が大きくなります。
• - contfree_safe_ptr<std::map<>> lock-free-map libCDS 1 64. , 20 .
• 64 30 , 20 — , 10 — . , 30% , contfree_safe_ptr<T> (MOPS -), lock-free libCDS.

libCDSのより単純なロックフリーおよび待機フリーのコンテナ（キュー、スタック...）は、ロックの実装よりも遅延が顕著に少なくなっています。



結論：

1. 同じコンテナでフローの競合が激しい場合、つまり ある時点で、平均で8個を超えるスレッドがコンテナにアクセスする場合、最良の解決策はCDSlibライブラリのコンテナを使用することです：github.com/khizmax/libcds
2. 必要なスレッドセーフコンテナがCDSlibにある場合は、それを使用します。
3. プログラムがストリーム間でデータを交換する以外に何かを行い、ストリーム間で交換するのに合計時間の30％しかかからない場合、数十個のストリームを使用しても、contfree_safe_ptr <>ポインターはCDSlibのマップコンテナーより高速です。
4. , CDSlib, contfree_safe_ptr<T> . , lock-free .

これらの記事では、Execute Around Pointer Idiomの例を使用して、単一スレッドでのC ++言語構造の実行シーケンスを詳細に調べました。また、競合のない共有ミューテックスの例を使用して、マルチスレッドプログラムでの読み取りおよび書き込み操作のシーケンスを調べました。また、libCDSのロックフリーアルゴリズムと、当社が開発したロックベースアルゴリズムの高性能な使用例を示しました。



その結果、safe_ptr.hファイルをダウンロードできます。このファイルには、次の記事で作成されたすべてのクラスと関数が含まれています。github.com / AlexeyAB / object_threadsafe



ブーストライブラリの一部として、記事で分析されたアルゴリズムを修正した形式で表示しますか？