Category Archives: Tests

О реализации целочисленного аналога функции sqrt

Год назад я написал пост по обращению матриц определённого вида. Он возник не на пустом месте. Исходной посылкой послужило желание сконструировать способ качественного определения быстродействия маленьких быстро выполняющихся функций в условиях, «приближенных к реальности». На тот момент я пытался сравнивать быстродействие различных вариантов реализации функции вычисления целочисленного квадратного корня.

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

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

Неожиданным открытием при первом простом тестировании стала зависимость скорости выполнения функции от её положения в asm-файле (для ассемблерных вариантов). Директива align перед циклами, напротив, не продемонстрировала устойчивого эффекта. Наиболее вероятным «виновником» в данном случае является предсказатель ветвлений и особенности его работы для конкретного CPU. Также может сказываться работа L1I и TLB (здесь, в частности, может удачно или неудачно подействовать директива align).

В случае «простого» тестирования вроде многократного вызова одной функции в цикле есть немалый шанс натолкнуться на проявление таких особенностей во всей их красе. Поэтому я решил поступить несколько хитрее: выполнить псевдослучайное перемешивание разных вызовов. В каждом прогоне — разное количество вызовов разных функций. Выполнив столько же прогонов, сколько у нас есть функций, получим вектор суммарных времён и матрицу количеств вызовов. Решив линейное уравнение, получим оценки времени вызова каждой функции. Можно сделать и больше прогонов и получить решение с помощью МНК (здесь не реализовано). В итоге я всё же не стал использовать аналитически обращаемую матрицу, а задействовал библиотеку uBLAS из состава Boost. См. также о влиянии фрагментации кучи на результаты тестирования.

Использовалась среда Microsoft Visual C++ 2015, компиляция под x86-64 с O2. Причёсывать код однолетней давности я уже поленился — там есть, что выкинуть, но если бы я этим занялся, то… В общем, год уже и так прошёл.

Замечание. В MSVC все исходники .c, .cpp, .asm должны иметь разные имена, так как при компиляции каждого из них порождается одноимённый .obj файл, которые сваливаются в одну общую папку и могут затирать друг друга с печальным результатом во время компоновки.

Итак, исследуемые варианты:

  1. cpp1, asm1 — цикл + ветвление;
  2. cpp2, asm2 — цикл + cmov;
  3. cpp3, asm3 — цикл + ветвление + ilog2 (целочисленный логарифм позволяет выбрать хорошее начальное приближение, для его реализации на x86 используется команда bsr или lzcnt);
  4. cpp4, asm4 — цикл + cmov + ilog2;
  5. asm5 — развёрнутый вариант asm3;
  6. asm6 — развёрнутый вариант asm4 (computed goto);
  7. fpu — использует команды SSE для вычисления isqrt (стандартный метод);
  8. null — ничего не делает, используется для оценки времени вызова.

Итак, результаты тестирования представлены на графике ниже. Числа получены следующим образом: в каждом прогоне использовалось 100’000 псевдослучайных чисел-аргументов, равномерно распределённых от нуля до числа, указанного по оси 0x (1k — 1024, 32k — 32’768, 1M — 220, 1G — 230), выполнялось 1100 повторений, из которых верхние и нижние 5% полученных оценок времён отбрасывались, а от оставшихся 1000 бралось арифметическое среднее. Всего выполнялось по 10 таких прогонов, из результатов которых для каждой функции выбиралось минимальное значение и затем вычиталось соответствующее минимальное значение функции null. В конце все результаты нормировались по функции fpu, так что по оси 0y графиков мы видим, во сколько раз все варианты медленнее вычисления isqrt на fpu.

Процессор, на котором производился тест — AMD K10. Итак, мы видим, что «бодаться» с FPU на «больших» процессорах (пусть даже старых) бессмысленно. Пиррова победа в режиме 1k у asm4/cpp4. Применение ilog2 в комбинации с cmov даёт весьма неплохой эффект, который может оказаться ещё выше на простых процессорах без хорошего предсказателя переходов. А вот разворачивание цикла здесь не помогает (впрочем, опять же на «простом» процессоре ситуация может быть другой).

Сравнение скорости некоторых способов организации простейших циклов по std::vector

На написание данного поста меня сподвигла статья Есть ли практический смысл использовать для итераторов префиксный оператор инкремента ++it, вместо постфиксного it++. У меня появилось желание посмотреть поведение большего числа вариантов и на современном компиляторе — в моём случае это Microsoft Visual C++ 2015 (платформа: Windows 7 x64, компиляция под x64).

Методика тестирования: заполнение массива (vector) псевдослучайными числами на основе случайного зерна размером в 10 миллионов элементов типа double, замер времени выполнения каждого варианта с помощью стандартного high_resolution_clock (имеет микросекундную точность в MSVC2015). Повторы выполнялись вручную для оценки погрешности теста «на глаз», так как высокая точность здесь не требуется, а аномалии не ожидаются (и не были обнаружены). Полученная таким образом погрешность оказалась меньше 4%.

Результаты приведены в таблице ниже. Числа соответствуют debug-сборке, запущенной из Visual Studio под отладчиком. Запуск непосредственно exe-файла без отладчика демонстрирует увеличение скорости примерно на 5% — на грани погрешности. Числа получены делением времени работы debug-сборки на время работы release-сборки. Release-сборка демонстрирует одинаковое время работы для всех вариантов (в том числе, при запуске из-под Visual Studio и запуске непосредственно exe-файла).

Вариант Замедление к release
v1, it++ 1210
v2, ++it 610
v3, it != e; ++it 230
v4, for(:) 230
v5, accumulate 18
v6, items[i] 184
v7, p[i] 3

Ниже приведён исходный код всех вариантов.

Вариант 1. Постфиксный инкремент итератора.

  for (auto it = begin(items); it != end(items); it++)
    s += *it;

Вариант 2. Префиксный инкремент итератора (быстрее варианта 1 вдвое).

  for (auto it = begin(items); it != end(items); ++it)
    s += *it;

Вариант 3. Сохранение конца диапазона в переменную (быстрее варианта 2 втрое).

  for (auto it = begin(items), e = end(items); it != e; ++it)
    s += *it;

Вариант 4. Цикл for по диапазону (эквивалентен по скорости варианту 3).

  for (auto &&item : items)
    s += item;

Вариант 5. Стандартный алгоритм accumulate (быстрее вариантов 3 и 4 более, чем в 12 раз).

  return accumulate(begin(items), end(items), Item{ 0 });

Вариант 6. Целочисленный индекс вместо итератора (незначительно быстрее вариантов 3 и 4).

  for (size_t i = 0, sz = items.size(); i < sz; ++i)
    s += items[i];

Вариант 7. Целочисленный индекс, обращение по указателю (убирает проверки диапазона при отладке, в шесть раз быстрее варианта 5).

  const auto p = items.data();
  const auto sz = items.size();
  for (size_t i = 0; i < sz; ++i)
    s += p[i];

Код теста целиком.

Итак, влияние на скорость отладки может быть очень значительным.

На мой взгляд, разумно использовать вариант 4 во всех случаях, когда нет дополнительных обстоятельств. Сделать ошибку при использовании for(:) цикла сложнее всего. Варианты 1 и 2 использовать не следует никогда. Если вариант 5 подходит к конкретной ситуации (вроде рассмотренной здесь суммы), то, наверное, следует предпочесть его, хотя и не совсем ясно, почему он оказался быстрее варианта 4. Вариант 7 я использую при написании узких циклов на векторах: опыт показывает, что на таком коде оптимизирующий компилятор обычно способен достичь большего, чем на других вариантах (правда, на такой простой задаче как сумма, это не сказалось). Данный вариант является условно-опасным: в нём даже в отладочной сборке в цикле не выполняются проверки на выход за пределы диапазона (в отличие от варианта 6).

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.

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

ReBits 32 x64

В ReBits 32 и ReBits 32 x4 использовался компилятор под IA-32 (часто обозначаемую как «x86»). Однако, почти все x86-совместимые ЦП, выпускаемые в настоящее время, поддерживают 64-битные расширения (часто называемые «x86-64» или, сокращённо, «x64»), предложенные AMD в 2000 (первый процессор вышел в 2003). ОС, работающие в 64-битном режиме всё шире распространяются на домашних ПК. Поэтому, на мой взгляд, именно x64, а не IA-32 следует рассматривать как основную целевую платформу для новых приложений, особенно, если они должны будут обрабатывать большие объёмы данных.

Система команд x64 включает в себя обязательную поддержку SSE2, причём количество регистров xmm удвоено (до 16). Количество РОНов также удвоено, что, в частности, позволяет ускорить вызов функций (использовать больше регистров для передачи параметров). Посмотрим, как будут работать полученные ранее решения в 64-битном режиме.

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

Для условной компиляции кода, имеющего разные версии под IA-32 и x64, MSVC предлагает макрос _M_X64 (определён для целевой платформы x64).

Рассматривались следующие варианты: N0, H0, H1 и цикл H5, как написанные на C и не требующие изменений перед перекомпиляцией под x64. Были переписаны H5 (как лучший доступный вариант для обработки одного 32-битного блока), циклы с использованием SSE2 и SSSE3. MSVC предлагает следующие заголовочные файлы:

  • intrin.h — набор всех интринсиков (включает все ниже перечисленные), новый вариант H5 использует _rotl/_rotr (вместо rol/ror: циклический сдвиг влево/вправо) и _byteswap_ulong (вместо bswap: обращение порядка байт);
  • mmintrin.h — команды MMX;
  • xmmintrin.h — команды SSE, включает mmintrin.h;
  • emmintrin.h — команды SSE2, включает xmmintrin.h;
  • pmmintrin.h (Prescott) — команды SSE3, включает emmintrin.h;
  • tmmintrin.h (Tejas) — команды SSSE3, включает pmmintrin.h;
  • smmintrin.h (?) — команды SSE4.1, включает tmmintrin.h;
  • nmmintrin.h (Nehalem) — команды SSE4.2, включает smmintrin.h;
  • wmmintrin.h (Westmere) — команды AES NI и CLMUL, включает nmmintrin.h;
  • immintrin.h (?) — команды AVX, включает wmmintrin.h;
  • ammintrin.h — команды, предложенные AMD (бывший SSE5).

Удвоенное количество регистров позволяет хранить инвертированные маски (и сократить таким образом количество инструкций), а также обрабатывать не одну четвёрку, а, например, две четвёрки за итерацию цикла. При этом вторая загрузка происходит после первого блока вычислений. Теоретически такое «смешивание» команд должно минимизировать простой XMM блоков ЦП. Итак, переписанные на интринсиках варианты: для SSE2, для SSSE3. Сравним их результаты (за 100% приняты соответственно H1 и цикл на H5, обозначенный H5x4).

Можно заметить, что SSE2 улучшил свои относительные показатели. N0 не показан из-за его низкой скорости (чтобы не портить масштаб), кроме того, для N0 переход на x64 ничего не дал (на Deneb даже стало медленнее на 11%). Ниже представлена диаграмма, показывающая отношение времени, затраченного x64 версией, ко времени IA-32 версии. Для большинства рассмотренных вариантов переход на x64 оказался полезен.