用並行FOR循環節省時間

Question

我有一個關於並行for循環的問題。我有以下代碼：

public static void MultiplicateArray(double[] array, double factor) 
    { 
     for (int i = 0; i < array.Length; i++) 
     { 
      array[i] = array[i] * factor; 
     } 
    } 

    public static void MultiplicateArray(double[] arrayToChange, double[] multiplication) 
    { 
     for (int i = 0; i < arrayToChange.Length; i++) 
     { 
      arrayToChange[i] = arrayToChange[i] * multiplication[i]; 
     } 
    } 

    public static void MultiplicateArray(double[] arrayToChange, double[,] multiArray, int dimension) 
    { 
     for (int i = 0; i < arrayToChange.Length; i++) 
     { 
      arrayToChange[i] = arrayToChange[i] * multiArray[i, dimension]; 
     } 
    } 

現在我嘗試添加並行功能：

public static void MultiplicateArray(double[] array, double factor) 
    { 
     Parallel.For(0, array.Length, i => 
      { 
       array[i] = array[i] * factor; 
      }); 
    } 

    public static void MultiplicateArray(double[] arrayToChange, double[] multiplication) 
    { 
     Parallel.For(0, arrayToChange.Length, i => 
     { 
      arrayToChange[i] = arrayToChange[i] * multiplication[i]; 
     }); 
    } 

    public static void MultiplicateArray(double[] arrayToChange, double[,] multiArray, int dimension) 
    { 
     Parallel.For(0, arrayToChange.Length, i => 
     { 
      arrayToChange[i] = arrayToChange[i] * multiArray[i, dimension]; 
     }); 
    } 

的問題是，我想節省時間，不要浪費它。使用循環標準計算大約2分鐘，但使用並行循環需要3分鐘。爲什麼？

Answer 1

Parallel.For()可以通過並行代碼提高性能提升不少，但它也有開銷（線程之間的同步，在每次迭代中調用委託）。而且由於在你的代碼中，每次迭代都很短（基本上只有幾個CPU指令），這個開銷可能會變得很突出。因此，我認爲使用Parallel.For()不適合您。相反，如果您手動並行處理代碼（在這種情況下非常簡單），您可能會看到性能提高。

爲了驗證這一點，我進行了一些測量：我在200 000 000個項目的數組上運行了不同的MultiplicateArray()實現（我使用的代碼如下）。在我的機器上，串行版本一直花費0.21秒，而Parallel.For()通常花費了大約0.45秒，但是時不時，它會跳到8-9秒！

首先，我會嘗試改善常見情況，稍後我會回到那些尖峯。我們想要通過N CPU來處理數組，因此我們將其分成N等大小的零件並分別處理每個零件。結果？ 0.35秒。這比串行版本還要糟糕。但for遍歷數組中的每個項是最優化的構造之一。我們不能幫助編譯器嗎？提取計算循環的邊界可能會有所幫助。事實證明它的確如此：0.18秒。這比串行版本更好，但不是太多。有趣的是，在我的4核機器上（沒有超線程）將並行度從4改爲2並不會改變結果：仍然是0.18秒。這讓我得出結論，CPU不是這裏的瓶頸，內存帶寬是。

現在，回到尖峯：我的自定義並行化沒有它們，但Parallel.For()呢，爲什麼？ Parallel.For()確實使用範圍分區，這意味着每個線程都處理它自己的數組部分。但是，如果一個線程提前結束，它將嘗試幫助處理尚未完成的另一個線程的範圍。如果發生這種情況，你會得到很多錯誤的分享，這可能會使代碼變慢。而我自己的強迫虛假分享的測試似乎表明這可能確實是問題所在。強制Parallel.For()的並行度似乎有助於稍微增加峯值。

當然，所有這些測量都是特定於我電腦上的硬件，並且會因您而異，所以您應該自行測量。

我使用的代碼：

static void Main() 
{ 
    double[] array = new double[200 * 1000 * 1000]; 

    for (int i = 0; i < array.Length; i++) 
     array[i] = 1; 

    for (int i = 0; i < 5; i++) 
    { 
     Stopwatch sw = Stopwatch.StartNew(); 
     Serial(array, 2); 
     Console.WriteLine("Serial: {0:f2} s", sw.Elapsed.TotalSeconds); 

     sw = Stopwatch.StartNew(); 
     ParallelFor(array, 2); 
     Console.WriteLine("Parallel.For: {0:f2} s", sw.Elapsed.TotalSeconds); 

     sw = Stopwatch.StartNew(); 
     ParallelForDegreeOfParallelism(array, 2); 
     Console.WriteLine("Parallel.For (degree of parallelism): {0:f2} s", sw.Elapsed.TotalSeconds); 

     sw = Stopwatch.StartNew(); 
     CustomParallel(array, 2); 
     Console.WriteLine("Custom parallel: {0:f2} s", sw.Elapsed.TotalSeconds); 

     sw = Stopwatch.StartNew(); 
     CustomParallelExtractedMax(array, 2); 
     Console.WriteLine("Custom parallel (extracted max): {0:f2} s", sw.Elapsed.TotalSeconds); 

     sw = Stopwatch.StartNew(); 
     CustomParallelExtractedMaxHalfParallelism(array, 2); 
     Console.WriteLine("Custom parallel (extracted max, half parallelism): {0:f2} s", sw.Elapsed.TotalSeconds); 

     sw = Stopwatch.StartNew(); 
     CustomParallelFalseSharing(array, 2); 
     Console.WriteLine("Custom parallel (false sharing): {0:f2} s", sw.Elapsed.TotalSeconds); 
    } 
} 

static void Serial(double[] array, double factor) 
{ 
    for (int i = 0; i < array.Length; i++) 
    { 
     array[i] = array[i] * factor; 
    } 
} 

static void ParallelFor(double[] array, double factor) 
{ 
    Parallel.For(
     0, array.Length, i => { array[i] = array[i] * factor; }); 
} 

static void ParallelForDegreeOfParallelism(double[] array, double factor) 
{ 
    Parallel.For(
     0, array.Length, new ParallelOptions { MaxDegreeOfParallelism = Environment.ProcessorCount }, 
     i => { array[i] = array[i] * factor; }); 
} 

static void CustomParallel(double[] array, double factor) 
{ 
    var degreeOfParallelism = Environment.ProcessorCount; 

    var tasks = new Task[degreeOfParallelism]; 

    for (int taskNumber = 0; taskNumber < degreeOfParallelism; taskNumber++) 
    { 
     // capturing taskNumber in lambda wouldn't work correctly 
     int taskNumberCopy = taskNumber; 

     tasks[taskNumber] = Task.Factory.StartNew(
      () => 
      { 
       for (int i = array.Length * taskNumberCopy/degreeOfParallelism; 
        i < array.Length * (taskNumberCopy + 1)/degreeOfParallelism; 
        i++) 
       { 
        array[i] = array[i] * factor; 
       } 
      }); 
    } 

    Task.WaitAll(tasks); 
} 

static void CustomParallelExtractedMax(double[] array, double factor) 
{ 
    var degreeOfParallelism = Environment.ProcessorCount; 

    var tasks = new Task[degreeOfParallelism]; 

    for (int taskNumber = 0; taskNumber < degreeOfParallelism; taskNumber++) 
    { 
     // capturing taskNumber in lambda wouldn't work correctly 
     int taskNumberCopy = taskNumber; 

     tasks[taskNumber] = Task.Factory.StartNew(
      () => 
      { 
       var max = array.Length * (taskNumberCopy + 1)/degreeOfParallelism; 
       for (int i = array.Length * taskNumberCopy/degreeOfParallelism; 
        i < max; 
        i++) 
       { 
        array[i] = array[i] * factor; 
       } 
      }); 
    } 

    Task.WaitAll(tasks); 
} 

static void CustomParallelExtractedMaxHalfParallelism(double[] array, double factor) 
{ 
    var degreeOfParallelism = Environment.ProcessorCount/2; 

    var tasks = new Task[degreeOfParallelism]; 

    for (int taskNumber = 0; taskNumber < degreeOfParallelism; taskNumber++) 
    { 
     // capturing taskNumber in lambda wouldn't work correctly 
     int taskNumberCopy = taskNumber; 

     tasks[taskNumber] = Task.Factory.StartNew(
      () => 
      { 
       var max = array.Length * (taskNumberCopy + 1)/degreeOfParallelism; 
       for (int i = array.Length * taskNumberCopy/degreeOfParallelism; 
        i < max; 
        i++) 
       { 
        array[i] = array[i] * factor; 
       } 
      }); 
    } 

    Task.WaitAll(tasks); 
} 

static void CustomParallelFalseSharing(double[] array, double factor) 
{ 
    var degreeOfParallelism = Environment.ProcessorCount; 

    var tasks = new Task[degreeOfParallelism]; 

    int i = -1; 

    for (int taskNumber = 0; taskNumber < degreeOfParallelism; taskNumber++) 
    { 
     tasks[taskNumber] = Task.Factory.StartNew(
      () => 
      { 
       int j = Interlocked.Increment(ref i); 
       while (j < array.Length) 
       { 
        array[j] = array[j] * factor; 
        j = Interlocked.Increment(ref i); 
       } 
      }); 
    } 

    Task.WaitAll(tasks); 
} 

輸出示例：

Serial: 0,20 s 
Parallel.For: 0,50 s 
Parallel.For (degree of parallelism): 8,90 s 
Custom parallel: 0,33 s 
Custom parallel (extracted max): 0,18 s 
Custom parallel (extracted max, half parallelism): 0,18 s 
Custom parallel (false sharing): 7,53 s 
Serial: 0,21 s 
Parallel.For: 0,52 s 
Parallel.For (degree of parallelism): 0,36 s 
Custom parallel: 0,31 s 
Custom parallel (extracted max): 0,18 s 
Custom parallel (extracted max, half parallelism): 0,19 s 
Custom parallel (false sharing): 7,59 s 
Serial: 0,21 s 
Parallel.For: 11,21 s 
Parallel.For (degree of parallelism): 0,36 s 
Custom parallel: 0,32 s 
Custom parallel (extracted max): 0,18 s 
Custom parallel (extracted max, half parallelism): 0,18 s 
Custom parallel (false sharing): 7,76 s 
Serial: 0,21 s 
Parallel.For: 0,46 s 
Parallel.For (degree of parallelism): 0,35 s 
Custom parallel: 0,31 s 
Custom parallel (extracted max): 0,18 s 
Custom parallel (extracted max, half parallelism): 0,18 s 
Custom parallel (false sharing): 7,58 s 
Serial: 0,21 s 
Parallel.For: 0,45 s 
Parallel.For (degree of parallelism): 0,40 s 
Custom parallel: 0,38 s 
Custom parallel (extracted max): 0,18 s 
Custom parallel (extracted max, half parallelism): 0,18 s 
Custom parallel (false sharing): 7,58 s 

Answer 2

Parallel.For涉及更復雜的內存管理。這種結果可能取決於CPU的規格，像#cores，L1 & L2緩存而變化......

請看看這個有趣的文章：

http://msdn.microsoft.com/en-us/magazine/cc872851.aspx

Answer 3

從http://msdn.microsoft.com/en-us/library/system.threading.tasks.parallel.aspx和http://msdn.microsoft.com/en-us/library/dd537608.aspx

你並沒有創建三個執行你的代碼的線程/進程，但是for的迭代被試圖並行執行，所以即使只有一個代碼使用多線程/進程。

這意味着索引= 0和索引= 1的交互可以同時執行。

可能的是，你迫使使用太多的線程/進程，並且創建/執行它們的開銷大於速度增益。

嘗試使用三個正常的，但在三個不同的線程/進程，如果你的SISTEM是多核（3X至少）應採取不到一分鐘

Answer 4

參見Custom Partitioners for PLINQ and TPL：

在For循環，循環的主體被提供給該方法作爲代表。調用該委託的成本與虛擬方法調用大致相同。在某些情況下，並行循環的主體可能足夠小，以致每個循環迭代上的委託調用的代價變得很大。在這種情況下，您可以使用Create過載之一在源元素上創建範圍分區的IEnumerable<T>。然後，您可以將這個範圍集合傳遞給一個ForEach方法，該方法的主體由一個常規for循環組成。這種方法的好處是委託調用成本僅在每個範圍內發生一次，而不是每個元素髮生一次。

在您的循環體中，您正在執行單個乘法，並且委託調用的開銷將非常明顯。

試試這個：

public static void MultiplicateArray(double[] array, double factor) 
{ 
    var rangePartitioner = Partitioner.Create(0, array.Length); 

    Parallel.ForEach(rangePartitioner, range => 
    { 
     for (int i = range.Item1; i < range.Item2; i++) 
     { 
      array[i] = array[i] * factor; 
     } 
    }); 
} 

參見：Parallel.ForEach documentation和Partitioner.Create documentation。

Answer 5

Svick已經提供了一個很好的答案，但我想強調的是，關鍵的一點是不要把「手工並行代碼」，而不是使用Parallel.For()，但你必須處理數據的更大的塊。

這仍然可以使用Parallel.For()這樣進行：

static void My(double[] array, double factor) 
{ 
    int degreeOfParallelism = Environment.ProcessorCount; 

    Parallel.For(0, degreeOfParallelism, workerId => 
    { 
     var max = array.Length * (workerId + 1)/degreeOfParallelism; 
     for (int i = array.Length * workerId/degreeOfParallelism; i < max; i++) 
      array[i] = array[i] * factor; 
    }); 
} 

它做同樣的事情svicks CustomParallelExtractedMax()但更短，更簡單，（我的機器上），即使執行速度稍快：

Serial: 3,94 s 
Parallel.For: 9,28 s 
Parallel.For (degree of parallelism): 9,58 s 
Custom parallel: 2,05 s 
Custom parallel (extracted max): 1,19 s 
Custom parallel (extracted max, half parallelism): 1,49 s 
Custom parallel (false sharing): 27,88 s 
My: 0,95 s 

順便說一句，這是從所有其他答案中缺少的關鍵字是粒度。