最近、私は、任意の基数の順列ごとに生成するための並列化可能なメソッドの最適化に関する質問に答えました。Parallelized, poor implementation code block list に似た回答を投稿しましたが、誰かがすぐにこれを指摘しました:
これにより、誤った共有が行われることがほぼ保証され、おそらく何倍も遅くなります。（gjvdkampのクレジット）
そして彼らは正しかった、それは死の遅さでした。そうは言っても、私はこのトピックを調査し、それに対抗するための興味深い資料と提案(アーカイブされた MSDN マガジンのみ、.NET Matters: False Sharing ) を見つけました。私が正しく理解していれば、スレッドが連続したメモリ (たとえば、それをサポートしている可能性が高い配列) にアクセスするとConcurrentStack、誤った共有が発生する可能性があります。
水平線より下のコードの場合、aBytesは次のとおりです。
struct Bytes {
public byte A; public byte B; public byte C; public byte D;
public byte E; public byte F; public byte G; public byte H;
}
私自身のテストでは、これの並列バージョンを実行して本当に高速にしたかったので、元のコードに基づいて簡単な例を作成しました。6私の側では怠惰なlimits[0]選択でした-私のコンピューターには6つのコアがあります。
シングルスレッドブロック 平均実行時間: 10s0059ms
var data = new List<Bytes>();
var limits = new byte[] { 6, 16, 16, 16, 32, 8, 8, 8 };
for (byte a = 0; a < limits[0]; a++)
for (byte b = 0; b < limits[1]; b++)
for (byte c = 0; c < limits[2]; c++)
for (byte d = 0; d < limits[3]; d++)
for (byte e = 0; e < limits[4]; e++)
for (byte f = 0; f < limits[5]; f++)
for (byte g = 0; g < limits[6]; g++)
for (byte h = 0; h < limits[7]; h++)
data.Add(new Bytes {
A = a, B = b, C = c, D = d,
E = e, F = f, G = g, H = h
});
並列化、貧弱な実装 平均実行時間: 81 秒 729 ミリ秒、～ 8700 回の競合
var data = new ConcurrentStack<Bytes>();
var limits = new byte[] { 6, 16, 16, 16, 32, 8, 8, 8 };
Parallel.For(0, limits[0], (a) => {
for (byte b = 0; b < limits[1]; b++)
for (byte c = 0; c < limits[2]; c++)
for (byte d = 0; d < limits[3]; d++)
for (byte e = 0; e < limits[4]; e++)
for (byte f = 0; f < limits[5]; f++)
for (byte g = 0; g < limits[6]; g++)
for (byte h = 0; h < limits[7]; h++)
data.Push(new Bytes {
A = (byte)a,B = b,C = c,D = d,
E = e,F = f,G = g,H = h
});
});
並列化、?? 平均実行 時間: 5 秒 833 ミリ秒、92 回の競合
var data = new ConcurrentStack<List<Bytes>>();
var limits = new byte[] { 6, 16, 16, 16, 32, 8, 8, 8 };
Parallel.For (0, limits[0], () => new List<Bytes>(),
(a, loop, localList) => {
for (byte b = 0; b < limits[1]; b++)
for (byte c = 0; c < limits[2]; c++)
for (byte d = 0; d < limits[3]; d++)
for (byte e = 0; e < limits[4]; e++)
for (byte f = 0; f < limits[5]; f++)
for (byte g = 0; g < limits[6]; g++)
for (byte h = 0; h < limits[7]; h++)
localList.Add(new Bytes {
A = (byte)a, B = b, C = c, D = d,
E = e, F = f, G = g, H = h
});
return localList;
}, x => {
data.Push(x);
});
シングル スレッド バージョンよりも高速な実装が得られたことを嬉しく思います。約 10 秒 / 6、つまり約 1.6 秒に近い結果になると予想していましたが、それはおそらく単純な予想です。
私の質問は、実際にはシングル スレッド バージョンよりも高速な並列化された実装についてです。操作に適用できるさらなる最適化はありますか? 値の計算に使用されるアルゴリズムの改善ではなく、並列化に関連する最適化について疑問に思っています。具体的には：
structの代わりにとして格納および入力する最適化については知っていますbyte[]が、それは並列化とは関係ありません (またはそうですか?)struct必要な値は、リップルキャリー加算器を使用して遅延評価できることを知っていますが、最適化と同じです。