Параллельный обход дерева в C #

Мне нужно быстро пройти по дереву, и я хотел бы сделать это параллельно. Я бы предпочел использовать параллельные расширения, чем вручную запускать кучу потоков.

Мой текущий код выглядит примерно так:

   public void Traverse(Node root)
    {
        var nodeQueue = new Queue();
        nodeQueue.Enqueue(root);
        while (nodeQueue.Count!=0)
        {
            var node = nodeQueue.Dequeue();
            if (node.Property = someValue) DoSomething(node);
            foreach (var node in node.Children)
            {
                nodeQueue.Enqueue(node);
            }
        }
    }

Я действительно надеялся, что у Parallel.ForEach есть аналог Parallel.While. Я наткнулся на статью Стивена Туба Реализация Parallel While с Parallel.ForEach . При правильном прочтении это все равно не сработает, потому что я изменяю очередь, которую пытаюсь перебрать.

Нужно ли мне использовать фабрику задач и рекурсию (и это рискованно?)? или есть какое-то простое решение, которое я не замечаю?

Изменить: @svick

В дереве чуть более 250 000 узлов. На данный момент максимальная глубина составляет 14 узлов, включая корень.

Есть около 500 узлов вне корня, и баланс после этого имеет довольно случайное распределение. Скоро я получу лучшую статистику по распределению.

@Enigmativity:

Да, дерево модифицируется одновременно многими пользователями, но обычно у меня есть общая блокировка чтения для дерева или поддерева, или разрешить грязное чтение.

Вызовы node.Children можно считать атомарными.

DoSomething на самом деле является одним из нескольких делегатов, для некоторых дорогостоящих операций я, вероятно, соберу список моментальных снимков узлов и обработаю их вне обхода.

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

Я использовал Parallel.ForEach (узлы, Traverse) для каждого алгоритма обхода, где узлы содержали все ~ 250 тыс. Узлов. Это имитировало (как бы) множество пользователей, одновременно запрашивающих множество разных узлов.

00256 мс, ширина, первая последовательность

00323 мс, ширина, первая последовательность с работой (я увеличил статический счетчик как «работа»)

01495 мс, Киркс, первый ответ

01143 мс, второй ответ, Svicks

00000 мс, рекурсивный однопоточный, не сделал ' t закончить через 60 секунд

00000ms Ответ Enigmativity не завершился через 60 секунд

@Enigma, я думаю, что возможно я каким-то образом испортил ваш алогритм, потому что похоже, что это должно быть намного быстрее.

Результаты удивил меня мягко говоря. Мне пришлось немного поработать с последовательностью в ширину, чтобы убедить себя в том, что компилятор не оптимизирует обходы волшебным образом.

Для одного обхода головы распараллеливание первого уровня дает наилучшую производительность. Но едва,это число улучшилось, поскольку я добавил больше узлов на второй уровень (2000 вместо 500).