Как использовать инструкции процессора в C ++ для реализации быстрых арифметических операций

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

Распознавание идиомы

Запишите операцию, не предлагаемую непосредственно в C ++, в «длинной форме» и надейтесь, что ваш компилятор распознает ее как идиому для базовой инструкции, которую вы хотите. Например, вы можете написать переменную с поворотом влево от x на amount как (x << amount) | (x >> (32 - amount)), и все gcc, clang и icc распознают это как поворот и выполнить базовую инструкцию rol, поддерживаемую x86.

Иногда этот метод ставит вас в неудобное положение: приведенная выше реализация поворота C ++ демонстрирует неопределенное поведение для amount == 0 (а также amount >= 32), поскольку результат сдвига 32 на uint32_t не определен, но код, на самом деле, созданный этими компиляторами, в этом случае вполне подойдет. Тем не менее, наличие этого скрытого неопределенного поведения в вашей программе опасно, и, вероятно, оно не будет работать против ubsan и его друзей. Альтернативная безопасная версия amount ? (x << amount) | (x >> (32 - amount)) : x; распознается только icc, но не gcc или clang.

Этот подход, как правило, работает для распространенных идиом, которые отображаются непосредственно на инструкции уровня сборки, которые существовали некоторое время: повороты, битовые тесты и наборы, умножения с более широким результатом, чем входные (например, умножение двух 32-битных значений на 64 -битный результат), условные ходы и т. д., но с меньшей вероятностью уловят новейшие инструкции, которые также могут быть интересны для криптографии. Например, я совершенно уверен, что ни один компилятор в настоящее время не распознает приложение расширений набора инструкций AES. Он также лучше всего работает на платформах, на которые разработчики компилятора приложили много усилий, поскольку каждую распознанную идиому приходится добавлять вручную.

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

Внутренние функции

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

GCC вызывает эти встроенные функции, и вы можете найти список здесь. Например, вы можете использовать вызов __builtin_popcnt для выдачи инструкции popcnt, если текущая цель поддерживает ее. Встроенные команды man из gcc также поддерживаются icc и clang, и в этом случае все gcc, clang и icc поддержите этот вызов и испустите popcnt, пока для архитектуры (-march=Haswell) установлено значение Haswell. В противном случае clang и icc встраивают заменяющую версию, используя некоторые хитрые уловки SWAR, в то время как gcc вызывает __popcountdi2, который предоставляется средой выполнения ¹.

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

В частности, для инструкций SIMD x86 Intel предоставляет набор встроенных функций объявил заголовки, покрывающие их расширения ISA, например, включив #include <x86intrin.h>. Они имеют более широкую поддержку, чем инстринсики gcc, например, они поддерживаются пакетом компиляторов Microsoft Visual Studio. Новые наборы инструкций обычно добавляются до того, как станут доступны микросхемы, которые их поддерживают, поэтому вы можете использовать их для доступа к новым инструкциям сразу после выпуска.

Программирование с внутренними функциями SIMD - это своего рода полпути между C ++ и полной сборкой. Компилятор по-прежнему заботится о таких вещах, как соглашения о вызовах и выделение регистров, а также некоторая оптимизация (особенно для генерации констант и других широковещательных сообщений) - но обычно то, что вы пишете, более или менее соответствует тому, что вы получаете на уровень сборки.

Встроенная сборка

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

Автономная сборка

Вы также можете просто написать всю свою функцию ядра в сборке, собрать ее так, как вы хотите, а затем объявить ее extern "C" и вызвать ее из C ++. Это похоже на вариант встроенной сборки, но работает с компиляторами, которые не поддерживают встроенную сборку (например, 64-разрядная Visual Studio). Вы также можете использовать другой ассемблер, если хотите, что особенно удобно, если вы ориентируетесь на несколько компиляторов C ++, поскольку тогда вы можете использовать один ассемблер для всех из них.

Вам необходимо самостоятельно позаботиться о соглашениях о вызовах и других беспорядочных вещах, таких как DWARF-информация о размотке и Обработка Windows SEH.

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

Автоматическая векторизация ⁴

Если сегодня вы хотите написать быструю криптографию для ЦП, вы в значительной степени ориентируетесь в основном на инструкции SIMD. Большинство новых алгоритмов, разработанных с программной реализацией, также разработаны с учетом векторизации.

Вы можете использовать встроенные функции или сборку для написания кода SIMD, но вы также можете написать обычный скалярный код и полагаться на auto -вектор. Они получили плохую репутацию еще на заре SIMD, и, хотя они все еще далеки от совершенства, они прошли долгий путь.

Рассмотрим эту простую функцию с байтовыми массивами payload и key и xors key в полезную нагрузку:

void otp_scramble(uint8_t* payload, uint8_t* key, size_t n) {
    for (size_t i = 0; i < n; i++) {
        payload[i] ^= key[i];
    }
}

Это, конечно, пример софтбола, но в любом случае gcc, clang и icc векторизуют его в что-то вроде этот внутренний цикл ⁴:

  movdqu xmm0, XMMWORD PTR [rdi+rax]
  movdqu xmm1, XMMWORD PTR [rsi+rax]
  pxor xmm0, xmm1
  movups XMMWORD PTR [rdi+rax], xmm0

Он использует инструкции SSE для загрузки и xor по 16 байтов за раз. Однако разработчику нужно подумать только о простом скалярном коде!

Одним из преимуществ этого подхода перед встроенными функциями или сборкой является то, что вы не запекаете длину SIMD набора инструкций на уровне исходного кода. Тот же самый код C ++, что и выше, скомпилированный с -march=haswell, приводит к такому циклу, как:

  vmovdqu ymm1, YMMWORD PTR [rdi+rax]
  vpxor ymm0, ymm1, YMMWORD PTR [rsi+rax]
  vmovdqu YMMWORD PTR [rdi+rax], ymm0

Он использует инструкции AVX2, доступные на Haswell, чтобы обрабатывать 32 байта за раз. Если вы компилируете с -march=skylake-avx512, clang использует 64-байтовые vxorps инструкции для zmm регистров (но gcc и icc используют 32-байтовые внутренние циклы). Так что, в принципе, вы можете воспользоваться преимуществами нового ISA, просто перекомпилировав его.

Обратной стороной автоматической векторизации является то, что она довольно хрупкая. То, что автоматически векторизуется в одном компиляторе, может отсутствовать в другом или даже в другой версии того же компилятора. Поэтому вам нужно убедиться, что вы получаете желаемые результаты. Авто-векторизатор часто работает с меньшим объемом информации, чем есть у вас: он может не знать, что длина ввода кратна некоторой мощности или двум или что указатели ввода выровнены определенным образом. Иногда вы можете передать эту информацию компилятору, но иногда нет.

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

  movzx ecx, BYTE PTR [rsi+rax]
  xor BYTE PTR [rdi+rax], cl
  lea rcx, [rax+1]
  cmp rdx, rcx
  jbe .L1
  movzx r8d, BYTE PTR [rsi+1+rax]
  xor BYTE PTR [rdi+rcx], r8b
  lea rcx, [rax+2]
  cmp rdx, rcx
  jbe .L1
  movzx r8d, BYTE PTR [rsi+2+rax]
  xor BYTE PTR [rdi+rcx], r8b
  lea rcx, [rax+3]
  cmp rdx, rcx
  jbe .L1
  movzx r8d, BYTE PTR [rsi+3+rax]
  xor BYTE PTR [rdi+rcx], r8b
  lea rcx, [rax+4]
  cmp rdx, rcx
  jbe .L1
  movzx r8d, BYTE PTR [rsi+4+rax]
  xor BYTE PTR [rdi+rcx], r8b
  lea rcx, [rax+5]
  cmp rdx, rcx
  jbe .L1
  movzx r8d, BYTE PTR [rsi+5+rax]
  xor BYTE PTR [rdi+rcx], r8b
  lea rcx, [rax+6]
  cmp rdx, rcx
  jbe .L1
  movzx r8d, BYTE PTR [rsi+6+rax]
  xor BYTE PTR [rdi+rcx], r8b
  lea rcx, [rax+7]
  cmp rdx, rcx
  jbe .L1
  movzx r8d, BYTE PTR [rsi+7+rax]
  xor BYTE PTR [rdi+rcx], r8b
  lea rcx, [rax+8]
  cmp rdx, rcx
  jbe .L1
  movzx r8d, BYTE PTR [rsi+8+rax]
  xor BYTE PTR [rdi+rcx], r8b
  lea rcx, [rax+9]
  cmp rdx, rcx
  jbe .L1
  movzx r8d, BYTE PTR [rsi+9+rax]
  xor BYTE PTR [rdi+rcx], r8b
  lea rcx, [rax+10]
  cmp rdx, rcx
  jbe .L1
  movzx r8d, BYTE PTR [rsi+10+rax]
  xor BYTE PTR [rdi+rcx], r8b
  lea rcx, [rax+11]
  cmp rdx, rcx
  jbe .L1
  movzx r8d, BYTE PTR [rsi+11+rax]
  xor BYTE PTR [rdi+rcx], r8b
  lea rcx, [rax+12]
  cmp rdx, rcx
  jbe .L1
  movzx r8d, BYTE PTR [rsi+12+rax]
  xor BYTE PTR [rdi+rcx], r8b
  lea rcx, [rax+13]
  cmp rdx, rcx
  jbe .L1
  movzx r8d, BYTE PTR [rsi+13+rax]
  xor BYTE PTR [rdi+rcx], r8b
  lea rcx, [rax+14]
  cmp rdx, rcx
  jbe .L1
  movzx eax, BYTE PTR [rsi+14+rax]
  xor BYTE PTR [rdi+rcx], al

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

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

¹ Преимущество подхода gcc здесь заключается в том, что во время выполнения, если платформа поддерживает popcnt, этот вызов может разрешить реализацию, которая просто использует инструкцию popcnt, используя механизм GNU IFUNC.

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

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

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

⁵ С небольшими отличиями: gcc, как показано, clang немного развернут, а icc использовал load-op pxor, а не отдельную загрузку.