Category Archives: concurrency

Поиск дублирующихся файлов

На днях мной была написана простенькая консольная утилита 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.

Реклама

Parallel String Histogram

Not long ago I’ve read the following article: Solving the Multicore Dilemma.

The article proposes an interesting approach to enabling automaic parallelization of high-level code. This approach is presented as an alternative to enforcing immutability of values (pure functional programming). We can think of it as (full) scatter-gather paradigm (while pure FP corresponds to the «gather» part).

As for me, I don’t think that this approach is really universally applicable, but it may be fruitful anyway even as a mindset for parallelization by hand.

The post you’re reading is devoted to a small special case, which was used as a simple example in the aforementioned article. It’s about getting the histogram of a string (I call it «counting codes» below). Imagine that the simple sequential algorithm is transformed into a scatter-gather counterpart. There each character codepoint has its own container where 1s are accumulated. I think that a sophisticated parallelizing compiler should find out that we don’t need real containers but just a bunch of simple counters.

Well, this way of reasoning may lead to a structure consisting of atomic counters and replacing pushing and summing with atomic increment (so no scatter-gather anymore). People doing parallel algorithms may guess that atomic counters being used so intensively will prevent us from gaining any performance increase (even with state-of-the-art hardware support for atomic operations) for this «parallel» code. More likely, it will be working slower than that simple sequential algorithm. I don’t claim that our would-be sophisticated compiler couldn’t find out the problem with atomic increment. But too clever compilers may produce quite unpredictable code…

Meanwhile, it seems logical to parallelize this algorithm just by providing each thread with it’s own array of counters and then summing the results. I found it to be interesting to measure real-life speed of these algorithms.

For simplicity I used 8-bit char, so I can use a plain C array of 256 integers fitting exactly in 1kb of RAM to store counters for all possible codepoints. Strings are generated using Mersenne twister mt19937 and uniform_int_distribution. The source code containing all the details is available via URLs given below.

Tested algorithms:

  • reference sequential: reference.h
  • atomic via OpenMP means: atomic.h
  • using std::atomic (a dirty hack, just for testing!) with OpenMP thread-group: std_atomic.h
  • parallel with per-thread counters arrays and no atomic operations: parallel.h

Other code: random_string.h, test.cpp. Archived MSVC project with compiled exe (x64) and the testing results: here.

Compiler/OS used: Microsoft Visual C++ 2012 (x64, default release settings + /GS- /Qpar) / Windows 7SP1 Pro x64.

Testing machines: AMD Phenom 2 x4 @ 2.1GHz and 3.2GHz with 2x2Gb DDR3-1333 RAM, Intel Celeron U3400 1.07GHz with 4Gb DDR3-800.

I tried std::atomic just to see «lock xadd» in assembly (MSVC transforms OpenMP atomic directive into «call _vcomp_atomic_add_i4» here, the procedure is hidden somewhere in the runtime). What’s interesting and counter-intuitive (at least for me), OpenMP variant stably works faster than std::atomic on Phenom and vice versa: std::atomic is quite faster on Celeron.

Both atomic variants work an order of magnitude SLOWER than simple sequential algorithm – a serious warning to everyone using atomics indiscriminately. Atomic operations prevent caching of counters and lock memory bus (therefore each iteration loads from and stores to DRAM an integer, and no matter how many threads try to do it, they do it serially).

«Normal» parallel variant works only twice faster on my quad-core machine (and almost no faster on the dualcore machine) than a sequential one not reaching even 1Gbps string reading speed @ 2.1GHz and hardly reaching 1.33Gbps @ 3.2GHz (in a perfect situation the counters array should reside in L1D, string parts should be prefetched to cores’ caches line by line effectively reaching RAM subsystem throughput limit). So, a field for some improvement obviously exists.

Performance scaling with string length and CPU frequency is almost linear. However doing small strings in parallel may lead to high overhead (threads starting and joining, possible context switches).

Intel Celeron U3400

AMD Phenom @ 3.2GHz

AMD Phenom @ 2.1GHz

UPDATE 2013.03.25.

The code was revised and published on Bitbucket.

ParallelSort: Tier-1b Bucket

Общий принцип блочной сортировки можно описать двумя словами «scatter-gather». В нашем случае сортировки чисел производятся следующие операции.

  1. Найти min и max сортируемой последовательности N чисел, размах r = max — min.
  2. Положим, что зафиксирован «целевой» размер блока b, создадим 1 + [N/b] блоков размера cb, где c ≥ 1 (избыточное резервирование).
  3. Пройдёмся по сортируемой последовательности, пусть x – число, положим его в блок с индексом [[N/b] (x — min) / r].
  4. Отсортируем каждый блок независимо.
  5. Конкатенируем блоки по порядку в результирующую последовательность.

Код базового варианта (bucket sort 1) вычисляет размер блока, используя шаблон BucketSize<тип элемента>::value. Текущий размер взят с прицелом на то, чтобы блок помещался (в случае равномерного распределения входной последовательности) в L2-кэш машины Deneb (512kb), что должно положительно сказаться на скорости сортировки блока. Собственно сортировка блока может выполняться как рекурсивно (к блоку снова применяется блочная сортировка, пока блоки не станут совсем маленькими), либо может использоваться любая другая сортировка, здесь используется std::sort. Пожалуй, наиболее логичным вариантом было бы применять блочную сортировку до достижения размера блока < L2-кэша (256кб – 2Мб в распространённых ЦП, можно остановиться на 256кб), после чего переключаться на std::sort.

В качестве блоков в базовом варианте используются объекты std::vector, автоматически увеличивающие свой размер при необходимости. Впрочем, как показал опыт, полезнее заранее посчитать размеры блоков, так как операции с памятью (особенно выделение в несколько потоков) обходятся дорого. Поэтому был написан вариант 2 (bucket sort 2), который заранее определяет размеры блоков и потом размечает под них массив размера N. Кроме увеличения скорости, это гарантирует использование количества вспомогательной памяти, равного размеру входной последовательности, в то время как вариант 1 может «съесть» гораздо больше памяти в случае «неудачного» распределения исходной последовательности.

Далее, было рассмотрено два способа распараллеливания алгоритма блочной сортировки.

Вариант распараллеливания 1 (bucket sort 1/p на основе bucket sort 1 и bucket sort 2/p на основе bucket sort 2). Каждый этап распараллеливается отдельно, входная последовательность разбивается на примерно равные куски, обрабатываемые каждый своим потоком. Каждый поток «разбрасывает» элементы по своей группе блоков (но блоки покрывают одинаковые поддиапазоны, не зависящие от потока). Блоки сортируются параллельно. В конце производится (последовательное) слияние групп блоков (обобщение слияния двух упорядоченных последовательностей).

Вариант распараллеливания 2 (bucket sort 3/p и bucket sort 4/p). Каждому потоку отводится своя часть диапазона значений входной последовательности. Все потоки пробегают входную последовательность целиком, но берут только те значения, которые попадают в поддиапазон потока. Опять же, сортировка блоков производится параллельно. Слияние групп блоков в конце уже не требуется. Вариант 4 отличается от варианта 3 так же, как вариант 2 отличается от варианта 1 (т.е. блоки размещаются не в отдельных векторах, а в общем буфере, и их размер вычисляется заранее).

Результаты тестирования показывают, что bucket sort 2 и bucket sort 4 способны обеспечить большую эффективность задействования дополнительных ядер, и лишний проход по входной последовательности для вычисления размеров блоков оправдывается. С другой стороны, вариант распараллеливания 1 выглядит более эффективным (практически всегда – сравните результаты bucket sort 4/p vs bucket sort 2/p) нежели вариант распараллеливания 2.

Далее: tier-1c radix, tier-1b.1 SSE2, tier-1b.2 bucket size varying (планируется продолжение изучения блочной сортировки, как одного из наиболее эффективных алгоритмов сортировки чисел)

ParallelSort: Tier-0 VirtualBox

Довольно интересно посмотреть на эффективность виртуальной машины в самом, пожалуй, неудачном для неё случае: когда «бутылочным горлышком» оказывается производительность подсистемы памяти (что как раз характерно для сортировок). Я провёл тестирование tier-0 на Oracle VM VirtualBox 4.1.6 r74713 с установленной на ней Windows XP SP3 (32-битная), использующей 2Гб RAM и 2 ядра ЦП хост-машины «Deneb». Результаты тестирования показывают относительно неплохую производительность порядка 60% — 95% от скорости на хост-машине. Тем не менее, не следует проявлять излишний оптимизм касательно производительности виртуальных машин и доверять заверениям вроде «почти без потерь» или «95% от ОС хоста».

Далее: tier-1 VirtualBox.

ParallelSort: Tier-1a Bitonic

Битоническая сортировка является самой популярной сортировкой на основе сортирующих сетей. Исходный код однопоточного нерекурсивного варианта. Тип Index является синонимом библиотечного типа std::ptrdiff_t и используется для представления индексов и размеров массивов. Если присмотреться к коду, то можно заметить, что а) всего производится O(N (log N)2) сравнений и их количество зависит только от N, а не от содержимого (от него уже зависит количество обменов); б) итерации внутренних циклов (по k и p) независимы друг от друга и могут выполняться параллельно. Благодаря указанным свойствам битоническая сортировка может быть реализована аппаратно (для фиксированного N) в виде сети компараторов, может эффективно выполняться параллельно на устройствах с высокой степенью параллелизма, например, графических процессорах.

Для распараллеливания битонической сортировки на ЦП было применено расширение языка C OpenMP. MSVC поддерживает OpenMP 2.0. При использовании OpenMP низкоуровневым управлением потоками исполнения занимается компилятор, программист же размечает исходный код директивами OpenMP, основанными на директиве препроцессора pragma. Это весьма удобно, пока код укладывается в ограничения OpenMP, например, если достаточно параллельного исполнения итераций цикла for. Последнее делается следующим образом:

#pragma omp parallel for
for (SignedIntegerType i = i0; i < i1; i += di)
  // code

Ограничения, накладываемые директивой parallel for:

  • тип переменной-счётчика должен быть целым со знаком;
  • количество итераций должно быть известно и фиксировано на момент входа в цикл;
  • инкремент счётчика должен выполняться простой формулой (удалить или добавить константу);
  • тело цикла не должно содержать break или выход из цикла по goto.

Так как ядер в современных массовых ЦП относительно немного, то решено сделать ветвление, которое распараллеливает либо цикл по k, либо цикл по p: исходный код и результаты тестирования. К сожалению, реальная эффективность распараллеливания оказалась довольно низкой, видимо, из-за большого количества промахов кэшей (в пользу этого говорит и то, что оценка parallelism на основе congestion довольно хорошо описывает реальную эффективность параллельной версии). В случае использования битонической сортировки на ГП указанный фактор уже не должен оказывать заметного влияния.

Далее: tier-1b bucket.

ParallelSort: Tier-0

Итак, результаты стандартных алгоритмов. Heap sort реализован как

template <class RanIt>  // RanIt == Random Iterator
void heapSort (RanIt begin, RanIt end)
{
  std::make_heap (begin, end);
  std::sort_heap (begin, end);
}

В среднем/худшем случае std::stable_sort оказалась лишь немного хуже std::sort. Последняя обычно является «прокаченным» вариантом introsort с выборкой (вероятной) медианы в качестве опорного элемента и переключением на сортировку вставками при обработке небольших диапазонов, и с ней действительно сложно соревноваться. Высокое качество работы std::sort демонстрируют низкие показатели congestion (соответственно, высокий parallelism). У std::stable_sort они существенно хуже и ещё хуже у пирамидальной сортировки, которая из-за частых промахов кэшей упирается в латентность случайного доступа контроллера DRAM.

Далее: tier-1a bitonic, tier-0 VirtualBox.

ParallelSort: Testing method

Тестируемые сортировки выполняются по возрастанию над массивами чисел с плавающей запятой двойной точности (double, 64-bit). Размер массива составляет 225 элементов или 256Мб. Размер, равный степени двойки, выбран для того, чтобы не усложнять реализацию битонической сортировки, простой вариант которой требует равный степени двойки размер сортируемой коллекции. Остальные алгоритмы этого не требуют. Размер массива в 256Мб достаточно велик, чтобы даже одна восьмая его не помещалась в L3 кэш распространённых x86 процессоров, при этом он достаточно мал, чтобы позволить себе хранить несколько таких массивов в RAM, и при этом система с 2+ Гб RAM «не уходила в своп«, а под 32-битной ОС процессу хватало адресного пространства (Windows address space limits).

Входные последовательности

Сортируемый массив заполняется 12-ю способами. Псевдослучайные величины генерируются с помощью вихря Мерсенна и инициализируются текущим системным временем.

  1. «uniform 1» равномерное на [-1, 1] распределение.
  2. «uniform 2» равномерное на [0, 1e150] распределение.
  3. «normal 1» нормальное распределение с μ = 0, σ = 1.
  4. «normal 2» нормальное распределение с μ = 1e150, σ = 1e150.
  5. «lognormal» логнормальное распределение с μ = 0, σ = 0,5.
  6. «Cauchy» распределение Коши.
  7. «Weibull» распределение Вейбулла с k = 0,5, λ = 1.
  8. «sorted» заранее отсортированная последовательность (изначально uniform 1).
  9. «sorted/desc» заранее отсортированная по убыванию последовательность (изначально uniform 1).
  10. «sorted/blocks» последовательность из отсортированных последовательностей-«блоков» (размера порядка sqrt (N), где N – размер исходной последовательности, сгенерированной как uniform 1).
  11. «sine» синусоида (полученная копированием sqrt (N) выборок).
  12. «chaotic» «хаотическая» постепенно возрастающая последовательность, полученная по формуле a[n] = sqrt (sqrt (n)) * modf (13 * sqrt (modf (51 * sqrt (modf (107 * sqrt (n)))))).

Каждый замер (комбинация алгоритма и вида входной последовательности) производится 10 раз, в качестве результата приводится арифметическое среднее. Замер производится таймером микросекундной точности. Для упрощения сравнения приводятся минимальный, максимальный результат и геометрическое среднее («gmean») результатов по всем входным последовательностям.

Перед собственно замерами производится «прогрев»: один прогон std::sort для каждого варианта входной последовательности. После каждой сортировки производится автоматическая проверка корректности.

Congestion

Кроме собственно сортировки заданного набора выполняется оценка того, насколько сам принцип работы алгоритма (в первую очередь, характер обращений к RAM) может помешать эффективному распараллеливанию. Для этого исходный массив разбивается на равные части по числу логических ядер ЦП, замеряется максимальное время сортировки одной части в однопоточном режиме Tmax, затем замеряется время одновременной сортировки всех частей (каждому логическому ядру назначается своя часть) Tpar. Конечный результат получается по формуле congestion = (TparTmax) / Tmax.

Таким образом, если congestion равно 0, распараллеливание идеальное, если равно 1 на 4-ядернике, то получается эффективность до 50% (ускорение вдвое при загрузке всех четырёх ядер против одного). Естественно, эта метрика вычисляется только для однопоточных алгоритмов. Её результаты несравнимы между ЦП с разным числом ядер.

Компиляция и тестовые системы

Компилятор Microsoft Visual C++ 2010 SP1 x64 (в 64-битный код), опции: /O2 /Oi /GL /Gm- /EHsc /GS- /Gy /fp:fast /openmp /Gd /MD. Тесты прогонялись на двух системах с ОС Windows 7 x64:

  1. «Deneb» AMD Phenom II x4 955 3.2GHz / 2GHz uncore, 2x 2Gb DDR3-1333 (4 ядра).
  2. «Arrandale» Intel Celeron U3400 1.07GHz, 4Gb DDR3-800 (2 ядра).

Далее: tier-0.

ParallelSort: Intro

Этим постом я открываю серию постов, посвящённых исследованию возможностей распараллеливания ряда алгоритмов сортировки. Одновременно планируется исследовать применимость некоторых средств SMT распараллеливания, доступных для языка C++, в связи с чем (механизм задействования параллелизма) алгоритмы сортировки разделены на три группы («tiers») плюс эталонная однопоточная группа «стандартных сортировок»:

  1. Алгоритмы стандартной библиотеки C++: std::sort, std::stable_sort, пирамидальная heap sort (std::make_heap + std::sort_heap).
  2. Алгоритмы, распараллеливание которых может быть эффективно осуществлено путём параллельного исполнения независимых итераций циклов for: битоническая bitonic sort (нерекурсивный вариант), блочная bucket sort (базовый размер блока, соизмеримый с L2 кэшем ядра), поразрядная radix sort (базовый вариант использует 4-битные разряды).
  3. Рекурсивные алгоритмы с параллельным исполнением ветвей рекурсии: слияниями merge sort, быстрая quick sort, рекурсивный вариант битонической сортировки rbitonic sort.
  4. Алгоритмы, разные стадии которых могут исполняться параллельно, т.е. удобно выполнить конвейеризацию: расчёской comb sort.

Далее: методика тестирования.