Branch prediction: 10–30 циклов штрафа за неожиданный if

Тот же цикл. Те же данные. Одно сортирование массива перед циклом — и код становится в 2–3 раза быстрее. Алгоритм не изменился. Изменился только порядок данных — и CPU больше не ошибается в предсказаниях.

Как branch prediction работает

Modern CPU pipeline глубокий: 15–20+ стадий. CPU fetch-ит инструкции задолго до их исполнения. Когда встречается branch (if, for, while, virtual call), CPU не знает заранее, какой путь будет taken — но он должен что-то поставить в pipeline.

Branch predictor угадывает: taken или not-taken. CPU начинает исполнять предсказанный путь спекулятивно. Если угадал правильно — win, pipeline не останавливался. Если ошибся — pipeline flush: все спекулятивно исполненные инструкции выбрасываются, нужно начать с правильного пути. Цена: глубина pipeline × missed slots.

На современном x86 с pipeline depth ~19 стадий: 10–30 wasted cycles per misprediction.

TAGE predictor

Modern branch predictors умные. Intel и AMD используют TAGE (TAgged GEometric) predictor, комбинирующий несколько history length. Он запоминает не просто last-taken/not-taken, а complex patterns up to N branches назад.

Типичная accuracy: 95–99% на реальном коде.

Hard cases для любого predictor:

• Data-dependent branches (if на random input value).
• Virtual function calls с высокой polymorphism (непредсказуемый target).
• Очень длинные pipelines (Apple M1/M2/M3: 10+ стадий) — ошибка дороже.

Sorted-array trick

Проблема: tight loop суммирует элементы array, превышающие threshold.

int sum = 0;
for (int i = 0; i < N; i++) {
    if (arr[i] > threshold) sum += arr[i];  // branch 50/50 на random data
}

На random unsorted data: ~50% miss rate → ~15 wasted cycles per iteration.

Фикс: сортировка перед циклом.

std::sort(arr, arr + N);  // O(N log N) один раз
for (int i = 0; i < N; i++) {
    if (arr[i] > threshold) sum += arr[i];
}

Теперь первая половина цикла всегда not-taken (arr[i] <= threshold), вторая всегда taken. Predictor учит pattern быстро: один transition point, 99%+ accuracy после него.

Несмотря на O(N log N) sort cost, общее время часто меньше — потому что inner loop перестаёт платить mispredict penalty на каждой итерации.

Branchless код

Когда branch непредсказуем и нельзя re-sort данные — убирай branch совсем.

// branched (mispredict-friendly если arr[i] > 0 random):
if (arr[i] > 0) y = a; else y = b;

// branchless:
y = (arr[i] > 0) * a + (arr[i] <= 0) * b;

Или CMOV (conditional move на x86) — компилятор часто emit-ит автоматически при -O2:

y = arr[i] > 0 ? a : b;  // компилятор может генерировать cmov

Tradeoff:

• Branchless версия всегда вычисляет обе стороны.
• Branched версия пропускает одну сторону но платит mispredict cost когда ошибается.

Tipping point: если branch предсказуем 95%+, branched быстрее. Если 50/50 (random), branchless выигрывает в 2–5x.

PGO для branches

Profile-guided optimisation (PGO): build с instrumentation, run representative workload, recompile с profile данными.

PGO для branches:

• Predicted-taken branches размещаются последовательно в памяти — hot path contiguous в instruction cache.
• Basic blocks переупорядочиваются, держа hot path вместе.
• Компилятор инлайнит callees, которые hot, и не инлайнит cold.

Real speedup: 10–30% на большинстве production workloads. Компилятор делает автоматически то, что разработчик иначе делает через __builtin_expect и ручное аннотирование.