CPU pipeline: 14 шагов одной инструкции

Современные CPU выполняют инструкции конвейерно. Одна инструкция (например, add, mov, cmp) проходит через ~10-20 стадий: fetch, decode, register rename, schedule, execute, write-back, retire. Каждая стадия занимает 1 такт.

Чтобы не простаивать, CPU держит несколько инструкций одновременно в разных стадиях pipeline. К тому моменту, когда первая инструкция дошла до execute, вторая на decode, третья на fetch. Это даёт throughput до 4-5 инструкций за такт на современных CPU.

Проблема: что fetch-ить после ветвления?

Pipeline работает идеально, пока CPU знает, какая инструкция следующая. Но что делать при ветвлении?

if x > 100:
    do_a()
else:
    do_b()

На уровне ассемблера это:

cmp x, 100
je else_branch
call do_a
jmp end
else_branch:
call do_b
end:

После cmp и je (jump if equal) CPU не знает, куда дальше — пока je не выполнится в стадии execute. Но что делать в stages fetch, decode? Что fetch-ить?

Если ждать — pipeline stalls (простой). Если ошибиться — приходится сбросить pipeline (flush) и начать заново с правильной ветки. Flush стоит ~14-20 тактов на современных CPU.

Решение: branch predictor

CPU оснащён branch predictor — отдельным блоком, который угадывает, куда пойдёт ветвление, ещё до его выполнения. Predictor отслеживает историю каждой условной инструкции: «эта ветка обычно идёт по true, эта — по false, эта чередуется».

Современные predictors имеют точность ~95-99% на типичных программах. Это значит, что pipeline почти всегда заполнен правильно — без stalls.

Стоимость misprediction:

• 5 ns при 14-стадийном pipeline на 3 GHz CPU.
• 10-20% performance hit на ветвистом коде, если predictor работает плохо.

Знаменитый эксперимент: sorted vs unsorted

В 2012 на Stack Overflow появился знаменитый вопрос: «Почему обработка sorted-массива быстрее, чем unsorted?». Это самый цитируемый пример эффекта branch prediction.

Идея: пройти по массиву и сложить только элементы больше некоего порога.

import timeit
import random
import array

def sum_above(arr, threshold):
    s = 0
    for x in arr:
        if x > threshold:
            s += x
    return s

N = 1_000_000
threshold = 128

# Случайные данные
random.seed(42)
unsorted = array.array('i', [random.randint(0, 255) for _ in range(N)])

# Те же данные, но отсортированные
sorted_arr = array.array('i', sorted(unsorted))

t_unsorted = min(timeit.repeat(
    lambda: sum_above(unsorted, threshold),
    number=3, repeat=3
)) / 3

t_sorted = min(timeit.repeat(
    lambda: sum_above(sorted_arr, threshold),
    number=3, repeat=3
)) / 3

print(f"Unsorted: {t_unsorted*1000:.0f} ms")
print(f"Sorted:   {t_sorted*1000:.0f} ms")
print(f"Speedup:  {t_unsorted/t_sorted:.2f}x")

Почему sorted быстрее? Потому что в unsorted массиве условие x > 128 непредсказуемо чередуется true/false. Branch predictor проседает к ~50% accuracy (хуже монетки), и каждый misprediction — 14-20 тактов в утиль.

В sorted массиве условие сначала всегда false (маленькие значения), потом всегда true (большие). Predictor угадывает безошибочно — pipeline никогда не сбрасывается.

Воспроизведение через numpy

Numpy выполняет операции в C, без overhead интерпретатора — там эффект branch prediction виден чище. Хотя numpy сам пытается использовать векторизованные операции (SIMD), где ветвления нет, но в более сложных случаях эффект есть:

import numpy as np
import time

N = 10_000_000
np.random.seed(42)

unsorted = np.random.randint(0, 256, size=N, dtype=np.int32)
sorted_arr = np.sort(unsorted.copy())

# Условная сумма через numpy boolean masking
def sum_above_np(arr, threshold):
    return int(arr[arr > threshold].sum())

# Замер
times_u = []
times_s = []
for _ in range(5):
    t = time.perf_counter()
    sum_above_np(unsorted, 128)
    times_u.append(time.perf_counter() - t)

    t = time.perf_counter()
    sum_above_np(sorted_arr, 128)
    times_s.append(time.perf_counter() - t)

print(f"Unsorted (numpy mask): {min(times_u)*1000:.1f} ms")
print(f"Sorted   (numpy mask): {min(times_s)*1000:.1f} ms")
print(f"Speedup:               {min(times_u)/min(times_s):.2f}x")

На numpy mask-based approach разница часто меньше, потому что numpy использует SIMD-инструкции, которые умеют делать parallel branch through masking. Но если написать скалярный numpy с ручным циклом — эффект ярче. Или через ctypes:

# Альтернатива через ctypes (если знакомо)
# Можно скомпилировать .c-файл с тем же алгоритмом и вызвать оттуда
# На C разница sorted vs unsorted легко 4-6x

Что это значит для DE

Branch prediction в DE-задачах проявляется в неожиданных местах:

1. if/else в hot loop — фильтрация в pipeline. Если условие непредсказуемо — медленнее.
2. JOIN на random data — каждое сравнение в hash bucket — условный jump. Branch predictor проседает.
3. Sort небольшими порциями + scan — иногда быстрее full scan, потому что условия в sorted predictable.
4. Sparse data processing — если 95% значений — нули, condition if x != 0 сильно предсказуемо.

Это объясняет, почему колоночные базы (ClickHouse, Snowflake, DuckDB) так быстрые на аналитических запросах: они работают векторизованно (без явных if-ов в hot path) и применяют операции через bitmask, где branch prediction не нужен.

Попробуй сам: насколько шумной должна быть условие, чтобы предсказатель сдался?

Поэкспериментируем: для разных «процентов true» в condition — сколько занимает работа?

import timeit
import random
import array

def sum_conditional(arr):
    s = 0
    for x in arr:
        if x == 1:    # условие — данные содержат много нулей или единиц
            s += 1
    return s

N = 1_000_000

for true_pct in [0, 10, 30, 50, 70, 90, 100]:
    random.seed(42)
    arr = array.array('i', [1 if random.random() < true_pct/100 else 0 for _ in range(N)])
    t = min(timeit.repeat(lambda: sum_conditional(arr), number=3, repeat=3)) / 3
    print(f"true_pct={true_pct:>3}%: {t*1000:>5.0f} ms")

true_pct=  0%:   72 ms  -- predictor легко угадывает 'всегда false'
true_pct= 10%:   77 ms  -- редкое true, легко предсказать 'почти всегда false'
true_pct= 30%:   85 ms  -- начинает быть сложно
true_pct= 50%:   88 ms  -- самое тяжёлое: 50/50, predictor бессилен
true_pct= 70%:   84 ms  -- симметрично 30%
true_pct= 90%:   76 ms  -- легко 'почти всегда true'
true_pct=100%:   72 ms  -- легко 'всегда true'

Шпаргалка по branch prediction

В следующем уроке — инструменты измерений: какие есть, как правильно использовать, на что обращать внимание.