Preciso atravessar uma árvore rapidamente e gostaria de fazê-lo em paralelo. Prefiro usar as extensões paralelas do que girar manualmente um monte de thread

Meu código atual é mais ou menos assim:

   public void Traverse(Node root)
    {
        var nodeQueue = new Queue<Node>();
        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);
            }
        }
    }

Eu estava realmente esperando que o Parallel.ForEach tivesse um analógico Parallel.While. Me deparei com o artigo de Stephen Toub emImplementing Parallel Enquanto com Parallel.ForEach. Se a ler corretamente, isso ainda não funcionará, porque estou mudando a fila que estou tentando repeti

Preciso usar uma fábrica de tarefas e recursão (e isso é arriscado?)? ou existe alguma solução simples que estou ignorando?

Edit: @ svick

A árvore tem pouco mais de 250.000 nós. A profundidade máxima agora é de 14 nós, incluindo a rai

Existem cerca de 500 nós fora da raiz, e o saldo a seguir tem uma distribuição bastante aleatória. Em breve, vou obter estatísticas melhores sobre a distribuição.

@ Enigmatividade:

im, a árvore está sendo modificada simultaneamente por muitos usuários, mas normalmente terei um bloqueio de leitura compartilhado para a árvore ou subárvore ou permitirei leituras suja

s chamadas podem ser consideradas atômica

DoSomething é realmente um dos vários delegados, para algumas operações caras, provavelmente reunirei uma lista instantânea de nós e os processarei fora do percurs

Eu percebi que provavelmente deveria olhar para o caso geral (uma subárvore sendo atravessada em vez de toda a árvore). Para esse fim, percorri todos os nós da árvore e observei o tempo tota

Eu usei um Parallel.ForEach (nós, Traverse) para cada algoritmo transversal, onde os nós continham todos os ~ 250k nós. Simulou (mais ou menos) muitos usuários solicitando simultaneamente vários nós diferentes.

00256ms Largura Primeiro Sequencial

00323ms Largura do primeiro seqüencial com trabalho (eu incrementei um contador estático como "trabalho")

01495ms Kirks Primeira resposta

01143ms Svicks Segunda resposta

00000ms O único segmento recursivo não terminou após os anos 60

00000ms A resposta da enigmatividade não terminou depois dos anos 60

@ Enigma, acho que é possível que eu tenha estragado o seu alogritmo de alguma forma, porque parece que deve ser muito mais rápid

Os resultados me surpreenderam para dizer o mínimo. Eu tive que adicionar algum trabalho ao primeiro seqüencial de largura apenas para me convencer de que o compilador não estava otimizando magicamente as travessia

Para a travessia única da cabeça, paralelizar o primeiro nível apenas teve o melhor desempenho. Mas, apenas por pouco, esse número melhorou à medida que adicionei mais nós ao segundo nível (2000 em vez de 500