Всем привет, меня зовут Антон, я Java‑разработчик в Сбере, подразделение SberWorks. Я разрабатываю Giga IDE — новую IDE на основе IntelliJ IDEA. В ходе работы столкнулся с тем, что при открытии проектов происходит сканирование всех папок для поиска тех или иных файлов. Если обобщить, то задача сводится к обходу дерева. Я решил подробнее рассмотреть эту тему, причём с прицелом на многопоточность.

Обход в глубину и в ширину

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

Говорят, что обход в ширину хорош при широких деревья, когда узлов на каждом уровне достаточно много, а самих уровней мало. А обход в глубину хорош, когда уровней много, а узлов на каждом уровне мало. В случае проектов в IDE деревья, видимо, скорее узкие, чем широкие, потому что мы, разработчики, не очень любим папки с большим количеством файлов, а стремимся к большему порядку и структуре. Но это не точно. Поэтому мы рассмотрим оба подхода, сначала в классическом однопоточном варианте, а потом в многопоточном.

Вот характеристики ноутбука, на котором проводил тесты:

Процессор: AMD Ryzen 5 6600U with Radeon Graphics, 
Семейство: 25
Модель: 68
Потоков на ядро: 2
Ядер на сокет: 6
Память: 30 Гб
Накопитель: NVMe
ОС: SberOS GNU/Linux
SDK: OpenJDK 21

Однопоточные реализации

В качестве тестового примера я буду искать XML‑файлы по расширению в дереве на 5000 (59), 50 000 (1944) и 150 000 (4317) узлов. В скобках указано количество XML‑файлов в этих директориях (примерно 3% от общего количества).

public static boolean processFilesRecursively(final @NotNull VirtualFile root,
                                              final @NotNull Processor<? super VirtualFile> processor) 

Мне интересны все эти подходы с точки зрения производительности, поэтому хорошо бы иметь какой эталонный вариант, к результату которого можно стремится. Я решил, что это будет Linux‑утилита find, благо у меня SberOS (предок — Debian). Команда find явно написана на С и работает в один поток. Если мы её трассируем, то никаких pthread не найдём. Как бы там ни было, возьмём её за эталон, выполним 10 раз и выведем всё в /dev/null:

#!/bin/bash
for number in {1..10}
do
    time find $1 -type f -name *.xml > /dev/null
done

Получим следующие числа для ориентира:

Даже для сверхбыстрого C и Linux задача оказалась не такой уж простой. При реально большом проекте время обхода дерева (причём критерий для фильтра тут простой) окажется уже вполне заметным. В скобках указана длительность выполнения первой итерации, и оно всегда больше, чем у всех последующих, как будто получается какой‑то прогрев, но не Java, а Linux. Знатоки Linux, напишите, почему так?

Ну хорошо, а что нам может предложить Java? Первое — это Files.walkFileTree, реализация будет такой:

public List<Path> collect(Path path) throws IOException {
    List<Path> result = new ArrayList<>();
    Files.walkFileTree(path, new SimpleFileVisitor<>() {
        @Override
        public FileVisitResult visitFile(Path file, BasicFileAttributes attrs) {
            if (Files.isRegularFile(file) && file.endsWith(".xml")) {
                result.add(file);
            }
            return FileVisitResult.CONTINUE;
        }
    });
    return result;
}

Честно прогоняем через JMH и получаем следующие числа:

Да, печально. На средних по величине проектах получаем результат более чем вдвое медленнее, чем find.

Ещё есть Files.walk. Это подход уже современней, реализация будет такой (строчек меньше, смысл тот же):

public List<Path> walk(String dir, int depth) throws IOException {
    try (Stream<Path> stream = Files.walk(Paths.get(dir), depth)) {
        return stream.filter(file -> Files.isRegularFile(file)
                        && file.endsWith(".xml")).toList();
    }
}

Результаты:

Лучше не стало. Если залезть «под капот», то можно заметить, что оба метода используют один и тот же объект: FileTreeWalker, просто немного разная обвязка. Дерево обходится в ширину, поэтому и результаты очень схожи.

Тогда я решил самостоятельно реализовать два самых известных алгоритма обхода дерева. Первым был обход в глубину, то есть методом рекурсии. Реализация:

public static List<File> recursion(File root, List<File> result) {
    if (root.isDirectory()) {
        for (File f : root.listFiles()) {
            recursion(f, result);
        }
    } else {
        if (root.getName().endsWith(".xml")) {
            result.add(root);
        }
    }
    return result;
}

Результат:

Здесь уже намного лучше, и чем больше узлов и файлов, тем ближе мы к find.

А если в ширину? Для реализации этого метода обхода нужна дополнительная коллекция. Я использую ArrayDeque<T>, a если вместо неё использовать Stack<T>, то обход будет итерационный, но в глубину. То есть со сменой коллекции меняется и подход. В глубину мы уже обходили, потому реализация на очереди:

public List<File> iterations(File root) {
    List<File> result = new ArrayList<>();
    Queue<File> queue = new ArrayDeque<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        File file = queue.remove();
        if (file.isDirectory()) {
            queue.addAll(Arrays.stream(file.listFiles()).toList());
        } else {
            if (file.getName().endsWith(".xml")) {
                result.add(file);
            }
        }
    }
    return result;
}

Обход в ширину оказался всё‑таки немного медленнее, чем в глубину. Значит деревья проектов больше глубокие, чем широкие?

В любом случае, самостоятельные упрощённые реализации дали гораздо лучший результат по производительности, чем библиотечные методы. Видимо, в этом случае, чем проще — тем лучше.

Многопоточные реализации

Рекурсивный метод в глубину хорош, но всё равно хотелось быстрее. Как известно, в Java есть ForkJoinPool, а в рамках этого API — RecursionTask, которые помогут обойти дерево в глубину, да ещё и в несколько потоков. Сначала алгоритм будет очень простым: если в узле дерева директория — мы делаем fork и создаём новую задачу; если в узле файл — проверяем, что это XML; если так, то забираем в результат, иначе — игнорируем. Реализация у меня сразу стала почти обобщённой, таким образом можно обходить любое дерево, не только файловую систему:

public class MultiThreadWalker<T> {
    private final Predicate<T> filter;
    private final ChildSupplier<T> supplier;
    private final T root;
    private final Predicate<T> forkPredicate;

    public MultiThreadWalker(T root, Predicate<T> filter, Predicate<T> forkPredicate, ChildSupplier<T> supplier) {
        this.root = root;
        this.filter = filter;
        this.supplier = supplier;
        this.forkPredicate = forkPredicate;
    }

    public List<T> collect() {
        WalkTask<T> task = new WalkTask<>(root, filter, forkPredicate, supplier);
        return task.invoke();
    }

    public static class WalkTask<T> extends RecursiveTask<List<T>> {
        private final T root;
        private final Predicate<T> filter;
        private final ChildSupplier<T> supplier;
        private final Predicate<T> forkPredicate;

        public WalkTask(T root, Predicate<T> filter, Predicate<T> forkPredicate, ChildSupplier<T> supplier) {
            this.root = root;
            this.filter = filter;
            this.supplier = supplier;
            this.forkPredicate = forkPredicate;
        }

        @Override
        protected List<T> compute() {
            List<WalkTask<T>> tasks = new ArrayList<>();
            List<T> result = new ArrayList<>();

            for (T t : supplier.getChildren(root)) {
                if (forkPredicate.test(t)) {
                    tasks.add(new WalkTask<>(t, filter, forkPredicate, supplier));
                }

                if (filter.test(t)) {
                    result.add(t);
                }
            }

            result.addAll(
                    ForkJoinTask.invokeAll(tasks)
                    .stream()
                    .map(ForkJoinTask::join)
                    .flatMap(Collection::stream)
                    .toList());

            return result;
        }
    }

    @FunctionalInterface
    public interface ChildSupplier<T> {
        T[] getChildren(T t);
    }
}

MultiThreadWalker<File> multiThreadWalker = new MultiThreadWalker<>(
        new File(PATH),
        f -> f.getName().endsWith(".xml"),
        File::isDirectory,
        File::listFiles);
multiThreadWalker.collect();

Результаты:

Ого! Как тебе такое, Илон Маск! Многопоточный алгоритм дал результат в среднем в 4 раза лучше, чем find, причём на любых выборках (хотя казалось, что на маленьких деревьях накладные расходы съедят всю выгоду). Класс! Прирост есть, причем не на проценты, а в разы.

Во всех многопоточных примерах я запускаю задачи через invoke(), никак не ограничивая многопоточность. Возможно, если использовать эти методы в реальных условиях, то необходимо будет создать свой forkJoinPool и ограничить количество потоков.

Дальше попробуем сделать многопоточный обход дерева в ширину. Минимально изменим однопоточный алгоритм: набираем узлы в коллекцию, а потом по классической схеме делим её пополам на две другие задачи.

Реализация:

public class MultiThreadIteration extends RecursiveTask<List<File>> {
    private final int DIRS_LIMIT = 5000;
    private final List<File> root;

    public MultiThreadIteration(List<File> root) {
        this.root = root;
    }

    @Override
    public List<File> compute() {
        List<File> result = new ArrayList<>();
        Queue<File> queue = new ArrayDeque<>(root);

        while (!queue.isEmpty()) {
            File file = queue.remove();
            if (file.isDirectory()) {
                queue.addAll(Arrays.stream(file.listFiles()).toList());
                if (queue.size() > DIRS_LIMIT) {
                    result.addAll(ForkJoinTask.invokeAll(createSubtasks(queue.stream()
                                    .toList())).stream().map(ForkJoinTask::join)
                            .flatMap(Collection::stream).toList());
                    return result;
                }
            } else {
                if (file.getName().endsWith(".xml")) {
                    result.add(file);
                }
            }
        }
        return result;
    }

    private Collection<MultiThreadIteration> createSubtasks(List<File> dirs) {
        List<MultiThreadIteration> dividedTasks = new ArrayList<>();
        dividedTasks.add(new MultiThreadIteration(dirs.subList(0, dirs.size() / 2)));
        dividedTasks.add(new MultiThreadIteration(dirs.subList(dirs.size() / 2, dirs.size())));
        return dividedTasks;
    }
}

В этих случаях может возникнуть вопрос: «Когда делить коллекцию на две части, при достижении какой длины?» За это отвечает константа DIRS_LIMIT. Я пробовал значения 50, 500 и 5000. Наилучший результат был при 50, а если ставить меньше, то мы будем семантически приближаться к многопоточному рекурсивному методу, что уже не имеет смысла. Результаты при DIRS_LIMIT = 50:

Числа хорошие. Очень сильно приближаются к рекурсивному многопоточному методу (на средних по величине проектах даже быстрее), и, следовательно, в разы опережают find.

В рекурсивном методе сходу видно неоптимальное решение — форк на каждой директории, хотя частенько одна директория просто вложена в другую (там чаще всего структура типа /src/main/java/...). Можно было бы просто следовать вглубь структуры, поэтому я создал некий гибридный вариант, когда мы набираем папки в ширину и при достижении лимита делимся на две части, но основной обход выполняем рекурсивно. То есть взял всё лучшее из двух методов.

Реализация (привожу только код RecursionTask):

public class HybridTask extends RecursiveTask<List<File>> {
    private final File[] root;

    public HybridTask(File[] root) {
        this.root = root;
    }

    @Override
    protected List<File> compute() {
        return computeRecursively(root, new ArrayList<>());
    }

    private List<File> computeRecursively(File[] rootDirs, List<File> results) {
        List<File> dirs = new ArrayList<>();

        for (File dir : rootDirs) {
            for (File file : dir.listFiles()) {
                if (file.isDirectory()) {
                    dirs.add(file);
                } else if (file.getName().endsWith(".xml")) {
                    results.add(dir);
                }

            }
        }

        if (dirs.size() >= DIRS_LIMIT) {
            results.addAll(ForkJoinTask.invokeAll(createSubtasks(dirs)).stream().map(ForkJoinTask::join)
                    .flatMap(List::stream).toList());
            return results;
        } else {
            if (!dirs.isEmpty()) {
                return computeRecursively(dirs.toArray(new File[0]), results);
            }
        }
        return results;
    }

Оказалось, что такой «умный» проход не даёт никаких преимуществ. Иногда простота — залог успеха.

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

На самом деле, приглядевшись и взглянув в профилировщик, мы сразу найдём самые долгие методы — те, которые в конце концов идут в ядро и делают системные вызовы в Linux, со всеми вытекающими последствиями. Здесь есть два таких метода: File.listFiles() и File.isDirectroy(). Что мы можем сделать в таком случае? Только одно: не делать этих вызовов. listFiles() убрать нельзя, но можно заменить на list(), который вернёт не массив файлов, а массив строк, что немного всё упрощает. После этого можно убрать isDirectory(), будем лишь проверять, что путь заканчивается на .xml.

Сделаем так:

@Override
protected List<String> compute() {
    List<WalkTask> tasks = new ArrayList<>();
    List<String> result = new ArrayList<>();
    String[] files = root.list();

    if (files == null) {
        return Collections.emptyList();
    }

    for (String file : files) {
        if (file.endsWith(".xml")) {
            result.add(file);
        } else {
            tasks.add(new WalkTask(new File(root, file)));
        }
    }

    result.addAll(ForkJoinTask.invokeAll(tasks)
            .stream()
            .map(ForkJoinTask::join).flatMap(Collection::stream).toList());

    return result;
}

Тогда мы получим хороший прирост скорости, но вдобавок к этому можем получить директории с именем типа my.xml. Да, никто не запрещает так назвать директорию. Поэтому проверяем чуть выше, после того, как нашли все пути. Переводим в File и фильтруем по isDirectory(). В таком случаем мы вызываем isDirectory() не 150 тыс. раз, а только на результате:

public List<File> collect() {
    WalkTask task = new WalkTask(root);
    List<String> paths = task.invoke();

    return paths.stream().map(File::new).filter(f->!f.isDirectory()).toList();
}

Все эти манипуляции привели к росту производительности в среднем еще на 40 %. Ура! Быстрее, чем find в 6 раз. Быстрее, чем библиотечные методы в 12 раз!

Также была надежда, что я смогу добиться ещё более лучшего результата, используя CountedCompleter (развитие ForkJoinTask), но нет, быстрее не стало, даже немного ухудшилось на большой выборке: 0,004 ± 0,001, 0,049 ± 0,002 и 0,165 ± 0,001 на 5 тыс., 50 тыс. и 150 тыс. файлов соответственно. Но реализация всё‑таки интересная, поэтому положил её в Git.

А что на Windows?

Все свои эксперименты я проводил на рабочем ноутбуке на SberOS (Linux), Windows есть только на домашнем компьютере. Там совсем другое железо и другие проекты, файлы и файловая система в целом, поэтому сравнить напрямую две ОС не получится. Но и не об эта статья. Меня больше интересует разница в производительности между однопоточными и многопоточными реализациями.

Характеристики домашней машины:

Процессор: AMD Ryzen 5 3600
Потоков на ядро: 2
Ядер на сокет: 6
Память: 30 Гб
Накопитель: HP SSD FX900 Plus M.2, 1 Тб
ОС: Windows 10
SDK: OpenJDK 21

В итоге подобрал сопоставимые по количеству файлов проекты и провёл тесты:

Интересные результаты: на Windows библиотечные методы и методы собственного производства практически равны, библиотечные даже немного быстрее. Что же касается многопоточных версий, то здесь тоже кратные приросты, примерно в 6–7 раз.

Выводы

Библиотечные методы обхода файловой системы универсальны, видимо, поэтому их производительность оставляет желать лучшего (по крайней мере, на Linux‑машинах). Если необходимо быстро обойти глубокое дерево, то лучше всего написать свой простой рекурсивный метод обхода в глубину. Если дерево широкое, то можно дополнительно реализовать обход в ширину и сравнить результат.

Многопоточные версии выигрывают даже у стандартных Linux‑утилит, которые написаны на С, причём примерно в 6 раз. Гибридный и более усложнённый алгоритм, к сожалению, прироста скорости не дал, также как и переход со списков на массивы и со стримов на циклы, так как в случае обхода файловой системы узким горлышком являются вызовы в ядро ОС. Следовательно, надо стараться по возможности их не делать, или хотя бы делать их меньшее количество раз.

GitHub: https://github.com/devs‑lair/walker