13. Предсказание ветвлений и Спекулятивное исполнение

В предыдущей лекции 12. Суперскалярность, Out Of Order Execution и Register Renaming мы увидели, как современное процессорное ядро превратилось в ненасытный многопоточный двигатель. Благодаря суперскалярным портам, внеочередному исполнению и сотням физических регистров ядро жаждет непрерывного притока работы, заглядывая на сотни инструкций вперед.

Но на пути этого высокоскоростного локомотива стоит фундаментальное препятствие, пронизывающее любой программный код — ветвления (Branches).

Каждый оператор if, switch или цикл for в вашем коде на Go компилируется в ассемблерную инструкцию условного перехода (например, JEQ — Jump if Equal, JNE — Jump if Not Equal).

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

• Нужно ли перепрыгнуть на новый адрес памяти (блок else)?
• Или продолжать исполнять код последовательно (тело if)?

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

Если бы процессор послушно нажимал на тормоза перед каждым if, конвейер опустел бы, а 8 параллельных портов ALU простаивали бы вхолостую.

Чтобы не терять скорость, создатели процессоров наделили кристалл способностью предвидеть будущее.

Предсказатель ветвлений (Branch Predictor)

Представьте скоростной поезд «Сапсан» или TGV, летящий на скорости $300\text{ км/ч}$ сквозь густой туман. Впереди железнодорожная стрелка. Если поезд будет полностью останавливаться перед каждой стрелкой, ждать стрелочника и разгоняться заново, его средняя скорость упадет до черепашьей.

Вместо остановки машинист на полной скорости угадывает положение стрелки и несется вперед.

В кремнии эту роль выполняет Branch Predictor (Предсказатель ветвлений) — сложнейший аппаратный комплекс прямо на входе конвейера CPU. Это не просто случайное подбрасывание монетки, а специализированная аппаратная нейросеть (в современных ядрах применяются алгоритмы TAGE — TAgged GEometric history length, перцептронные модели и двухуровневые адаптивные таблицы).

flowchart TD
    subgraph Frontend ["Front-End процессора (Выборка команд)"]
        Fetch["Выборка условного перехода<br>(JEQ, JNE, CMP)"] --> BP{"Branch Predictor<br>(BHT + BTB + TAGE)"}
    end

    BP -->|"Предсказание: Прыжок (Taken)<br>Точность 97–99%"| SpecPath["<b>Спекулятивное исполнение</b><br>Выполнение инструкций целевой ветки в ALU"]

    SpecPath --> Verify{"Реальное вычисление<br>условия в ALU"}

    Verify -->|"Угадал! (Hit)"| Commit["<b>Commit в ROB</b><br>Задержка: 0 тактов!<br>Код летит на полной скорости"]
    Verify -->|"Ошибся! (Mispredict)"| Flush["<b>Pipeline Flush!</b><br>Сброс конвейера, очистка ROB<br>Штраф: 15–20 тактов простоя"]

    Flush --> Reload["Перезагрузка конвейера<br>с правильного адреса"]

    classDef fe fill:#131d33,stroke:#38bdf8,stroke-width:1px,color:#f8fafc;
    classDef hit fill:#1e293b,stroke:#10b981,stroke-width:1px,color:#f8fafc;
    classDef miss fill:#1e293b,stroke:#f43f5e,stroke-width:1px,color:#f8fafc;
    class Frontend,Fetch,BP fe;
    class SpecPath,Commit hit;
    class Verify,Flush,Reload miss;
  

Для предсказания используются специализированные аппаратные кэши:

1. BHT (Branch History Table — Таблица предыстории переходов): массив 2-битных насыщающихся счетчиков. Если переход по данному адресу произошел, счетчик инкрементируется; если не произошел — декрементируется. Состояния «уверенно взят» / «скорее всего взят» защищают процессор от ложных переключений на редких аномалиях в циклах;
2. BTB (Branch Target Buffer — Буфер целей ветвления): сверхбыстрый ассоциативный кэш, хранящий не только факт перехода, но и целевой адрес в памяти, куда именно нужно прыгнуть. Без BTB процессор потерял бы несколько тактов просто на вычисление адреса перехода!

Спекулятивное исполнение (Speculative Execution)

Предсказать ветку — это только полдела. Настоящее безумие начинается дальше.

Сделав догадку, процессор не просто подготавливает инструкции. Он начинает физически выполнять их на полную мощность задолго до того, как узнает, было ли предсказание верным! Этот процесс называется Спекулятивным исполнением (Speculative Execution).

Ядро читает память, перемножает числа в ALU, переименовывает регистры и загружает строки кэша. Но все эти вычисления производятся в «теневом режиме» — их результаты сохраняются исключительно в буфере переупорядочивания (ROB), не фиксируясь в архитектурном состоянии процессора.

Когда операнды условия наконец приходят и ALU вычисляет реальный результат проверки, разыгрывается один из двух сценариев:

Сценарий 1: Процессор угадал (Branch Hit)

Происходит триумф оптимизации. Результаты спекулятивных вычислений мгновенно утверждаются (Commit) из буфера ROB в видимые регистры и кэш данных. Для вашей программы ветвление прошло с нулевой задержкой ($0\text{ тактов}$)!

Сценарий 2: Процессор ошибся (Branch Misprediction)

Наступает аппаратная расплата. Процессор осознает, что последние 15–20 тактов вычислял бессмысленный мусор по ложному пути.
Аппаратура вынуждена совершить экстренную остановку:

1. Все спекулятивные результаты вычислений в буфере ROB аннулируются;
2. Производится полная очистка конвейера — Pipeline Flush;
3. Внутреннее состояние регистров откатывается назад к точке ветвления;
4. Счетчик команд RIP перезагружается правильным адресом из альтернативной ветки, и конвейер начинает наполняться с нуля.

Штраф за один неверный прогноз составляет от 15 до 20+ тактов CPU. Если в горячем цикле ветвление непредсказуемо, процессор будет тратить до 70% своего времени не на полезные вычисления, а на бесконечные сбросы конвейера!

Mechanical Sympathy: Отсортированные данные быстрее

Влияние предсказателя ветвлений на производительность реального программного кода иллюстрирует знаменитый эксперимент (ставший легендой Computer Science): почему фильтрация отсортированного массива работает в разы быстрее неотсортированного?

Напишем эталонный тест на Go:

package main

import (
    "fmt"
    "math/rand"
    "sort"
    "time"
)

func main() {
    const size = 1_000_000
    data := make([]int, size)

    // Заполняем массив случайными числами от 0 до 255
    for i := range data {
        data[i] = rand.Intn(256)
    }

    _ = sort.Ints // пакет подключён, чтобы пример компилировался и с закомментированной строкой ниже

    // Раскомментируйте эту строку для демонстрации магии:
    // sort.Ints(data)

    start := time.Now()
    var buckets [256]int

    // Горячий цикл с простым условием внутри.
    // Тело с записью в память (buckets[v]++) компилятор не может заменить на CMOV,
    // поэтому ветвление остаётся настоящим.
    for _, v := range data {
        if v > 128 {
            buckets[v]++
        }
    }

    elapsed := time.Since(start)
    fmt.Printf("Бакет[200]: %d, Время: %v\n", buckets[200], elapsed)
}

Посмотрим на поведение железа в двух случаях:

Случай А: Неотсортированный массив

Числа идут вперемешку: 210, 15, 189, 4, 130....
Условие v > 128 ведет себя как генератор случайных величин: True, False, True, False, False...
Branch Predictor процессора пытается уловить логику там, где царит белый шум. Его точность падает примерно до 50% (как угадывание орла и решки). Примерно на каждом втором числе ядро процессора спотыкается, делает сброс конвейера (Pipeline Flush) и теряет порядка 15–20 тактов.

Случай Б: Отсортированный массив

Мы раскомментировали sort.Ints(data). Массив упорядочен: 0, 1, 2... 128, 129, 200....
Теперь первые 500 000 итераций условие выдает строго False, а оставшиеся 500 000 итераций — строго True.
Предсказатель мгновенно адаптируется: насыщающиеся счетчики BHT защелкиваются в состоянии «уверенно не брать переход», а во второй половине — «уверенно брать».
Предсказатель ошибется ровно один раз за миллион итераций — на границе перехода возле числа 128! Точность предсказания составляет более 99.99%.

Итог: Один и тот же цикл, один и тот же объем данных, абсолютно одинаковая алгоритмическая сложность $O(N)$ — но отсортированный массив обрабатывается в несколько раз быстрее (в нашем замере на Go 1.27.1 с телом buckets[v]++ — примерно в 3,5 раза; точное число зависит от процессора) исключительно благодаря механическому сочувствию к Branch Predictor'у!

Branchless Programming (Программирование без ветвлений)

Как опытный разработчик может радикально обезопасить свой код от потерь на промахах ветвления?
Один из способов победить штраф за сброс конвейера — избавиться от ветвления в коде (Branchless Programming) — но с оговорками: CMOV вычисляет обе стороны и ждёт данных от обеих, поэтому на хорошо предсказуемых ветвях он может быть медленнее обычного перехода, а компилятор Go применяет его не всегда (например, для abs ниже на Go 1.27.1 ветвление остаётся и для int32, и для int64). Поэтому ручной трюк оправдан, но проверять нужно измерениями.

В архитектуре x86-64 есть специальная инструкция CMOV (Conditional Move — Условное копирование). Она проверяет флаги ALU и перезаписывает регистр без инструкции прыжка JMP. Кроме того, программисты часто заменяют логику побитовыми операциями.

Сравним два способа нахождения абсолютного значения числа (модуля $|x|$):

Вариант с ветвлением (Опасен для Branch Predictor)

func absBranch(x int32) int32 {
    if x < 0 {
        return -x // Потенциальный промах предсказателя
    }
    return x
}

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

Branchless-вариант (Чистая математика)

func absBranchless(x int32) int32 {
    // Арифметический сдвиг вправо:
    // если x < 0, то mask = -1 (бинарно все единицы: 0xFFFFFFFF)
    // если x >= 0, то mask = 0 (бинарно все нули: 0x00000000)
    mask := x >> 31

    // Побитовое исключающее ИЛИ и вычитание:
    // для x >= 0: (x ^ 0) - 0 = x
    // для x < 0:  (x ^ -1) - (-1) = (~x) + 1 = -x (дополнительный код!)
    return (x ^ mask) - mask
}
// Крайний случай: для x = math.MinInt32 результат переполняется
// и остаётся math.MinInt32 (у -x то же самое).

Branchless-код обладает потрясающими свойствами:

1. Детерминированная скорость: он выполняется строго за фиксированные 2–3 такта CPU, независимо от входных данных;
2. Нулевой риск промаха: здесь нет инструкции ветвления, а значит, физически невозможен сброс конвейера;
3. Безопасность в криптографии: в пакете crypto/subtle алгоритмы обязаны выполняться за строго константное время (Constant-Time Execution), чтобы злоумышленник не мог подобрать приватный ключ шифрования по колебаниям времени выполнения (атаки по сторонним каналам — Timing Attacks). Предсказатель ветвлений — лишь один из источников таких колебаний (есть ещё кэши, зависимость времени DIV от операндов и т.д.). Для аппаратных нюансов в Go 1.24 появилась функция crypto/subtle.WithDataIndependentTiming, которая на процессорах Arm64 с поддержкой FEAT_DIT включает режим выполнения с независимым от данных временем (DIT); на остальных архитектурах (в том числе x86-64) она просто выполняет переданную функцию без побочных эффектов.

Итог

1. Конфликт управления (Control Hazard): условные операторы (if, switch, for) создают неопределенность для конвейера. Ожидание вычисления условия заморозило бы ядро на десятки тактов.
2. Branch Predictor: сложнейший аппаратный модуль прогнозирования на базе перцептронов и таблиц истории (BHT, BTB, TAGE), угадывающий путь ветвления с точностью до 98–99%.
3. Спекулятивное исполнение: процессор физически вычисляет угаданную ветку наперед в теневом буфере ROB. Успех дает нулевую задержку ветвления ($0\text{ тактов}$). Ошибка (Mispredict) карается сбросом конвейера (Pipeline Flush) и потерей 15–20 тактов.
4. Mechanical Sympathy: упорядочивание данных (0, 1, 2... 128, 129, 200...) позволяет предсказателю достичь точности более 99.9%, ускоряя работу одного и того же алгоритма в несколько раз (если ветвление не заменено на CMOV).
5. Branchless Programming: замена ветвлений на инструкции CMOV и побитовую арифметику исключает риск промаха; побитовые маски (так устроен crypto/subtle) критически важны для криптографии с постоянным временем исполнения.

Мы выяснили, как процессоры выжимают последние капли параллелизма из обычного последовательного кода, заставляя несколько ALU работать одновременно. Но что, если нам нужно применить одну и ту же математическую операцию к огромному массиву чисел (например, сложить миллион векторов или обработать кадр видео)? Неужели процессор должен прогонять этот миллион элементов через конвейер по одному?

В следующей лекции мы откроем мир векторной обработки данных — параллелизма на уровне данных: 14. SIMD. Single Instruction Multiple Data.