數組遍歷：並行性能比非平行

Question

在我的計劃要慢，我想detemine多少個號碼有9位數字如何，許多有8位等與這個循環：

for (int i = 0; i < 60000000; i++) 
     { 
      if (a[i] >= 1000000000) { p[10] += 1; } 
      else if (a[i] >= 100000000) { p[9] += 1; } 
      else if (a[i] >= 10000000) { p[8] += 1; } 
      else if (a[i] >= 1000000) { p[7] += 1; } 
      else if (a[i] >= 100000) { p[6] += 1; } 
      else if (a[i] >= 10000) { p[5] += 1; } 
      else if (a[i] >= 1000) { p[4] += 1; } 
      else if (a[i] >= 100) { p[3] += 1; } 
      else if (a[i] >= 10) { p[2] += 1; } 
      else { p[1] += 1; } 
     } 

我並行循環像這樣：

void partiton(int f, int l, int[] p) 
    { 
     Parallel.Invoke(()=>calc(f,l/2,p),()=>calc(l/2,l,p)); 
    } 

    void calc(int f, int l, int[] p) 
    { 
     for (int i = f; i < l; i++) 
     { 
      if (a[i] >= 1000000000) { p[10] += 1; } 
      else if (a[i] >= 100000000) { p[9] += 1; } 
      else if (a[i] >= 10000000) { p[8] += 1; } 
      else if (a[i] >= 1000000) { p[7] += 1; } 
      else if (a[i] >= 100000) { p[6] += 1; } 
      else if (a[i] >= 10000) { p[5] += 1; } 
      else if (a[i] >= 1000) { p[4] += 1; } 
      else if (a[i] >= 100) { p[3] += 1; } 
      else if (a[i] >= 10) { p[2] += 1; } 
      else { p[1] += 1; } 
     } 
    } 
private void button1_Click(object sender, EventArgs e) 
    { 
     Stopwatch w = new Stopwatch(); 
     w.Restart(); 
     int f = 0; 
     int l = 60000000; 
     Parallel.Invoke(() => calc(f, l/2, p),() => calc(l/2, l, p)); 
     w.Stop(); 
     label1.Text = w.Elapsed.ToString(); 

    } 

但基準是： 順序：0.3834 並行：0.6864

爲什麼並行代碼慢？我的代碼有問題嗎？我的CPU是AMD Phenom™II X4。型號，955.

Answer 1

這一切都在變量中。

以您的p爲例。您將相同的p對象傳遞給線程均爲線程。現在，我不確定Parallel.Invoke是否能夠檢測到這一點，因此它們是以串行方式執行它們（雖然開銷很大），但我做了知道如果它沒有檢測到這個，那麼你有一個lot嘗試在同一個線程中讀取/寫入相同的值。

現在，我建立了一個小的，具體的例子，用你的代碼作爲基礎，這裏是它的一個副本。 （粘貼到任何新的控制檯項目，重命名_Main到Main和運行，你認爲合適。）

static int[] a = new int[100000000]; 
static void calc(int f, int l, int[] p, int[] a) 
{ 
    for (int i = f; i < l; i++) 
    { 
     if (a[i] >= 1000000000) { p[10] += 1; } 
     else if (a[i] >= 100000000) { p[9] += 1; } 
     else if (a[i] >= 10000000) { p[8] += 1; } 
     else if (a[i] >= 1000000) { p[7] += 1; } 
     else if (a[i] >= 100000) { p[6] += 1; } 
     else if (a[i] >= 10000) { p[5] += 1; } 
     else if (a[i] >= 1000) { p[4] += 1; } 
     else if (a[i] >= 100) { p[3] += 1; } 
     else if (a[i] >= 10) { p[2] += 1; } 
     else { p[1] += 1; } 
    } 
} 
public static void _Main(string[] args) 
{ 
    for (int i = 0; i < a.Length; i++) 
    { 
     a[i] = i; 
    } 

    int f = 0; 
    int l = a.Length; 
    int[] p = new int[10]; 
    int[] p1 = new int[10]; 
    int[] p2 = new int[10]; 
    int[] p3 = new int[10]; 
    int[] p4 = new int[10]; 

    int[] a1 = new int[l/2]; 
    int[] a2 = new int[l/2]; 

    int[] a11 = new int[l/4]; 
    int[] a12 = new int[l/4]; 
    int[] a13 = new int[l/4]; 
    int[] a14 = new int[l/4]; 

    for (int i = 0; i < a.Length; i++) 
     if (i >= l/2) 
      a2[i - l/2] = a[i]; 
     else 
      a1[i] = a[i]; 

    for (int i = 0; i < a.Length; i++) 
     if (i >= l/4 * 3) 
      a14[i - l/4 * 3] = a[i]; 
     else if (i >= l/4 * 2) 
      a13[i - l/4 * 2] = a[i]; 
     else if (i >= l/4 * 1) 
      a12[i - l/4] = a[i]; 
     else 
      a14[i] = a[i]; 

    int rc = 5; 
    for (int d = 0; d < rc; d++) 
    { 
     Stopwatch w = new Stopwatch(); 
     w.Start(); 
     Parallel.Invoke(() => calc(f, l/2, p1, a1),() => calc(f, l/2, p2, a2)); 
     w.Stop(); 
     Console.WriteLine("Attempt {0}/{1}: {2}", 1, d, w.ElapsedMilliseconds); 
     w.Reset(); 
     w.Start(); 
     Parallel.Invoke(() => calc(f, l/4, p1, a11),() => calc(f, l/4, p2, a12),() => calc(f, l/4, p3, a13),() => calc(f, l/4, p4, a14)); 
     w.Stop(); 
     Console.WriteLine("Attempt {0}/{1}: {2}", 2, d, w.ElapsedMilliseconds); 
     w.Reset(); 
     w.Start(); 
     Parallel.Invoke(() => calc(f, l/2, p, a),() => calc(l/2, l, p, a)); 
     w.Stop(); 
     Console.WriteLine("Attempt {0}/{1}: {2}", 3, d, w.ElapsedMilliseconds); 
     w.Reset(); 
     w.Start(); 
     calc(f, l, p, a); 
     w.Stop(); 
     Console.WriteLine("Attempt {0}/{1}: {2}", 4, d, w.ElapsedMilliseconds); 
    } 
} 

我敢肯定有更多的優化，我可以運行。 （例如，將if s轉換爲while循環。）我也不能保證它的準確性。我只是採取你的邏輯，並採取適當的調試。

但是，當我跑我的電腦，這個確切的例子，我有以下結果：

1. 嘗試了1平均327.8ms。此嘗試將a和p變量拆分爲兩個個別變量。
2. 嘗試2平均需要306ms。此嘗試將a和p變量拆分爲四個個別變量。
3. 嘗試3平均需要703ms。這與你所做的完全一樣。 （雖然在calc方法的局部變量。
4. 嘗試4把平均347.6ms，這是同步運行calc方法。

爲什麼這麼大的差異？嘗試1和2分割處理後的數據到不需要線程同步的變量中，而嘗試3則強制兩個線程使用相同的變量，從而產生衝突，正如Ron Beyer所說，上下文切換。

基本上，如果您要嘗試寫入同樣的任何東西並行，你應該本地化數據每個線程是最後編寫和合並更改。

Answer 2

• 此代碼不會給你正確的數字，因爲它增加了從多個線程相同的變量沒有同步。當不同的CPU內核在同一個變量上工作時，每個內核都有自己的版本，並且此版本的修改不會立即流向其他緩存。因此，其他內核在舊版本上工作。例如，一個內核可能會將p [0]從0增加到1，但另一個內核仍然認爲它是0.因此，當它增加時，該值再次變爲1。後來，這1將出現在主存儲器中，而不是2.
• 要回答你的問題，問題是你使用兩個線程中相同的內存塊，並且會降低內存訪問速度。數據通常被緩存，但是當一個內核寫入內存區域時，其他內核遲早會檢測到這一點，並且他們需要從緩慢的主內存中重新加載它。 （遲早對你來說很重要，它不會立即發生，所以你需要同步，這使得一切都變得更慢）。由於這些重新獲取，多線程版本較慢。

當您嘗試製作多線程算法時，您需要嘗試以不使用共享內存的方式分離任務。作爲一種微型優化 - 這是不良的 - 你可以嘗試按照不相鄰的方式分配內存，否則之前提到的緩存問題會減慢處理速度。