В прошлую пятницу я объяснял джуну, почему его код на отсортированном массиве работает в шесть раз быстрее, чем на неотсортированном. Тот же массив, тот же алгоритм, и те же данные. Просто в другом порядке. Джун смотрел на меня как на сумасшедшего и, честно говоря, я его понимаю.
Потому что ответ звучит безумно: процессор внутри вашего ноутбука постоянно пытается предсказать будущее. Буквально. Он гадает, какая ветка 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, если подумать. Мой предсказатель веток в жизни (он же интуиция) работает сильно хуже.