3

Как распараллелить процесс поиска по папкам?

public  IEnumerable<string> GetDirectoryFiles(string rootPath, string patternMatch, SearchOption searchOption)
{
    
    var foundFiles = Enumerable.Empty<string>();

    if (searchOption == SearchOption.AllDirectories)
    {
        try
        {
            IEnumerable<string> subDirs = Directory.EnumerateDirectories(rootPath);
            foreach (string dir in subDirs)
            {
                foundFiles = foundFiles.Concat(GetDirectoryFiles(dir, patternMatch, searchOption)); // Add files in subdirectories recursively to the list
            }
        }
        catch (UnauthorizedAccessException ex) { LoggingExtensions.WriteDebug(ex.Message); }
        catch (PathTooLongException ex) { LoggingExtensions.WriteDebug(ex.Message); }
    }

    try
    {
        var files = Directory.EnumerateFiles(rootPath, patternMatch);
        foundFiles = foundFiles.Concat(files); 
        var z = foundFiles.Distinct().ToList();
    }
    catch (UnauthorizedAccessException ex) { LoggingExtensions.WriteDebug(ex.Message); }
    return foundFiles;
}
12
  • 2
    Вообще конечно можно, ведь это обычный поиск в ширину\глубину. Но 1) зачем параллелить именно рекурсивный вариант? 2) Надо ли вообще параллелить работу с жестким диском? 3) Собираетесь ли вы контроллировать уровень параллелизма?
    – tym32167
    22 янв 2021 в 17:43
  • 7
    Доступ к накопителю (не важно - HDD, SSD, CD/DVD) всё равно последовательный, поэтому от параллелизации толку практически не будет. Параллелить нужно не IO-доступ, а CPU-задачи. 22 янв 2021 в 18:08
  • 1
    @AlexanderPetrov а для SSD это точно без разницы? Пошел гуглить, вот в ответе кто-то измерения проводил на скорость чтения. SSD показал лучшие значения. 22 янв 2021 в 18:21
  • 3
    Я проверил - убираете строчку var z = foundFiles.Distinct().ToList(); и оно начинает раз в 5 работать быстрее.
    – aepot
    22 янв 2021 в 21:02
  • 2
    @PashaPash - насколько я понимаю, эту операцию - поиск по B-Tree - выполнит драйвер и распараллеливание никак её не улучшит. 23 янв 2021 в 10:20

4 ответа 4

7

Фух, придётся дать свой ответ.

@aepot дал комментарий, что при удалении строки var z = foundFiles.Distinct().ToList(); код начинает раз в 5 работать быстрее.

Почему так получается, откуда ускорение работы? Дело в том, что пока процессор выполняет эту строку кода, нет новых обращений к диску за новой порцией данных. То есть накопитель простаивает.

Удаляем эту строку - получаем более частые IO-запросы.

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

Но не стоит путать это с прямым распараллеливанием доступа к накопителю! Если несколько потоков будут вхолостую читать данные (и никак не использовать их), то они просто будут ждать в очереди.


Полагаю, шаблон producer-consumer является классическим решением проблемы долгой обработки данных: один-единственный поток читает данные с накопителя и складывает их в некую коллекцию, другой(ие) поток(и) берут данные из этой коллекции и обрабатывают. При этом ни один поток не ждёт своей очереди поработать с диском.

6

У меня достаточно быстрый SSD. Как бы я не пытался распараллелить выполнение поиска, оно все равно съедает только один процессор, то есть вся работа ведется где-то драйвером в одном потоке, а мои потоки в приложении просто висят и ждут результатов этой работы. Но так как оверхед на асинхронность и спавн потоков получается весьма существенный, так как я выполнял поиск по всему диску C:\, то и выполнение метода затягивается и получается дольше.

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

Поэтому ответ на ваш вопрос: Распараллеливание здесь бесполезно из-за особенностей работы драйвера файловой системы.

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

Основная проблема вашего метода из вопроса - это то, что он сначала полностью отрабатывает, а затем только возвращает IEnumerable вызывающему методу. То есть сначала отработают все рекурсии, а потом только вы сможете проитерировать результаты. Если быть точнее, то возврат из метода произойдет только тогда, когда отработают все .Concat. Это можно исправить и получать результаты по мере их возвращения файловой системой.

Вторая проблема - баг, неиспользуемая переменная z, вычисления значения которой надо сгенерировать массив, но вы далее ничего с этой переменной не делаете, так что можно просто удалить строчку var z = foundFiles.Distinct().ToList();.

Третья проблема - это то что метод пытается получить файлы из директории, к которой уже известно, что нет доступа. В результате метод генерирует в 2 раза больше исключений, чем могло бы быть в идеале.

После оптимизации рекурсивный метод выглядит вот так:

public IEnumerable<string> GetDirectoryFiles(string rootPath, string patternMatch, SearchOption searchOption)
{
    bool dirSuccess = true;
    if (searchOption == SearchOption.AllDirectories)
    {
        dirSuccess = false;
        IEnumerable<string> subDirs = Enumerable.Empty<string>();
        try
        {
            subDirs = Directory.EnumerateDirectories(rootPath);
            dirSuccess = true;
        }
        catch (UnauthorizedAccessException ex) { LoggingExtensions.WriteDebug(ex.Message); }
        catch (PathTooLongException ex) { LoggingExtensions.WriteDebug(ex.Message); }

        foreach (string dir in subDirs)
        {
            foreach (string path in GetDirectoryFiles(dir, patternMatch, searchOption))
            {
                yield return path;
            }
        }
    }

    // нет смысла пытаться запрашивать файлы, если нет доступа к каталогу или возникла другая ошибка
    if (dirSuccess)
    {
        foreach (string path in Directory.EnumerateFiles(rootPath, patternMatch))
        {
            yield return path;
        }
    }
}

Что можно оптимизировать дальше? То же что и всегда, когда я сталкиваюсь с рекурсивными методами - избавиться от рекурсии. Я попробовал механизмы с массивами и итерированием по большому массиву - особого прироста не получил, а получил его только от метода Directory.EnumerateDirectories с непосредственной передачей параметра SearchOption в него. То есть задачу поиска переложил наполовину на .NET, и вот тогда прирост стал ощутимым, хоть и не фантастическим.

Реализация без рекурсии:

public IEnumerable<string> GetDirectoryFilesFast(string rootPath, string patternMatch, SearchOption searchOption)
{
    foreach (string file in Directory.EnumerateFiles(rootPath, patternMatch))
    {
        yield return file;
    }
    if (searchOption == SearchOption.AllDirectories)
    {
        IEnumerator<string> enumarator = Directory.EnumerateDirectories(rootPath, string.Empty, searchOption).GetEnumerator();
        while (true)
        {
            bool skip = true;
            try
            {
                if (!enumarator.MoveNext())
                    break;
                skip = false;
            }
            catch (UnauthorizedAccessException ex) { LoggingExtensions.WriteDebug(ex.Message); }
            catch (PathTooLongException ex) { LoggingExtensions.WriteDebug(ex.Message); }

            if (skip)
                continue;

            foreach (string file in Directory.EnumerateFiles(enumarator.Current, patternMatch))
            {
                yield return file;
            }
        }
    }
}

Да и сам метод стал выглядеть проще.

Ну и измерил производительность на релизном билде.

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

public static class LoggingExtensions
{
    public static int ErrorsCount { get; set; }
    public static void WriteDebug(string text) { ErrorsCount++; }
}
static void Main(string[] args)
{
    Console.WriteLine("GetDirectoryFiles");
    DateTime date = DateTime.Now;
    int i = 0;
    LoggingExtensions.ErrorsCount = 0;
    foreach (string path in GetDirectoryFiles(@"C:\", "*.cs", SearchOption.AllDirectories)) { i++; }
    Console.WriteLine($"Found {i} files");
    Console.WriteLine($"{LoggingExtensions.ErrorsCount} exceptions thrown");
    TimeSpan elapsed = DateTime.Now - date;
    Console.WriteLine($"Elapsed {elapsed.TotalSeconds}s");

    Console.WriteLine("GetDirectoryFilesOriginal");
    date = DateTime.Now;
    i = 0;
    LoggingExtensions.ErrorsCount = 0;
    foreach (string path in GetDirectoryFilesOriginal(@"C:\", "*.cs", SearchOption.AllDirectories)) { i++; }
    Console.WriteLine($"Found {i} files");
    Console.WriteLine($"{LoggingExtensions.ErrorsCount} exceptions thrown");
    elapsed = DateTime.Now - date;
    Console.WriteLine($"Elapsed {elapsed.TotalSeconds}s");

    Console.WriteLine("GetDirectoryFilesFast");
    date = DateTime.Now;
    i = 0;
    LoggingExtensions.ErrorsCount = 0;
    foreach (string path in GetDirectoryFilesFast(@"C:\", "*.cs", SearchOption.AllDirectories)) { i++; }
    Console.WriteLine($"Found {i} files");
    Console.WriteLine($"{LoggingExtensions.ErrorsCount} exceptions thrown");
    elapsed = DateTime.Now - date;
    Console.WriteLine($"Elapsed {elapsed.TotalSeconds}s");
    Console.ReadKey();
}

Ваш метод из вопроса назван здесь GetDirectoryFilesOriginal и для чистоты эксперимента я воткнул его в неизменном виде в середину, ну чтобы не казалось, что он отработал медленнее из-за того что первое обращение к директориям еще не кешировано и работает медленнее. В моем конкретном случае это не так.

И получил вот такой вывод (релизный билд с оптимизацией кода):

GetDirectoryFiles
Found 2612 files
287 exceptions thrown
Elapsed 89,225523s
GetDirectoryFilesOriginal
Found 2612 files
574 exceptions thrown
Elapsed 440,9526969s
GetDirectoryFilesFast
Found 2612 files
287 exceptions thrown
Elapsed 69,9758348s

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

Так что решение вашей проблемы - не распараллеливание, а оптимизация.

4
  • 1
    ssd m2 или sata? (плюсик за проделанную работу, было интересно) 23 янв 2021 в 20:50
  • @Andrew SATAII, спасибо, я еще пару багов подправил
    – aepot
    23 янв 2021 в 21:00
  • Жаль, лучше такой тест проводить на м2 где меньше ограничение по шине. 23 янв 2021 в 21:16
  • @Andrew оно в любом случае не нагружает у меня SSD, а упирается в процессор. Так что при прочих равных на моей машине будет примерно фиолетово, M2 там у меня или SATAII.
    – aepot
    23 янв 2021 в 21:18
5

(Не совсем ответ / Или совсем не ответ)

Распаралеливание работы с HDD бесполезное занятие. В любом случае ты упираешся в скорость винчестера. А при множестве потоков общая скорость задач даже упадет. Это связано с тем что несколько операций чтения и записи имеют одинаковый приоритет и постоянно нужно перемещать головку для каждого потока на другое место. А перемещение головки = утраты времени на лишнюю работу.

В случае с SSD все не так однозначно. Теоретический прирост может быть, а может быть краткострочный прирост скорости, а может и вовсе не будет прироста. Нельзя сказать просто "на ССД это будет работать быстрее" ибо ссд ссд рознь. Взять китайский низкоклассовый ссд - там операция записи будет 70-80 мегабайт (честная, а не по CrystalDiskMark, который лжет как дышит). Операция чтения - как повезет. Но около 300-350 (надеюсь).

Если брать SSD средней ценовой категории - там залепливают дыры отвратного железа добавлением кеша. Поэтому скорость записи будет хорошая пока не забьется кеш. А дальше будет печаль.

Если брать топовый ссд вроде самсунг Эво - там будет +- честная скорость на всем ссд.

Уверен, там есть еще какие-то особенности про которые я не знаю.

Еще могут быть разные виды RAID-ов. Там изменения скорости паралельной записи будет зависеть еще и от вида рейда.


Оффтоп:

Не пользуйтесь CrystalDiskMark вообще. Это отвратный бенчмарк который не показывает обьективную оценку работы SSD от слова "вообще".


Резюме:

Вобщем, даже если написать алгоритм распаралеливания мы можем получить в части случаев замедление вместо желаемого убыстрения.

А что бы наверняка понять стоит ли это делать - нужно провести множество тестов с РАЗНЫМИ SSD разных ценовых категорий на разных задачах. И только потом уже будет понятно есть ли смысл в это ввязыватся при конкретной задаче и какие костыли писать что бы это не приводило к замедлениям у конечного пользователя.


Лично я бы вообще не паралелил бы I/O задачи в принципе.

20
  • 1
    поиск файлов в папках != работа с SSD / HDD. Там вполне может быть какая-то часть CPU нагрузки. И к тому же, это ведь поиск по MFT, а не по содержимому файлов. В случае NTFS - это поиск по B-Tree, которое скорее всего будет в кэше лежать. Поиск по нему - это CPU-задача, и ее можно параллелить. Тот же SQL Server, в котором индексы - это лежащие на диске / в кэше B-Tree, и в нем параллелизм запросов внезапно работает. Так что не все так однозначно. Нужно взять и померять.
    – user177221
    23 янв 2021 в 9:19
  • В MFT данные тоже лежать не последовательно, на сколько я понимаю. То есть если в паралели это делать, то вероятно, тоже приведет к замедлению потому что нужно будет заново проверять по списку какие именно файлы относятся к проверяемому пути или нет... А если это несколько потоков - то нужно проверять те же подпути по N раз.... Не уверен как именно это там работает, это теоретически. Что до кеширования - тоже тот еще вопрос. Думаю тут мы можем еще упереться в какие-то настройки винды дополнительно.... 23 янв 2021 в 9:33
  • Короче) Суть моего ответа все равно сводилась к тому что нужны тесты. Еще и с разным железом. А теперь еще и с разными настройками винды ахахах. (Хотя на самом деле я не уверен что MFT кешируется... Это должно быть и так максимально оптимально реализовано из коробки... В теории.). А еще это может быть не только NTFS. Это тоже нужно учитывать - может быть под виндой и FAT и REFS, например. И хрен его знает как это работает там. Особенно учитывая что в REFS еще и поддержка дедупликации файлов есть...Что практически наверняка как-то сказалось на особенностях MFT и поиска.... 23 янв 2021 в 9:38
  • Имхо, это совсем не ответ. Автор спрашивает как распараллелить. 23 янв 2021 в 10:21
  • Гм, а какая разница, дешманский или элитный SSD: в любом случае он будет показывать свою максимальную скорость при доступе в один поток. И добавление новых потоков ничего не изменит. 23 янв 2021 в 10:25
4

Просто скину как один из вариантов

if (searchOption == SearchOption.AllDirectories)
{
    IEnumerable<string> subDirs = Directory.EnumerateDirectories(rootPath);
    return subDirs.Concat(subDirs.AsParallel().SelectMany(dir => GetDirectoryFiles(dir, patternMatch, searchOption)));
}   

Код не запускал, так что пробуйте сами.

2
  • В этом коде проблема в том, что в случае ошибки (неавторизованный доступ к одной из папок/файлов) не будет получен ни один файл. 23 янв 2021 в 10:23
  • Я показал принцип, конструкции try-catch уже есть в самом вопросе.
    – tym32167
    23 янв 2021 в 13:06

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.