Обход дерева в несколько потоков

[Ketovdk]

Первый поток обходит дерево начиная с корня на всю глубину по «крайне левому» пути, т.е. всегда при перемещении вглубь поворачивает налево или другими словами всегда выбирает последний дочерний узел.
Параллельно первый поток собирает все пропущенные дочерние узлы и отправляет их в очередь (либо в стек) где их забирает другой поток, очередь или стек должны реализовывать многопоточный подход, и алгоритм повторяется, подставляя на место корня только-что взятый узел.

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

[mayorovp]

Вы используете Executor неправильно! В него нужно отправлять не потоки, а отдельные задачи.

Если уж вы создали несколько потоков MultiThreadTreeWalker — вам их нужно просто взять и запустить, их не надо отправлять для запуска в Executor, это глупо. Кстати, поток запускается вызовом start, а не run.

Если же вы решили использовать Executor, а не потоки — то вам не нужна очередь, очередь уже есть внутри Executor! Все, что вам требуется — создать по задаче на каждый узел дерева, и отправить их в Executor...

Как-то так оно должно в итоге выглядеть:

private Executor ex;

void reviewFileSystem(File f) {
    if (f.isFile()) {
        // ...
        return;
    }

    for (File f2 : f.listFiles()) {
        ex.execute(() -> reviewFileSystem(f2));
    }
}

Как видно, код на порядок проще вашего.

Отдельная проблема — как дождаться окончания подобного обхода, но вы её решать даже не пытались.

[alexeykuzmin0]

А не проще использовать BFS? Стандартный алгоритм, от DFS отличается только одним — очередь вместо стека. В первую очередь обходит вершины, близкие к корню.

[Ketovdk]

вообще, это сильно зависит от такого, какое дерево выстраивают данные. Если это файловая система, то скорее всего максимальная глубина сильно меньше максимальной ширины одного уровня, следовательно затраченная память (и время на ее алокацию и очистку) меньше при DFS не смотря на использование стека.

[mayorovp]

В многопоточном варианте "порядок обхода вершин" — оксюморон, так что BFS и DFS ничем и не отличаются.

[alexeykuzmin0]

Ну потоки же нужны не для того, чтобы были, а с какой-то целью. Автор описывает ее как

многопоточный поиск файлов может дать ускорение, в случае, когда один-единственный поток ищет файл в многоуровневой иерархии, а искомый файл лежит в соседней папке с одним уровнем

Вот и возникает закономерный вопрос — а зачем изобретать велосипед, если можно взять BFS (однопоточный).

[Karl_Marx]

1) Очень похоже на паттерн producer-consumer, где в качестве буфера выступает стек. Правда, конкретно в этом случае, один поток является одновременно и производителем и потребителем.
2) Не знаю, как в Java, а на .Net можно было бы сделать все это в один поток, но асинхронно, не нагружая CPU, но нагрузив при этом SSD по полной. Подозреваю, что в Java так тоже можно.
3) Кроме того, если это просто поиск файла и важна скорость, то на винде и, возможно, в линухе, для этого есть служба индексирования файлов.

[Labunsky]

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

По поводу алгоритма

Если отбросить все детали реализации (а там есть над чем работать) и оставить только сам алгоритм, то при распараллеливании стоит задуматься в первую очередь над КПД потоков:

• Во-первых, в исходном алгоритме рабочий за раз обрабатывает самостоятельно лишь одну ветвь под-дерева, все остальные отправляя в блокирующую структуру. Каждый вызов add и take блокирует все остальные аналогичные вызовы, тем самым образуется "бутылочное горлышко"
• Во-вторых, первый поток почему-то отличается от остальных и прекращает свою жизнь на первом же встретившимся листе, что не имеет практического смысла

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

1. Создает счетчик T = N-1;
2. Если у рассматриваемого узла есть M потомков (он папка):
   
   1. Если M < N, то шаг пропускается. Иначе, делит потомков на N частей, для N-1 из них:
      
      • Если T > 0, то присваивает T = T-1 и создает новый поток (который будет работать по тому же алгоритму с шага 2), передает ему для обработки рассматриваемую часть;
      • Если T == 0, то добавляет всю часть одной задачей в очередь;
   2. Если K >= N, то берет оставшующуюся N-ую часть из разделения на шаге 3;
   3. Иначе берет задачу из очереди;
3. Иначе (если файл) — обрабатывает его и возвращается на предыдущий уровень рекурсии;
4. Рекурсивно повторяет алгоритм для каждого файла из новой задачи с шага 2.

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

Стоит лишь заметить, что операции с T должны быть синхронизированы между потоками. В отличие от синхронизации на очереди, это ограничение легко обойти, храня локальную копию значения, и выполняя синхронизацию на шаге 2.1 только когда она > 0

По поводу реализации

Помимо сказанного другими выше, в коде не отслеживается конец задачи. Решение тривиально: нужно лишь проверять перед взятием новой задачи, сколько потоков в настоящий момент уже ждут у нее. Если значение равно N-1, значит, работы больше не светит, программу можно сворачивать

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

Не стоит просто игнорировать исключения в потоках — если добавил try, то сделай обработку в catch, иначе просто пробрось его наверх. И проверяй неявные исключения — listFiles() иногда возвращает null, в следующей строчке может получиться NullPointerException

И напоследок — очень советую использовать встроенные в джаву функции работы с потоками, не ограничивая себя одним интерфейсом блокирующей очереди

[UladzislauSafronau]

Для больших деревьев, которые имеет смысл обходить в несколько потоков гораздо удобнее будет использовать ForkJoinPool

[KvanTTT]

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

Очень актуально для алгоритмов альфа-бета отсечения и подобных, которые используются в антагонистических играх, таких как шахматы, реверси и других. Сложность заключается в том, что на каждом узле нужно решать, создавать ли новый поток или оставаться в старом? Причем делать это скорее всего динамически.

Правда в играх с очень большим фактором ветвления (например, го), такие методы будут неэффективны. Тогда используется алгоритм перебор дерева методом Монте-Карло. Его, к счастью, распараллелить уже относительно легко, т.к. используется элемент случайности.

[YogurtTheHorse]

А там в итоге есть какойто прирост к скорости, если сравнивать с однопоточным обходом? Если да, то можно было бы взглянуть на бенчмарки?

А то как-то это странно все выглядит

[avkomlev]

Всем спасибо за комментарии! В данный момент работаю над второй частью поста в которой будут бенчмарки по вышеупомянутым алгоритмам. Когда выйдет точно не могу сказать =)