Предсказание ветвлений в CPU: скрытое узкое место кода

Есть знаменитый ответ на Stack Overflow, который просмотрели более 3 миллионов раз. Вопрос такой: почему обработка отсортированного массива быстрее, чем несортированного? Код одинаковый — цикл с оператором if. Единственное различие в том, отсортирован ли входной массив. Отсортированный вариант работает в 6 раз быстрее. Объяснение — предсказание ветвлений в CPU — показывает один из самых важных факторов производительности в современных вычислениях.

Каждый if, каждое условие цикла, каждый case в switch — это ветвления в вашем коде. CPU встречает их миллиарды в секунду и должен предсказать исход каждого, прежде чем узнает реальный ответ. Если предсказание верное, выполнение идёт на полной скорости. Если ошибочное, CPU выбрасывает 10–20 тактов работы и начинает заново. Понимание этого механизма меняет подход к написанию критичного к производительности кода.

Зачем CPU нужно предсказывать

Современные CPU работают с конвейером: они не ждут завершения одной инструкции, прежде чем начать следующую. Типичный конвейер CPU имеет 12–20 стадий. Пока выполняется одна инструкция, ещё около 15 следующих уже выбираются, декодируются и готовятся. Именно конвейеризация позволяет CPU выполнять примерно одну инструкцию за такт, хотя каждая из них требует многих тактов на завершение.

Но когда CPU встречает ветвление (if x > 0), возникает проблема. Следующая инструкция зависит от того, выполнится ли переход. CPU не знает ответа несколько тактов — результат сравнения должен пройти через конвейер. У него два варианта: остановить конвейер и ждать (теряя 15+ тактов впустую) или угадать направление ветвления и продолжать работу.

CPU всегда угадывают. Предсказатель ветвлений делает прогноз, и процессор выбирает и выполняет инструкции по предсказанному пути. Если прогноз верен, ничего не теряется. Если ошибся, CPU должен сбросить неправильно выполненные инструкции, отбросить их результаты и начать с правильного пути. Такой «сброс конвейера» стоит примерно 15–20 тактов на современных x86 CPU — это как 15–20 потерянных инструкций.

Как работают предсказатели ветвлений

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

Простой случай: смещённые ветвления

Многие ветвления сильно смещены — почти всегда идут в одну сторону. Проверка ошибок, которая проходит в 99,9% случаев, или условие цикла, истинное 999 итераций и ложное один раз. Предсказатель быстро усваивает такие шаблоны и достигает почти идеальной точности. Ветвление, которое идёт в одну сторону в 99% случаев, имеет максимум 1% промахов.

Распознавание шаблонов

Современные предсказатели умеют больше, чем просто отслеживать смещение. Они распознают повторяющиеся шаблоны. Если ветвление следует шаблону «переход-переход-без перехода-переход-переход-без перехода...» (период 3), предсказатель выучит его и угадает правильно. Предсказатель TAGE (TAgged GEometric history length), который используется в современных CPU Intel и AMD, ведёт несколько таблиц истории разной длины и улавливает шаблоны с периодами от 2 до нескольких сотен.

Коррелированные ветвления

Самые продвинутые предсказатели также учатся находить связи между ветвлениями. Если переход по ветви A всегда означает, что ветвь B (дальше по коду) не выполняется, предсказатель может выучить эту зависимость. Это называется «двухуровневым адаптивным предсказанием», и оно справляется с такими шаблонами кода:

// These branches are correlated
if (x > 0) {      // Branch A
y = x * 2;
}
// ... some code ...
if (x <= 0) {     // Branch B — always opposite of Branch A
y = -x;
}
// The predictor learns: when A is taken, B is not taken, and vice versa
// Both branches are predicted with near-perfect accuracy

Разгадка тайны отсортированного массива

Вернёмся к знаменитому вопросу со Stack Overflow. Код выглядит так:

int sum = 0;
for (int i = 0; i < arraySize; i++) {
if (data[i] >= 128)    // This is the critical branch
sum += data[i];
}
// With SORTED data [0, 1, 2, ..., 127, 128, 129, ..., 255]:
// Branch pattern: NNNNNN...NNNTTTTTT...TTT
// First half: always NOT taken. Second half: always taken.
// Prediction accuracy: ~99.9% (only mispredicts at the transition)
// With UNSORTED data [random values 0-255]:
// Branch pattern: TNNTTNNTTTNNTNNT... (random)
// Prediction accuracy: ~50% (no pattern to learn)
// Every misprediction costs ~15 cycles

На отсортированных данных ветвление полностью предсказуемо: в первой половине массива оно не выполняется, во второй — выполняется. Предсказатель быстро выучивает каждую фазу и ошибается только в одной точке перехода. На случайных данных ветвление — это фактически бросок монетки: предсказатель не может точнее ~50%, и половина итераций тратит по 15 тактов на сброс конвейера.

При 100 000 итераций и частоте промахов ~50% получаем 50 000 промахов × 15 тактов = 750 000 потерянных тактов. На CPU 3 ГГц это четверть миллисекунды — заметная доля общего времени выполнения такого простого цикла.

Сколько ветвлений может обработать ваш CPU?

У предсказателя ветвлений ограниченный объём памяти. Он отслеживает историю для конечного числа мест ветвлений с помощью структуры Branch Target Buffer (BTB) и связанных с ней таблиц истории. Современные CPU могут отслеживать десятки тысяч мест ветвлений, но крупные кодовые базы могут превысить этот лимит.

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

Дэниел Лемир опубликовал отличное исследование ёмкости предсказателей ветвлений на разных CPU. Результаты показывают, что современные Intel (Alder Lake и новее) эффективно предсказывают ветвления с историей глубиной примерно до 200 ветвлений — то есть предсказатель учитывает исходы последних ~200 ветвлений при прогнозе текущего. У AMD ёмкость схожая. Чипы ARM различаются сильнее; чипы Apple серии M имеют особенно мощные предсказатели ветвлений.

Пишем код, дружелюбный к предсказанию ветвлений

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

Заменяем ветвления арифметикой

Самое быстрое ветвление — то, которого не существует. Многие условные конструкции можно заменить безветвевой арифметикой.

// Branching version:
int max_branch(int a, int b) {
if (a > b) return a;
return b;
}
// Branchless version (compiler often does this automatically):
int max_branchless(int a, int b) {
return a ^ ((a ^ b) & -(a < b));
}
// Conditional move — the compiler's favorite trick:
int max_cmov(int a, int b) {
// Most compilers will emit a CMOV instruction for this
return (a > b) ? a : b;
}
// Clamping with branches:
int clamp_branch(int x, int lo, int hi) {
if (x < lo) return lo;
if (x > hi) return hi;
return x;
}
// Clamping branchless:
int clamp_branchless(int x, int lo, int hi) {
// min(max(x, lo), hi)
int t = x > lo ? x : lo;  // CMOV
return t < hi ? t : hi;   // CMOV
}

Современные компиляторы в целом неплохо преобразуют простые условия в инструкции CMOV (conditional move), которые полностью избегают ветвлений. Но не всегда: особенно когда у ветвлений есть побочные эффекты или когда ветка «then» дорогая. Явные безветвевые конструкции помогают в горячих циклах, где компилятор генерирует не оптимальный код.

Сортируем перед обработкой

Если вы собираетесь фильтровать данные через ветвление, предварительная сортировка делает ветвление полностью предсказуемым. Звучит контринтуитивно — сортировка стоит O(n log n) — но для больших наборов данных, где цикл обработки выполняется много раз или стоимость промахов высока, сортировка окупается.

Используем таблицы поиска

Сложную условную логику (switch с большим количеством case) можно заменить поиском по таблице. Вместо цепочки сравнений вы индексируете массив. Обращение к массиву может вызвать промах кэша, но это обычно дешевле, чем каскад ошибочно предсказанных ветвлений.

// Branch-heavy version:
char to_hex(int nibble) {
if (nibble < 10)
return '0' + nibble;
else
return 'a' + nibble - 10;
}
// Lookup table version (no branches):
static const char hex_table[] = "0123456789abcdef";
char to_hex_lut(int nibble) {
return hex_table[nibble];
}

Подсказки компилятору

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

// Tell the compiler that errors are unlikely
if (__builtin_expect(result == NULL, 0)) {
handle_error();
}
// C++20 provides cleaner syntax:
if (result == NULL) [[unlikely]] {
handle_error();
}
// Linux kernel defines macros for this:
#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
if (unlikely(ptr == NULL)) {
panic("null pointer");
}

Измеряем поведение ветвлений

Производительность предсказания ветвлений можно измерить напрямую с помощью аппаратных счётчиков производительности. В Linux perf stat показывает частоту промахов для любой программы.

# Measure branch prediction statistics
$ perf stat -e branches,branch-misses ./my_program
Performance counter stats for './my_program':
1,482,937,256  branches          # 892.7M/sec
3,271,842  branch-misses     # 0.22% of all branches
# 0.22% misprediction rate — excellent.
# Anything under 1% is good.
# Over 5% in a hot loop means branch prediction is hurting you.
# Over 10% means you should consider branchless alternatives.

Для микробенчмарков такие инструменты, как Google Benchmark, могут отслеживать branch-misses на итерацию и дают точную обратную связь о том, улучшило ли изменение кода поведение ветвлений. Это полезнее, чем замер реального времени, который включает шум от других процессов системы.

Когда это важно, а когда нет

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

Для всего остального — бизнес-логики, обработчиков API, CRUD-операций — предсказание ветвлений не важно. Ветвления в маршрутизаторе вашего веб-сервера — не узкое место. Не переписывайте читаемые цепочки if/else в нечитаемую безветвевую арифметику в коде, который выполняется раз на HTTP-запрос. Оптимизируйте там, где показывает профилировщик, а не там, где теория подсказывает, что может быть проблема.

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