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

Question

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

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

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

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

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

Edit: @svick

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

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

@ Энигмативность:

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

Звонки на узел. Детей можно считать атомарными.

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

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

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

00256ms Ширина первая последовательность

00323ms Первый шаг ширины с работой (я увеличил статический счетчик как «работа»)

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

01143мс Свикс Второй ответ

00000ms Рекурсивная однопоточная обработка не завершилась через 60 с

00000ms Ответ Энигмативности не закончился через 60 с

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

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

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

Answer 1

Самый прямой способ - создать Task для каждого дочернего узла, а затем подождать всех их:

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 довольно легкий, поэтому их создается много.работает достаточно хорошо.Но у них есть некоторые накладные расходы, поэтому выполнение чего-то более сложного, например, выполнение нескольких задач с общей очередью, вероятно, будет быстрее.Если вы идете по этому пути, не забывайте, что пустая очередь не означает, что вся работа выполнена.Классы из пространства имен System.Collections.Concurrent пригодятся, если вы пойдете этим путем.

РЕДАКТИРОВАТЬ: Из-за формы дерева (корень имеет около 500 дочерних элементов), обработка толькопервый параллельный уровень должен дать хорошую производительность:

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 2

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

Я начал с идеи, что мне нужна функция, которая принимает узел в качестве параметра, создает задачу, которая выполняет DoSomething, рекурсивно вызывает себя для создания задач для всех дочерних узлов и, наконец, возвращаетЗадача, которая ожидает завершения всех внутренних задач.

Вот оно:

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

Все, что требуется для его вызова и ожидания завершения обхода:

createTask(root).Wait();

Я проверил это, создав дерево узлов с 500 дочерними элементами от корня с 14 уровнями, с 1 или 2 последующими дочерними элементами на узел.Это дало мне в общей сложности 319 501 узел.

Я создал DoSomething метод, который выполнил некоторую работу - for (var i = 0; i < 100000 ; i++) { }; - и затем запустил приведенный выше код и сравнил его с последовательной обработкой одного и того же дерева.

Параллельная версия заняла 5,151 мс.Последовательная версия 13 746 мс.

Я также выполнил тест, в котором уменьшил количество узлов до 3196 и увеличил время обработки для DoSomething в 100 раз.TPL очень умно возвращается к последовательному запуску, если его задачи выполняются быстро, поэтому увеличение времени обработки заставляет код работать с большей параллелизмом.

Теперь параллельная версия заняла 3203 мс.Последовательная версия заняла 11 581 мс.И если бы я только вызвал функцию createTask(root), не дожидаясь ее завершения, это заняло бы всего 126 мс.Это означает, что дерево перемещается очень быстро, и тогда имеет смысл заблокировать дерево во время обхода и разблокировать его во время обработки.

Надеюсь, это поможет.

Answer 3

Я мог бы что-то упустить, но я вообще не вижу необходимости в while. while просто гарантирует, что вы выполняете итерацию по каждому узлу.

Вместо этого просто вызовите вашу функцию рекурсивно для каждого узла в дереве.

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

edit: конечно, альтернатива, если вы предпочитаете обрабатывать горизонтально, а не вертикально, и ваша дорогая операция - DoSomething, - это сначала сделать Traverse.

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 4

Если у вас есть p процессоры, возможно, вы делаете Parallel.For более root.Children с p разделами. Каждый из них будет выполнять традиционный однопотоковый обход по поддеревьям, сравнивать и вместо DoSomething ставить делегата в очередь DoSomething в параллельную очередь. Если распределение в основном случайное и сбалансированное, и поскольку обход только выполняет обход / постановку в очередь, эта часть занимает 1 / p -й раз. Кроме того, обход, вероятно, исчерпает себя до того, как все DoSomethings будут выполнены, так что вы можете иметь p потребителей (исполнителей DoSomething ), дающих вам максимальное параллельное выполнение, предполагая все эти операции независимы.

При таком наивном разбиении на число корневых потомков со случайно распределенными поддеревьями сам обход будет быстрым. Когда ваши потребители примерно распределены по процессорам, вы также получаете максимальное параллельное DoSomething действие.

Answer 5

Возможно, использование List или Array вместо очереди поможет. Также используйте другой список / массив, чтобы заполнить следующие узлы для посещения. Вы не будете обрабатывать список, пока не закончите сначала всю ширину. Примерно так:

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