配列のマルチスレッド配列？

Question

I 1000個の配列要素から成るデータ構造を有し、各配列要素が8つのintの小さい配列である：

std::array<std::array<int, 8>, 1000> 

データ構造は、最大と最小の人口の配列要素を追跡する二つの「ポインタ」が含ま（「外側」、1000要素配列内）。たとえば、次のようになります。

min = 247 
max = 842 

複数のスレッドからこのデータ構造を読み書きするにはどうすればよいですか？要素のプッシュ/ポップと2つの "ポインタ"の維持の間の競合状態が心配です。操作の私の基本的なモードは次のとおりです。

// Pop element from current index 
// Calculate new index 
// Write element to new index 
// Update min and max "pointers" 

Answer 1

あなたの現在のアルゴリズムは、スレッドセーフではないことを正しいと、競合が発生する可能性がある場所がいくつかあります。

しかしこれはより多くの情報なしで最適化することは不可能です。あなたはそれを改善する前にスローダウンが起こっている場所を知る必要があります。そのためには、指標が必要です。あなたのコードをプロファイリングして、どのビットが実際に時間を費やしているのかを調べてください。それらのビットを並列化することによってしか得ることができないため、実際にはメモリやCPU以外の制限要因であることがわかります。

最も簡単な方法は、ちょうど完全なプロセスのための構造全体をロックすることになります。これは、スレッドが他の多くの処理を行っている場合にのみ機能します。そうでないと、実際にはシングルスレッドと比較してパフォーマンスが低下します。

は、その後、あなたは、データ構造の異なるセクションに別々のロックを持つと考えることができます。スプリットするのに役立つものをいつ、どこで、どのように使っているのかを適切に分析する必要があります。たとえば、各チャンクに独自のロックが設定されているサブアレイのチャンクがあるとします。

は、別のスレッドがすでに79を持っていながら、79をしたいし、次に32はあなたが常に同じ順序でロックを主張していることを確認したいと考えていますが、スレッド項32を持っているかもしれません、しかしこのような状況でデッドロックに注意してください。

最速オプション（可能な場合）があっても、それは、データ構造の自身のコピーの作業の各工程の1/Nと、その後終了時に結果をマージする各スレッドを与えることができます。この方法では、処理中に同期が全く必要ありません。

しかし、再び、それはすべてのバックメトリックとプロファイリングに来ます。これは単純な問題ではありません。