Процессор в вашем компьютере угадывает будущее. И ошибается в 5% случаев

В прошлую пятницу я объяснял джуну, почему его код на отсортированном массиве работает в шесть раз быстрее, чем на неотсортированном. Тот же массив, тот же алгоритм, и те же данные. Просто в другом порядке. Джун смотрел на меня как на сумасшедшего и, честно говоря, я его понимаю.

Потому что ответ звучит безумно: процессор внутри вашего ноутбука постоянно пытается предсказать будущее. Буквально. Он гадает, какая ветка if выполнится ещё до того, как условие будет вычислено. И на отсортированных данных ему угадывать проще.

Ну, давайте разбираться.

Конвейер, или почему процессору вообще нужно гадать

Представьте ресторан. Шеф-повар не ждёт, пока первое блюдо полностью приготовится, сервируется и доедается, он начинает готовить второе параллельно. И третье, и четвёртое. В каждый момент времени на кухне в разных стадиях готовки находятся десять блюд одновременно.

Процессор работает так же. Это называется конвейер (pipeline) — инструкция проходит через несколько стадий: fetch, decode, execute, memory access, write back. Пока одна инструкция выполняется, следующая декодируется, а третья уже загружается из памяти. В современных процессорах конвейер может быть глубиной 15–20 стадий. Иногда больше.

И всё прекрасно ровно до момента, когда вы пишете if.

if (x > 0) {
    doSomething();  // ветка A
} else {
    doOther();      // ветка B
}

Процессор дошёл до этого if. Значение x ещё не вычислено — оно где-то на пятой стадии конвейера, ждёт своей очереди. А загружать-то следующую инструкцию нужно прямо сейчас. Какую? doSomething()? Или doOther()?

Тут два варианта: остановиться и подождать (а это 15–20 тактов простоя — целая вечность по меркам процессора) или... угадать. Процессор угадывает.

Как угадывать будущее: от «орёл или решка» до нейронных сетей

Самый тривиальный вариант — предсказывать, что ветка всегда выполнится. Или всегда не выполнится. Это статическое предсказание, и оно работает... ну, примерно как монетка. 50% попаданий. Сойдёт для 1985 года, но не для 2026-го.

Дальше интереснее. Динамическое предсказание. Процессор ведёт историю: «прошлый раз эта ветка выполнилась, значит, и в этот раз выполнится». Это называется 1-bit predictor, и он удивительно хорош для циклов. Цикл на 1000 итераций? Предсказатель ошибётся два раза — на первой итерации и на последней. 99.8% точность.

Но для реального кода этого мало.

Двухбитный счётчик — маленький, но гордый

Инженерам Intel и AMD (ну и всем остальным, кто делает процессоры) пришла идея: а что если не менять предсказание после одной ошибки? Вдруг это случайность?

Двухбитный счётчик работает как ваша уверенность в чём-то:

Strongly Taken → Weakly Taken → Weakly Not Taken → Strongly Not Taken
     11              10              01                   00

Если ветка выполнилась — счётчик сдвигается вверх. Не выполнилась — вниз. Предсказание меняется, только когда вы пересекаете середину и одна осечка не ломает всю картину.

Точность уже 85–90%. Неплохо.

Двухуровневый предсказатель, или «а какой был паттерн?»

Вот тут начинается магия. Процессор запоминает не просто «выполнилась/не выполнилась», а паттерн последних N переходов. Допустим, ветка выполнялась так: да, да, нет, да, да, нет, да, да, нет... Видите паттерн? Процессор тоже видит.

Это работает через штуку под названием Branch History Register — сдвиговый регистр, который хранит последние, скажем, 12 результатов. Каждая уникальная комбинация из 12 бит указывает на свой двухбитный счётчик в Pattern History Table. По сути, процессор говорит: «Каждый раз, когда я видел паттерн 110110110110, следующим результатом было 1. Ставлю на 1».

И это работает очень хорошо.

TAGE, или то, что стоит в вашем процессоре прямо сейчас

Современные предсказатели — это TAGE (TAgged GEometric history length predictor).

Идея в следующем: несколько таблиц предсказаний с разной глубиной истории. Одна смотрит на последние 4 перехода, другая — на 8, третья — на 16, четвёртая — на 64... Геометрическая прогрессия. Для простого цикла хватит таблицы с короткой историей. Для сложного паттерна подключится таблица с длинной.

Результат? 95–97% точность на реальном коде. На некоторых бенчмарках — 98%.

Цена ошибки: 15 тактов псу под хвост

А вот теперь представьте, что процессор угадал неправильно. Он уже загрузил 15 инструкций из неверной ветки. Частично декодировал их. Может, даже начал выполнять. И тут приходит ответ: «нет, дружок, надо было в другую сторону».

Pipeline flush. Всё, что было загружено спекулятивно, — в мусорку. 15–20 тактов работы выкинуты. Процессор возвращается к правильной ветке и начинает заново.

На тактовой частоте 5 ГГц один такт — это 0.2 наносекунды. 20 тактов — 4 наносекунды. Фигня? Ну, если это происходит миллионы раз в секунду (а в горячем цикле запросто), вы внезапно теряете 30–50% производительности.

Тот самый пример с отсортированным массивом

Вернёмся к моему джуну. Вот код (классика, которую я видел кучу раз на Stack Overflow):

for (int i = 0; i < 100000; i++) {
    for (int j = 0; j < arraySize; j++) {
        if (data[j] >= 128) {  // вот этот if
            sum += data[j];
        }
    }
}

Массив data содержит случайные числа от 0 до 255. Порог — 128. Примерно половина чисел пройдёт фильтр, половина нет.

Неотсортированный массив: значения прыгают хаотично. 73, 201, 14, 255, 99, 182... Предсказатель видит: да, нет, нет, да, нет, да... Никакого паттерна. Он ошибается в ~50% случаев. Каждая ошибка — flush конвейера. Код ползёт.

Отсортированный массив: сначала идут числа от 0 до 127 (ветка не выполняется, тысячи раз подряд), потом от 128 до 255 (ветка выполняется, тысячи раз подряд). Предсказатель ошибается один раз — на границе. Один раз и код летит.

Разница на моей машине (Ryzen 7 5800X, GCC 12, -O2): 11.2 секунды против 1.9 секунды. В шесть раз.

(Я специально перепроверил перед написанием статьи. Шесть раз на одних и тех же данных.)

«Ну и что, мне теперь всё сортировать?»

Нет. Боже, нет. Сортировка ради предсказания веток — это как покупать самолёт, чтобы объехать пробку. Технически сработает, но есть способ получше. Вместо ветвления будем использовать старую добрую арифметику:

// Вместо:
if (data[j] >= 128) sum += data[j];

// Можно:
int t = (data[j] - 128) >> 31;  // 0 если >= 128, -1 если < 128
sum += ~t & data[j];

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

Компиляторы, кстати, иногда делают это сами — техника называется conditional move . GCC с -O3 может превратить ваш if в cmov автоматически. Может, но не обязан. И точно не в каждом случае.

Spectre, или когда предсказание веток становится уязвимостью

Помните 2018 год? Meltdown и Spectre? Так вот, Spectre — это в буквальном смысле эксплуатация предсказания веток.

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

Да, процессор сам прочитал чужую память, потому что угадал неправильно. Точнее, потому что угадал именно так, как вы хотели.

Это, пожалуй, самый красивый баг в истории вычислительной техники, аппаратный. Заложенный в саму идею спекулятивного выполнения. Патчи есть, но они стоят производительности — от 2% до 30% в зависимости от нагрузки.

Что с этим делать обычному разработчику

Ну, во-первых — почти ничего. И это нормально. Предсказатель веток работает достаточно хорошо, чтобы 99% кода не нуждались в ручной оптимизации под него. Компилятор умнее вас, и меня. (Ну, как правило.)

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

• perf stat на Linux покажет вам branch-misses — процент промахов предсказателя. Если там больше 10%, у вас проблема.

• Branchless код — замена if на арифметику, битовые операции, cmov. Не везде применимо, но где применимо — даёт ощутимый буст.

• Сортировка перед обработкой — иногда (иногда!) оправдана, если вы потом проходите по данным многократно.

• Профилирование — всегда, всегда, всегда. Не оптимизируйте по интуиции. Интуиция врёт. Моя так точно.

likely() и unlikely() макросы в C/C++ (или [[likely]]/[[unlikely]] в C++20) — это подсказки компилятору, а не процессору. Компилятор расположит код так, чтобы «вероятный» путь шёл без прыжка.

Момент который меня раздражает

Мы строим всё более сложные предсказатели, увеличиваем конвейеры, добавляем спекулятивное выполнение — и всё это ради чего? Ради того, чтобы последовательный код работал быстрее. Вместо того чтобы... ну, писать параллельный код?

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

Пять процентов ошибок. Звучит как отличный KPI, если подумать. Мой предсказатель веток в жизни (он же интуиция) работает сильно хуже.