SIMD должен знать каждый

Тезис Митчелла Хашимото заключается в том, что у повседневного использования SIMD есть единый шаблон, написать его не сложнее обычного цикла for, а инженеры, считающие SIMD инструментом исключительно для узких специалистов, добровольно отказываются от ускорения в 4-16 раз на циклах, которые у них уже есть. Примеры приведены на zig, поскольку именно на нём написан Ghostty, но ничего в аргументации не завязано на конкретный язык, кроме наличия обобщённых векторных типов.

Искать стоит любой цикл вида for (byte in bytes), for (character in string), for (value in array). SIMD превращает его в for (8 byte chunk in bytes). Выигрыш масштабируется вместе с числом lane'ов и требует объёма данных, достаточного для амортизации накладных расходов на инициализацию: сотни тысяч или миллионы байт дают отдачу, пара десятков - нет. Хашимото прямо подчёркивает, что simdutf и simdjson решают куда более сложные задачи и что вам не требуется заходить так далеко, чтобы получить пользу.

Пять шагов

1. Выполнить broadcast нужных констант и инициализировать векторные аккумуляторы.
2. Пройтись по входным данным кусками размером с вектор.
3. Выполнить сравнение или арифметическую операцию по всем lane'ам одновременно.
4. Свернуть (reduce) или сохранить векторный результат.
5. Обработать остаток скалярным хвостом - тем самым циклом, с которого всё начиналось.

Пример из Ghostty

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

while (end < cps.len and cps[end] > 0xF) end += 1;

Векторная версия добавляет двенадцать строк и не использует специфичных для конкретного CPU intrinsic'ов:

if (simd.lanes(u32)) |lanes| {
    const V = @Vector(lanes, u32);
    const threshold: V = @splat(0xF);
    while (end + lanes <= cps.len) : (end += lanes) {
        const values: V = cps[end..][0..lanes].*;
        const greater_than_threshold = values > threshold;
        if (@reduce(.And, greater_than_threshold)) continue;
        const mask: std.meta.Int(.unsigned, lanes) = @bitCast(greater_than_threshold);
        end += @ctz(~mask);
        break;
    }
}

while (end < cps.len and cps[end] > 0xF) end += 1;

simd.lanes(u32) - вспомогательная функция Ghostty, возвращающая количество значений u32, которые целевая платформа может обработать одновременно: 4 на ARM NEON, 8 на AVX2, 16 на AVX-512. Если подходящей ширины вектора нет, она возвращает null, и весь блок пропускается. @splat(0xF) копирует пороговое значение в каждый lane, поскольку для векторного сравнения вектор требуется с обеих сторон.

Цикл выполняется только тогда, когда остаётся полный вектор. Если при восьми lane'ах осталось пять значений, векторный цикл не может их загрузить, и вместо использования трюков с маскированной загрузкой (masked load) Ghostty оставляет их хвосту.

Сравнение values > threshold - это одна векторная инструкция, выдающая по одному булеву значению на lane:

values:                 { 0x41, 0x42, 0x43, 0x0A, 0x44, 0x45, 0x46, 0x47 }
threshold:              {  0xF,  0xF,  0xF,  0xF,  0xF,  0xF,  0xF,  0xF }
greater_than_threshold: { true, true, true, false, true, true, true, true }

На шаге 4 алгоритмы начинают различаться, и именно эта часть обычно выглядит непривычно. @reduce(.And, ...) сворачивает булевы значения через and. Если все проверки пройдены, continue переходит к следующему куску - для текста в терминале это самый частый сценарий. В противном случае булев вектор через @bitCast преобразуется в целое число с одним битом на lane, инвертируется (чтобы непрошедшие проверки стали единицами), а @ctz подсчитывает количество младших нулей, выдавая индекс первого несовпадения:

greater_than_threshold: { true, true, true, false, true, true, true, true }
mask:                   {    1,    1,    1,     0,    1,    1,    1,    1 }
~mask:                  {    0,    0,    0,     1,    0,    0,    0,    0 }

@ctz(~mask) возвращает 3 - индекс lane'а со значением 0x0A. Скалярный хвост затем обрабатывает оставшиеся значения (от нуля до семи штук), а также служит запасным путём, если simd.lanes вернул null. Исходная реализация остаётся в файле и выполняет сразу две задачи.

Хашимото оценивает предельное ускорение в 4x на NEON (включая Apple Silicon), в 8x на AVX2 и в 16x на AVX-512. В сквозном замере на десктопе с Intel и AVX2 - от вывода программы в терминал до финального состояния терминала - прирост составил около 5x. Разница между 8x и 5x приходится на сопутствующую работу, которая не была векторизована.

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

Почему бы не доверить это компилятору

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

Более веский довод связан с предсказуемостью. Если цикл настолько важен, что ради него нужно ускорение в 5x, векторизацию лучше зафиксировать явно в коде, а не полагаться на догадки компилятора: "Я не хочу, чтобы постороннее изменение кода или обновление компилятора молча превратило его обратно в скалярный цикл". Именно такой сбой описан в compiler-codegen-luck, где замена *p = x; p++; на *p++ = x переключила Clang между ветвлением и безветвевой инструкцией csel, изменив скорость быстрой сортировки более чем в 6 раз. Та же логика стоит и за go-bounds-checks-unsafe: если вы можете доказать то, чего компилятор не видит, выбор сводится к тому, чтобы либо зафиксировать это явно, либо постоянно перепроверять, согласен ли с вами оптимизатор.