並行遞歸比「順序」遞歸慢。我做錯了嗎？

Question

我正在做一些非常基本的測試，看看在我的程序中使用並行處理是否會提供任何明顯的速度提升。到目前爲止，我對結果感到困惑。在我的測試中，我構建了一個分支因子爲30的樹結構。首先，我使用無並行性來測試，然後使用parallel for循環嘗試相同的測試。下面是我的結果：

順序：

Depth: 2 Time: 0.0013964 (900 nodes) 
Depth: 3 Time: 0.0053703 (27,000 nodes) 
Depth: 4 Time: 0.3994147 (810,000 nodes) 
Depth: 5 Time: 14.8306510 (24,300,000 nodes) 
Depth: 6 Time: 6:54.4050838 (729,000,000 nodes) 

並行：

Depth: 2 Time: 0.0389201 (900 nodes) 
Depth: 3 Time: 0.1180270 (27,000 nodes) 
Depth: 4 Time: 6:06.2296531 (810,000 nodes) 

我沒有理會進一步的測試，因爲我沒有看到它由6取不到7分鐘深度。

我有一個雙核處理器，雖然我知道並行性有一定的開銷，但我認爲它不會那麼重要。我已經證實，在兩種情況下基因處理的樹結構都是在每個節點適當數量的兒童（30）的適當深度下形成的。

這裏是我的代碼：

using System; 
using System.Collections.Concurrent; 
using System.Collections.Generic; 
using System.Threading.Tasks; 

namespace ParallelRecursion 
{ 
    class TreeStructure 
    { 
     public TreeStructure(int targetLevel, bool runParallel) 
     { 
      _root = new TreeNode(targetLevel, runParallel); 
     } 

     private TreeNode _root; 
    } 

    class TreeNode 
    { 
     public TreeNode(int targetLevel, bool runParallel) 
     { 
      _runParallel = runParallel; 

      _rnd = new Random(); 
      _score = _rnd.Next(int.MinValue, int.MaxValue); 

      _level = 0; 
      _targetlevel = targetLevel; 

      if (_level < _targetlevel) 
      { 
       if (!_runParallel) 
       { 
        _children = new List<TreeNode>(); 
        GenerateChildren(); 
       } 
       else 
       { 
        _concurrentChildren = new ConcurrentBag<TreeNode>(); 
        GenerateParallelChildren(); 
       } 
      } 
     } 

     public TreeNode(TreeNode treeNode) 
     { 
      _runParallel = treeNode._runParallel; 

      _rnd = treeNode._rnd; 
      _score = _rnd.Next(int.MinValue, int.MaxValue); 
      _parent = treeNode; 

      _level = treeNode._level + 1; 
      _targetlevel = treeNode._targetlevel; 

      if (_level < _targetlevel) 
      { 
       if (!_runParallel) 
       { 
        _children = new List<TreeNode>(); 
        GenerateChildren(); 
       } 
       else 
       { 
        _concurrentChildren = new ConcurrentBag<TreeNode>(); 
        GenerateParallelChildren(); 
       }     
      } 
     } 

     private bool _runParallel; 
     private Random _rnd; 
     private int _score; 
     private int _level; 
     private int _targetlevel; 
     private TreeNode _parent; 
     private List<TreeNode> _children; 
     private ConcurrentBag<TreeNode> _concurrentChildren; 

     private void GenerateChildren() 
     { 
      for (int i = 0; i < 30; i++) 
      { 
       _children.Add(new TreeNode(this)); 
      } 
     }   

     private void GenerateParallelChildren() 
     { 
      Parallel.For(0, 30, i => { GenerateChild(); }); 
     } 

     private void GenerateChild() 
     { 
      _concurrentChildren.Add(new TreeNode(this)); 
     } 
    } 
} 

可以使用測試：

TreeStructure ts = new TreeStructure(4, true);//TreeStructure(int targetDepth, bool runParallel) 

我希望，我做錯了什麼。這僅僅是這種結構對並行性沒有影響嗎？

Answer 1

在一種情況下使用ConcurrentBag<T>而在另一種情況下使用List<T>並不能使它比較蘋果與蘋果。一旦你將List<T>替換爲ConcurrentBag<T>對於非併發兒童來說，兩種版本的運行速度差不多一樣。

Answer 2

您正在使用Parallelism錯誤，您正在啓動一個新任務來創建單個節點，這就是並行版本較慢的原因，因爲儘管TPL實際上並未爲每次迭代創建一個任務，但它仍然包含幾個其中，創建任務在時間上是昂貴的（不如線程）。

你應該做的是分而治之，劃分你的工作，做一個任務創建一堆TreeNode而不只是一個。