Parallel.ForEachは通常のforeachより遅い

Question

私はParallel.ForEachをC＃コンソールアプリケーションで使いこなしていますが、正しいとは思えません。私は乱数を使って配列を作成しています。配列foreachと配列の中で最大の値を見つけるParallel.ForEachがあります。 C++とほぼ同じコードを使って、配列の3M値でいくつかのスレッドを使うこととのトレードオフが見え始めました。しかし、Parallel.ForEachは100Mの値でも2倍の速度です。何が間違っているのですか？

class Program 
{ 
    static void Main(string[] args) 
    { 
     dostuff(); 

    } 

    static void dostuff() { 
     Console.WriteLine("How large do you want the array to be?"); 
     int size = int.Parse(Console.ReadLine()); 

     int[] arr = new int[size]; 
     Random rand = new Random(); 
     for (int i = 0; i < size; i++) 
     { 
      arr[i] = rand.Next(0, int.MaxValue); 
     } 

     var watchSeq = System.Diagnostics.Stopwatch.StartNew(); 
     var largestSeq = FindLargestSequentially(arr); 
     watchSeq.Stop(); 
     var elapsedSeq = watchSeq.ElapsedMilliseconds; 
     Console.WriteLine("Finished sequential in: " + elapsedSeq + "ms. Largest = " + largestSeq); 

     var watchPar = System.Diagnostics.Stopwatch.StartNew(); 
     var largestPar = FindLargestParallel(arr); 
     watchPar.Stop(); 
     var elapsedPar = watchPar.ElapsedMilliseconds; 
     Console.WriteLine("Finished parallel in: " + elapsedPar + "ms Largest = " + largestPar); 

     dostuff(); 
    } 

    static int FindLargestSequentially(int[] arr) { 
     int largest = arr[0]; 
     foreach (int i in arr) { 
      if (largest < i) { 
       largest = i; 
      } 
     } 
     return largest; 
    } 

    static int FindLargestParallel(int[] arr) { 
     int largest = arr[0]; 
     Parallel.ForEach<int, int>(arr,() => 0, (i, loop, subtotal) => 
     { 
      if (i > subtotal) 
       subtotal = i; 
      return subtotal; 
     }, 
     (finalResult) => { 
      Console.WriteLine("Thread finished with result: " + finalResult); 
      if (largest < finalResult) largest = finalResult; 
     } 
     ); 
     return largest; 
    } 
} 

Answer 1

非常に小さいデリゲートボディを持つことによるパフォーマンスの低下です。

パーティショニングを使用すると、パフォーマンスが向上します。この場合、本体デリゲートはデータ量の多い作業を実行します。

static int FindLargestParallelRange(int[] arr) 
{ 
    object locker = new object(); 
    int largest = arr[0]; 
    Parallel.ForEach(Partitioner.Create(0, arr.Length),() => arr[0], (range, loop, subtotal) => 
    { 
     for (int i = range.Item1; i < range.Item2; i++) 
      if (arr[i] > subtotal) 
       subtotal = arr[i]; 
     return subtotal; 
    }, 
    (finalResult) => 
    { 
     lock (locker) 
      if (largest < finalResult) 
       largest = finalResult; 
    }); 
    return largest; 
} 

localFinallyデリゲートを同期するように注意してください。また、localInit：() => arr[0]の適切な初期化の必要性には、() => 0の代わりに注意してください。 PLINQと

パーティショニング：

static int FindLargestPlinqRange(int[] arr) 
{ 
    return Partitioner.Create(0, arr.Length) 
     .AsParallel() 
     .Select(range => 
     { 
      int largest = arr[0]; 
      for (int i = range.Item1; i < range.Item2; i++) 
       if (arr[i] > largest) 
        largest = arr[i]; 
      return largest; 
     }) 
     .Max(); 
} 

私は非常にスティーブンToubで無料の本Patterns of Parallel Programmingをお勧めします。

Answer 2

ここにいくつかの考え：パラレル場合は、それが使用したいどのように多くのスレッドを決定関与スレッド管理ロジックがあります。このスレッド管理ロジックはおそらくあなたのメインスレッド上で実行される可能性があります。スレッドが新しい最大値を返すたびに、管理ロジックが起動し、次の作業項目（配列内で処理する次の番号）を決定します。私はこれが何らかのロックを必要としていると確信しています。いずれにしても、次の項目を決定することは、比較操作そのものを実行することよりもコストがかかる可能性がある。

これは、1つの番号を別の番号に処理する単一のスレッドよりも、はるかに大きな仕事（オーバヘッド）のようです。シングルスレッドの場合、いくつかの最適化が行われます。境界チェックなし、CPU内の第1レベルのキャッシュにデータをロードすることなどが可能です。

一般的なデスクトップマシンでは、物理CPUコアが2〜4個しかないため、実際にはそれ以上の作業はできません。したがって、並列処理オーバーヘッドがシングルスレッド処理の2〜4倍を超える場合、並列バージョンは不可避的に遅くなります。

これを32コアマシンで実行しようとしましたか？ ;-)

より良い解決策は、配列全体をカバーする非重複範囲（開始+停止インデックス）を決定し、各並列タスクが1つの範囲を処理するようにすることです。このようにして、各並列タスクは内部的にタイトなシングルスレッドループを実行し、範囲全体が処理された後にのみ戻ることができます。おそらく、マシンの論理コアの数に基づいて、ほぼ最適な数の範囲を決定することさえできます。私はこれを試していないが、私はあなたがシングルスレッドの場合よりも改善が見られると確信しています。

Answer 3

使用されるアルゴリズムが並列でなく、このアルゴリズムを実行するためにさらに多くの作業が行われているため、Parallel Foreachループの実行速度が遅くなります。

シングルスレッドでは、最大値を見つけるために、最初の数値を最大値として取り、それを配列内の他のすべての数値と比較することができます。最初の番号より大きな番号のいずれかがあれば、スワップして処理を続行します。このようにして、配列の各数値に1回アクセスし、合計N回の比較を行います。

上記のParallelループでは、各操作が戻り値を持つ関数呼び出しの中にラップされるため、アルゴリズムはオーバーヘッドを作成します。したがって、比較を行うことに加えて、これらの呼び出しを呼び出しスタックに追加したり削除したりするオーバーヘッドが発生しています。さらに、各呼び出しは前に関数呼び出しの値に依存しているため、順番に実行する必要があります。

以下のParallel For Loopでは、配列は、変数threadNumberによって決定される明示的な数のスレッドに分割されます。これにより、関数呼び出しのオーバーヘッドが低い数値に制限されます。

低い値の場合、並列ループは低速で実行されます。しかし、100Mの場合、経過時間が減少します。

static int FindLargestParallel(int[] arr) 
{ 
    var answers = new ConcurrentBag<int>(); 
    int threadNumber = 4; 

    int partitionSize = arr.Length/threadNumber; 
    Parallel.For(0, /* starting number */ 
     threadNumber+1, /* Adding 1 to threadNumber in case array.Length not evenly divisible by threadNumber */ 
     i => 
     { 
      if (i*partitionSize < arr.Length) /* check in case # in array is divisible by # threads */ 
      { 
       var max = arr[i*partitionSize]; 
       for (var x = i*partitionSize; 
        x < (i + 1)*partitionSize && x < arr.Length; 
        ++x) 
       { 
        if (arr[x] > max) 
         max = arr[x]; 
       } 
       answers.Add(max); 
      } 
     }); 

    /* note the shortcut in finding max in the bag */  
    return answers.Max(i=>i); 
} 

Answer 4

他の回答者が述べたように、ここの各項目に対して実行しようとしているアクションは、それほど重要ではありません。実際に行っている作業よりも多くの重量をもたらすさまざまな要因があります。これらは、可能性があります

• JITの最適化
• CPUの分岐予測
• I/O
• 呼び出す委譲し
• タスク管理のコストをコストを（タイマの実行中のスレッドの結果を出力）
• システムは、最適なスレッド戦略を誤って推測しています
• メモリ/ cpuキャッシュ
• メモリ圧力
• 環境（デバッグ）
• 等がより重くを圧迫するために、上記の多数の要因を可能にするために、それぞれが、単一の時間をテストするための適切な方法ではない接近実行

ある反復は別の反復よりも早い。より堅牢なベンチマーク戦略から始めてください。

さらに、実装は実際には危険です。 The documentation、具体的に言う：

localFinallyデリゲートは、各タスクのローカル状態の最終的なアクションを実行するタスクごとに一度呼び出されます。このデリゲートは、複数のタスクで同時に呼び出すことができます。したがって、共有変数へのアクセスを同期化する必要があります。

最終的なデリゲートは同期されていないため、関数が競合状態になり、誤った結果が生じる可能性があります。

ほとんどの場合と同様に、この方法の最善の方法は、私たちよりも賢明な人の作業を利用することです。In my testing、次のようなアプローチは、最速の全体的なように見えます：

return arr.AsParallel().Max();