Параллельная рекурсия медленнее, чем «последовательная» рекурсия. Я делаю это неправильно?

Question

Я делаю несколько очень простых тестов, чтобы увидеть, даст ли использование параллельной обработки в моей программе какое-либо заметное увеличение скорости.Пока что я запутался в результатах.В моем тесте я строю древовидную структуру с коэффициентом ветвления 30. Сначала я выполняю тестирование без параллелизма, затем пытаюсь сделать то же самое, используя параллельный цикл 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)

Я не потрудился провести тестирование дальше, так как не вижу, чтобы он занимал меньшечем 7 минут на глубину 6.

У меня есть двухъядерный процессор, и хотя я понимаю, что параллелизм имеет определенную нагрузку, я подумал, что он не будет настолько значительным.Я проверил, что древовидные структуры, сгенерированные в обеих ситуациях, правильно сформированы на заданную глубину с соответствующим числом дочерних элементов (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

Вы используете неправильный параллелизм, вы запускаете новую задачу для создания одного узла, поэтому параллельная версия медленнее, потому что, хотя TPL на самом деле не создает задачу для каждой итерации, он все равно создает несколькоих, а создание задач обходится дорого (не так много, как потоки).

То, что вы должны сделать, это разделить и победить, разделить вашу работу, заставить задачу создать связку TreeNode, а не только одну.