tipo - Cruce de árboles paralelos en C#

recorrer matriz c#

Question

Necesito atravesar un árbol rápidamente, y me gustaría hacerlo en paralelo. Prefiero usar las extensiones paralelas que manualmente subir un montón de hilos.

Mi código actual se ve así:

   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);
            }
        }
    }

Realmente estaba esperando que Parallel.ForEach tuviese un análogo Parallel.While. Me encontré con el artículo de Stephen Toub sobre la implementación de Parallel While con Parallel.ForEach . Si lo lees correctamente, esto no funcionará porque estoy mutando la cola que estoy tratando de iterar.

¿Debo usar una fábrica de tareas y recursión (y es arriesgado?)? o hay alguna solución simple que estoy pasando por alto?

Editar: @svick

El árbol tiene poco más de 250,000 nodos. La profundidad máxima ahora es de 14 nodos de profundidad, incluida la raíz.

Hay alrededor de 500 nodos desde la raíz, y el resto después tiene una distribución bastante aleatoria. Pronto tendré mejores estadísticas sobre la distribución.

@Enigmativity:

Sí, el árbol está siendo modificado, al mismo tiempo por muchos usuarios, pero normalmente tendré un bloqueo de lectura compartido para el árbol o subárbol, o permitiré lecturas sucias.

Llamadas al nodo. Los niños pueden considerarse atómicos.

DoSomething es realmente uno de varios delegados, para algunas operaciones costosas probablemente juntaré una lista instantánea de nodos y los procesaré fuera del cruce.

Me di cuenta de que probablemente debería mirar el caso general (un subárbol atravesado en lugar de todo el árbol). Para ese fin, corrí transversalmente en cada nodo del árbol y miré el tiempo total.

Usé un Parallel.ForEach (nodos, Traverse) para cada algoritmo transversal, donde los nodos contenían todos los ~ 250k nodos. Esto simuló (tipo de) una gran cantidad de usuarios solicitando simultáneamente una gran cantidad de nodos diferentes.

00256ms Breadth First Sequential

00323ms Breadth First Sequential con trabajo (incrementé un contador estático como "trabajo")

01495ms Kirks Primera respuesta

01143ms Svicks Segunda respuesta

00000ms Recursive Single Threaded no terminó después de los 60s

00000ms La respuesta de Enigmativity no terminó después de los 60

@Enigma, creo que es posible que haya estropeado tu alogrithm de alguna manera, porque parece que debería ser mucho más rápido.

Los resultados me sorprendieron por decir lo menos. Tuve que agregar algo de trabajo a la primera secuencia secuencial solo para convencerme de que el compilador no estaba optimizando mágicamente las travesías.

Para el recorrido único de la cabeza, la paralelización del primer nivel solo tuvo el mejor rendimiento. Pero apenas, este número mejoró ya que agregué más nodos al segundo nivel (2000 en lugar de 500).

Answer 1

Dado que el recorrido del árbol es extremadamente rápido, que las llamadas a los Children son atómicas y que es la naturaleza cara de los delegados de DoSomething que deben ejecutarse en paralelo, esta es mi opinión sobre la solución.

Comencé con la idea de que necesitaba una función que toma un nodo como parámetro, crea una tarea que ejecuta DoSomething , se llama recursivamente a sí misma para crear tareas para todos los nodos DoSomething , y finalmente devuelve una tarea que espera todo el nodo interno. tareas a completar.

Aquí está:

Func<Node, Task> createTask = null;
createTask = n =>
{
    var nt = Task.Factory.StartNew(() =>
    {
        if (n.Property == someValue)
            DoSomething(n);
    });
    var nts = (new [] { nt, })
        .Concat(n.Children.Select(cn => createTask(cn)))
        .ToArray();

    return Task.Factory.ContinueWhenAll(nts, ts => { });
};

Todo lo que se requiere para llamarlo y esperar a que se complete el recorrido es:

createTask(root).Wait();

Probé esto creando un árbol de nodos con 500 niños fuera de la raíz con 14 niveles, con 1 o 2 hijos subsiguientes por nodo. Esto me dio un total de 319,501 nodos.

DoSomething un método DoSomething que realizó algún trabajo - for (var i = 0; i < 100000 ; i++) { }; - y luego ejecuté el código anterior y lo comparé con el procesamiento del mismo árbol en serie.

La versión paralela tomó 5,151 ms. La versión secuencial 13,746 ms.

También realicé una prueba en la que reduje la cantidad de nodos a 3.196 y DoSomething tiempo de procesamiento de DoSomething en 100x. El TPL vuelve muy inteligentemente a ejecutarse secuencialmente si sus tareas se completan rápidamente, por lo que alargar el tiempo de procesamiento hizo que el código se ejecutara con más paralelismo.

Ahora la versión paralela tomó 3,203ms. La versión secuencial tomó 11,581ms. Y, si solo llamé a la función createTask(root) sin esperar a que se complete, solo tomó 126ms. Esto significa que el árbol se atraviesa muy rápido, y entonces tendría sentido bloquear el árbol durante el recorrido y desbloquearlo cuando se está procesando.

Espero que esto ayude.

Answer 2

Puede que me esté perdiendo algo, pero no veo la necesidad de un while en absoluto. El while es solo garantizar que itere sobre cada nodo.

En su lugar, simplemente llame a su función recursivamente para cada nodo en el árbol.

public void Traverse(Node root)
{         
    if (root.Property = someValue) DoSomething(node);    
    Parallel.ForEach<Node>(root.Children, node => Traverse(node));
} 

editar: por supuesto, la alternativa, si prefiere procesar horizontalmente en lugar de verticalmente y su costosa operación es DoSomething, es hacer primero la poligonal.

public IEnumerable<Node> Traverse(Node root)
{
    // return all the nodes on this level first, before recurring
    foreach (var node in root.Children)
    {
        if (node.Property == someValue)
            yield return node;
    }

    // next check children of each node
    foreach (var node in root.Children)
    {
        var children = Traverse(node);
        foreach (var child in children)
        {
            yield return child;
        }
    }
}

Parallel.ForEach<Node>(Traverse(n), n => DoSomething(n));

Answer 3

Suponiendo que tienes procesadores p , tal vez hagas un paralelo. Para más de root.Children con particiones p . Cada uno de estos haría el recorrido tradicional de un solo hilo sobre los subárboles, compare y, en lugar de DoSomething , enrutaría a un delegado a DoSomething a una cola simultánea. Si la distribución es básicamente aleatoria y equilibrada, y como el recorrido solo atraviesa / pone en cola, esa parte tarda 1 / vez. Además, es probable que el cruce se agote antes de que se ejecuten todos los DoSomethings , por lo que podría tener p consumidores (ejecutores de DoSomething ) que le den la ejecución paralela máxima, suponiendo que todas estas operaciones son independientes.

Con esta partición ingenua a través del número de hijos raíz con subárboles distribuidos aleatoriamente, el recorrido en sí será rápido. Con sus consumidores más o menos asignados por procesador, también obtiene la acción paralela DoSomething .

Answer 4

La forma más directa sería crear una Task para cada nodo secundario y luego esperar a todos ellos:

public void Traverse(Node root)
{
    if (node.Property == someValue)
        DoSomething(node);

    var tasks = new List<Task>();

    foreach (var node in node.Children)
    {
        // tmp is necessary because of the way closures close over loop variables
        var tmp = node;
        tasks.Add(Task.Factory.StartNew(() => Traverse(tmp)));
    }

    Task.WaitAll(tasks.ToArray());
}

Task es bastante liviana, por lo que crear muchas de ellas funciona razonablemente bien. Pero tienen algunos gastos generales, por lo que hacer algo más complicado como tener algunas tareas que comparten una cola probablemente sea más rápido. Si esa es la forma en que vas a ir, no olvides que la cola vacía no significa que todo el trabajo está hecho. Las clases del espacio de nombres de System.Collections.Concurrent serán útiles si fueras de esta manera.

EDITAR: debido a la forma del árbol (la raíz tiene alrededor de 500 niños), procesar solo el primer nivel en paralelo debería dar un buen rendimiento:

public void Traverse(Node root, bool parallel = true)
{
    if (node.Property == someValue)
        DoSomething(node);

    if (parallel)
    {
        Parallel.ForEach(node.Children, node =>
        {
            Traverse(node, false);
        });
    }
    else
    {
        foreach (var node in node.Children)
        {
            Traverse(node, false);
        }
    }
}

Answer 5

Tal vez usar una lista o matriz en lugar de cola ayudaría. También use otra Lista / Matriz para llenar los siguientes nodos a visitar. No procesará la lista hasta que termine todo el ancho primero de todos modos. Algo como esto:

List<Node> todoList = new List<Node>();
todoList.Add(node);
while (todoList.Count > 0)
{
    // we''ll be adding next nodes to process to this list so it needs to be thread-safe
    // or just sync access to a non-threadsafe list
    // if you know approx how many nodes you expect, you can pre-size the list
    ThreadSafeList<Node> nextList = new ThreadSafeList<Node>();  

    //todoList is readonly/static so can cache Count in simple variable
    int maxIndex  =  todoList.Count-1;
    // process todoList in parallel
    Parallel.For(0, maxIndex, i =>
    {
        // if list reads are thread-safe then no need to sync, otherwise sync
        Node x = todoList[i];

        //process x;
        // e.g. do somehting, get childrenNodesToWorkOnNext, etc.

        // add any child nodes that need to be processed next
        // e.g. nextList.add(childrenNodesToWorkOnNext);
    });

   // done with parallel processing by here so use the next todo list
   todoList = nextList;
)