На днях мной была написана простенькая консольная утилита fdf (сборка под Windows x86-64, для запуска требуется Microsoft Visual C++ 2013 runtime).

Цели разработки

• Получить минималистичную утилиту для поиска файлов-дубликатов или уникальных файлов в заданных директориях;
• потренироваться в решении подобных задач;
• опробовать SHA3 (Keccak).

Цель получить код, отвечающий каким-то специальным критериям (краткость, дидактическая ценность, высокая эффективность), не ставилась. Тем не менее, предполагается, что он может служить вспомогательным примером при изучении, например, многопоточного программирования на C++: вспомогательные компоненты LockedQueue, LockedLog и ThreadGroup вынесены в отдельные заголовочные файлы и являются довольно примитивными.

Исходники выложены на bitbucket. Для самостоятельной сборки требуется скачать референсную реализацию Keccak и (удобно при использовании Visual C++) распаковать её в папку проекта, так, чтобы папка KeccakReferenceAndOptimized была рядом с файлами исходного кода. За подключение нужных .c файлов отвечает файл FileHasher.cpp, связь кода fdf с Keccak обеспечивается файлом FileHasher.hpp. Оказалось, что использовать референсную оптимизированную (жаль только, что SIMD под Windows/x64 не используется) реализацию весьма просто, спасибо авторам!

Параметры командной строки

• /? ? -help —help выводит краткую справку;
• -tN задаёт количество рабочих потоков (всего параллельных потоков будет N+1), по умолчанию выбирается N = max(1, количество логических ядер / 2);
• -u меняет поведение программы на противоположное: вместо дубликатов будут перечислены найденные уникальные (в заданной области поиска) файлы;
• -size включает вывод размеров файлов (один размер на группу дубликатов);
• -loN включает фильтр по размеру файла: рассматриваются только файлы размера не менее N мегабайт, при этом если N=0, fdf будет игнорировать пустые файлы;
• -timing включает вывод в конце затраченного времени (в секундах);
• другие параметры расцениваются как указания мест поиска файлов (пути директорий), они формируют общую область поиска (объединение), если ни один путь не указан, то поиск производится в текущей директории.

Результаты работы

• в stderr: сообщения об ошибках (специально не форматируются, поэтому могут иметь заковыристый вид с лишними словами);
• в stdout: результат работы, который оформляется как последовательность строк, завершающихся переводом строки, содержащих или полные пути найденных файлов или размеры в байтах или (последняя строчка при наличии параметра -timing) затраченное время; группы дубликатов отделяются друг от друга пустой строкой.

Принцип работы

Для обхода директорий используется библиотека boost::filesystem. Процесс работы разбит на три стадии:

1. составление первичного списка файлов;
2. объединение результатов первой стадии;
3. проверка на дубликаты побайтовым сравнением найденных кандидатов в дубликаты.

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

На первой стадии основной поток раздаёт пути файлов, выполняя обход переданных директорий поиском в ширину (это приводит к большему расходу памяти, чем традиционный обход поиском в глубину, но позволяет паралелльно нагрузить произвольное число носителей данных), в то время как рабочие потоки вычисляют хэши файлов (целиком для файлов меньше 16 Мб и для выборки в 16 Мб для остальных, размер в 16 Мб взят «с потолка»), и в конце сортируют свои наборы файлов (лексикографически: размер, хэш, имя).

На второй стадии основной поток выполняет восходящее слияние результатов работы рабочих потоков.

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

Замечание. Вместо трёх стадий и формирования отсортированного списка файлов можно было использовать какую-либо параллельную реализацию хэш-таблицы (аналог std::unordered_multiset). Впрочем, в моей практике с использованием HDD именно первая стадия занимает этак 98% времени работы, поэтому сложно надеяться на заметное ускорение при работе на HDD.