Предсказание переходов и спекуляция: цена ошибки

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

В прямолинейном коде это тривиально — следующий адрес получается прибавлением длины команды. Но реальный код прямолинейным не бывает. Условия, циклы, вызовы, возвраты, виртуальные методы, switch, обработчики ошибок: по разным замерам на нагрузках общего назначения переходом оказывается порядка 15–25 % динамически исполненных команд, то есть примерно каждая пятая. Это порядок величины, сильно зависящий от кода: в плотном численном цикле переходов почти нет, в парсере или интерпретаторе байткода их доля выше.

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

Базовую механику «процессор выбирает и исполняет команды» считаем известной по вводному треку (Как работает процессор), работу с регистрами и стеком — по главе про ассемблер (Основы ассемблера).

Почему нельзя просто подождать

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

def cpi(dolya_perehodov: float, tochnost: float, shtraf_taktov: float) -> float:
    """Средний CPI при идеальном конвейере (1 такт на команду) плюс потери на переходах.

    dolya_perehodov — доля переходов среди динамических команд (например, 0.20);
    tochnost        — доля верно предсказанных переходов (0.0 — всегда мимо, 1.0 — идеал);
    shtraf_taktov   — сколько тактов теряется на одной ошибке.
    """
    return 1.0 + dolya_perehodov * (1.0 - tochnost) * shtraf_taktov


# Классы машин различаются штрафом: короткий конвейер микроконтроллера и
# широкое внеочередное ядро настольного класса — это разные порядки цены ошибки.
print(cpi(0.20, 0.00, 15))   # ждать всегда: 4.0 — конвейер работает на четверть силы
print(cpi(0.20, 0.60, 15))   # наивная статика: 2.2
print(cpi(0.20, 0.95, 15))   # неплохой динамический предсказатель: 1.15
print(cpi(0.20, 0.99, 15))   # хороший современный: 1.03

Числа условные, но соотношение показательно. Без предсказания глубокий конвейер бессмыслен: чем он длиннее, тем больше тактов пропадает на каждом переходе, и выигрыш от повышения частоты съедается простоями. Предсказание переходов — не оптимизация поверх конвейера, а условие его существования. Именно поэтому оно появилось не как «фича», а как необходимая часть любой машины, желающей исполнять больше одной команды за такт.

Обратите внимание и на другой конец шкалы: разница между точностью 95 % и 99 % — это разница CPI 1.15 против 1.03, то есть больше десяти процентов производительности на ровном месте. Вот почему за последние проценты точности индустрия готова платить десятками килобайт таблиц и целыми конференциями, посвящёнными одному этому вопросу.

Не один вопрос, а три

Слово «предсказание переходов» скрывает три независимые задачи. Их часто путают, а решаются они разными структурами и ошибаются по-разному.

Первый вопрос: есть ли в этом блоке переход вообще? Фронтенд читает из кэша команд не одну команду, а блок байтов, и делает это до декодирования. То есть в момент предсказания процессор ещё не знает, что там лежит. За это отвечает BTB (branch target buffer) — по сути кэш, помеченный адресами: «по такому-то адресу раньше встречался переход такого-то типа с такой-то целью». Промах BTB означает, что переход не был замечен, и фронтенд пойдёт читать байты подряд — то есть в цикле, чей заголовок вылетел из BTB, вы получите ошибку даже при идеально предсказуемом условии.

Второй вопрос: будет ли он взят? Это направление (direction) — единственный бит, за который и идёт вся борьба. Отвечает отдельная структура: таблицы счётчиков, история, TAGE или перцептрон — о них ниже.

Третий вопрос: куда именно? Для обычного условного перехода цель зашита в команде и сохранена в BTB. Но есть два тяжёлых случая. Возврат из функции (ret) идёт каждый раз в новое место — для него держат отдельный аппаратный стек адресов возврата (RAS, return address stack). Косвенные переходы (switch через таблицу, вызов виртуального метода, указатель на функцию) требуют предсказывать сам адрес — а это уже не бит, а слово, и ошибиться тут гораздо легче.

Ключевое свойство всей конструкции: она работает до декодирования, по одному лишь адресу. Предсказатель не «смотрит на код» — он смотрит на историю, привязанную к адресу. Это объясняет большую часть его странностей.

Статика: что можно сделать без истории

Самый дешёвый предсказатель — константа. «Никогда не взят» позволяет фронтенду просто идти подряд и не требует ни одного бита состояния; для этого достаточно ничего не делать. На типичном коде это даёт точность в районе половины — бесполезно.

Заметно лучше работает эвристика BTFNT (backward taken, forward not taken): переход назад считаем взятым, вперёд — не взятым. Идея простая и опирается на структуру кода: назад прыгают циклы, а цикл почти всегда исполняется больше одного раза; вперёд прыгают проверки ошибок и выходы, которые обычно не срабатывают. На коде общего назначения такая эвристика даёт порядок 70–80 % — достаточно, чтобы короткий конвейер жил, и недостаточно для длинного.

Дальше индустрия пробовала переложить работу на компилятор: класть в команду перехода бит- подсказку. Такие механизмы были в PA-RISC, PowerPC, Itanium, появлялись префиксы подсказок и в x86 поколения NetBurst. Все они, по сути, вышли из употребления, и причина поучительная: динамический предсказатель почти всегда знает больше, чем компилятор. Компилятор видит статический текст, предсказатель — конкретный ход конкретного запуска, включая то, что ветка ведёт себя по-разному в разных фазах программы. Биты подсказок либо игнорируются, либо занимают место в кодировке зря.

Это не значит, что компилятор бесполезен. Он влияет иначе — раскладкой кода:

// Подсказка компилятору (GCC/Clang). Она почти не влияет на предсказатель напрямую,
// но влияет на то, какой код окажется на прямом пути, а какой уедет в холодную секцию.
#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)

int handle(struct req *r) {
    if (unlikely(r == NULL))          // редкая ветка уедет из горячего участка
        return -EINVAL;               // и не будет занимать строки кэша команд
    if (unlikely(r->len > MAX_LEN))
        return -EMSGSIZE;
    return process(r);                // горячий путь остаётся линейным
}

Выигрыш здесь не столько в предсказании, сколько в плотности горячего кода и в том, что редкие пути не мусорят в кэше команд и в BTB. Ещё сильнее это работает при сборке с профилем (PGO): компилятор видит реальные частоты веток и переставляет базовые блоки так, чтобы типичный проход шёл подряд. Механику таких преобразований разбирает трек компиляторов (Оптимизации).

Двухбитный счётчик: минимум работающей памяти

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

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

Такой предсказатель называют bimodal. Он занимает два бита на запись, обновляется одной операцией и на предсказуемом коде даёт очень приличный результат. Его слабость видна сразу: он смотрит только на саму ветку и ничего не знает о контексте, в котором к ней пришли.

Корреляция: почему одной таблицы мало

Взгляните на классический пример:

if (x < 5)  { /* A */ }
if (y > 10) { /* B */ }
if (x < 5 && y > 10) { /* C */ }   // полностью определяется исходами A и B

Третья ветка не имеет собственной статистики — она функция двух предыдущих. Bimodal видит только «иногда взят, иногда нет» и колеблется. Но если добавить к индексу таблицы биты исходов последних переходов, ветка C становится идеально предсказуемой.

Так появились двухуровневые предсказатели (Yeh и Patt, начало 1990-х): регистр глобальной истории GHR хранит последние N исходов, и индекс в таблицу счётчиков строится из адреса и истории. Простейший рабочий вариант — gshare (McFarling, 1993): адрес и история складываются по исключающему ИЛИ.

Есть и симметричный подход — локальная история: для каждой ветки хранить её собственную последовательность исходов. Он отлично ловит регулярные шаблоны вроде «взят-взят-не взят, взят-взят-не взят» — то есть цикл с фиксированным малым числом итераций. Глобальная история ловит корреляции между разными ветками, локальная — периодичность одной. Ни одна не покрывает всё, поэтому появились турнирные предсказатели: два разных механизма работают параллельно, а третья таблица счётчиков помнит, кто из них чаще прав на этой конкретной ветке, и выбирает победителя. Классический пример такой схемы — Alpha 21264 (конец 1990-х).

Сравним три схемы на одной синтетической трассе. Симулятор помещается в полсотни строк, и писать такие модели полезно: это самый быстрый способ почувствовать, что именно ломает предсказание в вашем коде.

Псевдокод общего цикла:

для каждого перехода (адрес, реальный_исход) из трассы:
    индекс     = хэш(адрес, история)          # различается между схемами
    счётчик    = таблица[индекс]
    предсказание = старший_бит(счётчик)
    если предсказание != реальный_исход: промахи += 1
    таблица[индекс] = насытить(счётчик, реальный_исход)   # ±1 в пределах 0..3
    история = ((история << 1) | реальный_исход) и маска_истории

class Bimodal:
    """Таблица двухбитных счётчиков, индексируемая адресом перехода."""

    def __init__(self, bits: int = 12):
        self.mask = (1 << bits) - 1
        self.table = [1] * (1 << bits)        # старт в состоянии «слабо не взят»

    def index(self, pc: int) -> int:
        return (pc >> 2) & self.mask          # младшие биты адреса не несут информации

    def predict(self, pc: int) -> bool:
        return self.table[self.index(pc)] >= 2

    def update(self, pc: int, taken: bool) -> None:
        i = self.index(pc)
        # Насыщение: счётчик не выходит за пределы 0..3.
        self.table[i] = min(3, self.table[i] + 1) if taken else max(0, self.table[i] - 1)


class Gshare(Bimodal):
    """То же самое, но индекс смешан с глобальной историей."""

    def __init__(self, bits: int = 12, hist: int = 12):
        super().__init__(bits)
        self.hist_mask = (1 << hist) - 1
        self.ghr = 0

    def index(self, pc: int) -> int:
        return ((pc >> 2) ^ self.ghr) & self.mask

    def update(self, pc: int, taken: bool) -> None:
        super().update(pc, taken)
        self.ghr = ((self.ghr << 1) | int(taken)) & self.hist_mask


def run(predictor, trace) -> float:
    """Доля ошибок на трассе из пар (адрес, был_ли_взят)."""
    misses = 0
    for pc, taken in trace:
        if predictor.predict(pc) != taken:
            misses += 1
        predictor.update(pc, taken)
    return misses / len(trace)


# Трасса: две «шумные» ветки и третья, полностью определяемая первыми двумя.
import random
random.seed(7)
trace = []
for _ in range(200_000):
    a = random.random() < 0.5
    b = random.random() < 0.5
    trace.append((0x1000, a))
    trace.append((0x1010, b))
    trace.append((0x1020, a and b))        # коррелированная ветка

print(f"bimodal: {run(Bimodal(), trace):.3f}")   # около 0.33 — третья ветка не угадывается
print(f"gshare : {run(Gshare(), trace):.3f}")    # около 0.22 — коррелированная ветка выучена

Сложность одинакова у всех схем: O(1) по времени на переход (одно чтение, одно обновление — иначе предсказатель просто не успел бы за такт) и O(2^k) по памяти, где k — число бит индекса. Именно эта экспонента и есть главный инженерный ограничитель: точность растёт с размером таблиц, а площадь и энергия растут вместе с ней.

Здесь же вылезает главная беда простых схем — интерференция (aliasing). У таблицы счётчиков нет тегов: две разные ветки, попавшие в один индекс, делят один счётчик. Одна хорошо предсказуемая ветка может быть испорчена соседкой по индексу. Отсюда практическое следствие для программиста: значение имеет не только предсказуемость конкретного if, но и общее число активных ветвлений на горячем пути. Таблицы конечны, ветки друг друга вытесняют.

TAGE и перцептрон: то, что стоит в больших ядрах сейчас

Дальнейшая эволюция решает ровно две проблемы: интерференцию и то, что разным веткам нужна разная длина истории. Одной ветке хватает трёх последних исходов, другой нужно тридцать. Фиксированная длина всегда кому-то не подходит.

TAGE (TAgged GEometric history length, Seznec и Michaud, 2006) устроен так: несколько таблиц, каждая индексируется историей своей длины, причём длины растут геометрически (условно 5, 10, 20, 40, 80 последних исходов). В записях лежат теги — проверка, что запись действительно принадлежит этой ветке в этом контексте. Предсказание берётся из таблицы с самой длинной совпавшей историей: если для ветки нашёлся длинный контекст, он и точнее. Есть счётчики полезности: запись, которая давно ничего не даёт, вытесняется, новые записи выделяются в основном после ошибок. Фактически это ассоциативный кэш предсказаний с переменной длиной ключа.

Перцептронный предсказатель (Jiménez и Lin, 2001) идёт от машинного обучения: для каждой ветки хранится вектор весов, каждый вес отвечает одному биту истории, а предсказание — знак взвешенной суммы. Обучение простое: при ошибке (или при слабой уверенности) веса, совпавшие с исходом, увеличиваются, остальные уменьшаются. Плюс — длинная история стоит линейной, а не экспоненциальной памяти. Минус — линейный классификатор не выучит линейно неразделимые функции (то же XOR двух веток), и нужен конвейеризованный сумматор, чтобы уложиться в такт.

Реальные большие ядра 2010–2020-х используют гибриды: TAGE-подобное ядро с дополнительными компонентами, перцептронные схемы, отдельные предсказатели для циклов и косвенных переходов. Точные конструкции производители не публикуют — то, что известно публично, известно из исследовательских работ и из соревнования Championship Branch Prediction, где схемы сравниваются при фиксированном бюджете памяти (порядка десятков килобайт состояния — сам бюджет задаётся условиями соревнования). Практический вывод для инженера один: современный предсказатель на типичном коде ошибается редко, единицы промахов на тысячу команд, но это среднее по больнице; конкретно ваш горячий цикл может быть исключением.

Цели переходов: BTB, стек возвратов и косвенные ветвления

Направление — только половина дела. Разберём вторую.

BTB — кэш целей, и у него все свойства кэша: конечная ёмкость, ассоциативность, вытеснение, холодный старт. На больших ядрах он делится на уровни: маленький и быстрый, чтобы успеть за такт, и большой, но с задержкой в несколько тактов. Отсюда неочевидный эффект: программа с огромным «горячим» следом кода (крупные интерпретаторы, тяжёлые шаблонные обвязки, десятки мегабайт кода в одном процессе) может тормозить не из-за плохих веток, а из-за того, что переходы просто не попадают в BTB. Лечится это укрупнением редко используемых путей и раскладкой кода, а не переписыванием условий.

RAS — маленький аппаратный стек: команда вызова кладёт адрес возврата, ret его снимает. Пока пары вызов/возврат сбалансированы, точность близка к идеальной. Глубина конечна — на больших ядрах это порядок десятков записей, — и всё, что ломает дисциплину стека, ломает и предсказание:

• setjmp/longjmp и исключения, раскручивающие несколько кадров сразу;
• корутины и файберы, переключающие стек под ногами (это одна из причин, почему очень частое переключение легковесных потоков стоит дороже, чем кажется из подсчёта тактов);
• глубокая рекурсия, вылезающая за глубину RAS;
• хвостовые вызовы, превращающие call+ret в jmp — здесь эффект скорее полезный;
• вручную написанные последовательности, где ret используется как косвенный переход.

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

Классический пример — цикл диспетчеризации интерпретатора байткода: одна команда switch, через которую проходят все опкоды подряд. Приём «computed goto» (у каждого опкода своя копия перехода на следующий) исторически объясняли именно тем, что так у каждого места появляется своя история. Стоит знать, что более поздние измерения на ядрах с ITTAGE показывают: часть этого выигрыша современные предсказатели забирают сами, так что проверять надо на своей машине, а не по фольклору (см. работу Rohou, Swamy, Seznec, 2015 в источниках).

На стороне компилятора против косвенности работает девиртуализация: если профиль показывает, что 95 % вызовов идут в одну реализацию, компилятор вставляет проверку типа и прямой вызов, а косвенный оставляет как запасной путь. Условный переход по проверке предсказывается отлично — косвенный вызов заменяется на предсказуемую ветку. Это ещё один аргумент за сборку с профилем.

Что именно происходит при ошибке

Теперь главное — цена. Разберём по тактам, что теряется.

Разберём диаграмму словами.

Когда правда становится известна. Не при отставке команды, а при её исполнении: как только сравнение посчитано, переход сам сообщает фронтенду, что тот ошибся. Ждать отставки никто не станет — это стоило бы ещё десятков тактов. Ошибка перехода обрабатывается быстрее, чем исключение, именно потому, что она частая и потому что для неё заранее сохранена контрольная точка состояния переименования.

Что выбрасывается. Все команды моложе перехода — независимо от того, полезные они или нет. Сюда попадает и работа, которая была бы нужна в любом случае: сброс идёт по возрасту, а не по смыслу. Их результаты и так лежали в невидимом состоянии, поэтому архитектурно ничего не портится; портится только время.

Из чего складывается штраф. Задержка обнаружения (пока переход дойдёт до исполнения), восстановление состояния переименования, перезапуск выборки с правильного адреса, повторное прохождение всего фронтенда. Отсюда прямая связь: чем длиннее фронтенд, тем дороже ошибка.

Порядки величин по классам устройств — с обязательной оговоркой, что это именно порядки, и между поколениями и моделями они различаются:

Но такты — не вся история. На ядре, способном запускать 4–6 команд за такт, потерянные 15–20 тактов означают порядка сотни неиспользованных слотов исполнения. Именно поэтому в методике top-down анализа для этого выделена отдельная категория — «плохая спекуляция» (bad speculation): она измеряет не время, а долю пропускной способности ядра, потраченную на работу, которая была выброшена.

Как это измерить

Гадать здесь бессмысленно, всё измеряется аппаратными счётчиками.

# Linux, perf: сколько переходов и сколько промахов
perf stat -e instructions,branches,branch-misses ./app

# Пример вывода (порядок величин с реальной нагрузки):
#   12 340 000 000  instructions
#    1 980 000 000  branches            # около 16 % команд — переходы
#       31 500 000  branch-misses       #  1.6 % от переходов

# MPKI = branch-misses / instructions * 1000 = 2.55
# Это правильная метрика: проценты от переходов скрывают то,
# как часто переходы вообще встречаются.

# Где именно промахи — по функциям и строкам
perf record -e branch-misses:pp -g ./app
perf report --sort symbol

# Категория «плохая спекуляция» целиком, если ядро поддерживает top-down
perf stat --topdown ./app

Почему MPKI (misses per kilo-instruction) лучше процента точности: 99 % точности при доле переходов 25 % — это 2.5 промаха на тысячу команд; те же 99 % при доле 5 % — 0.5. Разница в пять раз, а «точность» одинаковая. Общая методика работы со счётчиками и профилировщиком разобрана в треке производительности (Профилирование CPU); там же — как не обмануться шумом измерений (Измерения).

Учтите два подвоха. Первый: счётчики считают и спекулятивно исполненное — часть событий относится к работе, которую выбросили. Суффикс :pp в perf запрашивает точную привязку к команде, и для охоты за ветками он практически обязателен. Второй: предсказатель — общий ресурс. На ядре с SMT два потока делят таблицы; после переключения контекста таблицы «холодные», и первые тысячи команд после возврата в ваш код предсказываются хуже. На коротких микробенчмарках это даёт красивые, но неверные результаты.

Классический пример: сортированный массив

Самая известная иллюстрация — вопрос, который годами держится в топе Stack Overflow: почему обработка отсортированного массива быстрее неотсортированного.

#include <stdlib.h>

// Один и тот же цикл. Разница только в том, отсортированы ли данные заранее.
long sum_above(const int *data, size_t n, int threshold) {
    long sum = 0;
    for (size_t i = 0; i < n; i++) {
        if (data[i] >= threshold)   // на случайных данных — монетка при каждой итерации
            sum += data[i];
    }
    return sum;
}

На отсортированных данных условие даёт длинные серии одинаковых исходов, предсказатель попадает почти всегда. На случайных данных при пороге около медианы условие — честная монетка, и никакая история не помогает: теоретический предел точности здесь 50 %, а промах стоит десятки тактов. Разница по времени между двумя запусками на большом внеочередном ядре легко достигает кратной — конкретный множитель зависит от машины и от того, что ещё делает цикл, поэтому меряйте у себя.

Тот же цикл без ветвления:

long sum_above_branchless(const int *data, size_t n, int threshold) {
    long sum = 0;
    for (size_t i = 0; i < n; i++) {
        // Маска: все единицы, если условие истинно, иначе нули.
        // Сдвиг знакового разряда — приём переносимый и предсказуемый по стоимости.
        long v = data[i];
        long mask = -(long)(v >= threshold);
        sum += v & mask;               // ветки нет, есть зависимость по данным
    }
    return sum;
}

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

Компилятор умеет делать это преобразование сам (if-conversion, обычно через команду условной пересылки: cmov в x86-64, csel в AArch64), но делает не всегда — он не знает распределения ваших данных без профиля. Смотреть, что получилось, надо в дизассемблере или на godbolt.org, а не по ощущениям.

Когда убирать ветку, а когда не трогать

Бесветочный код — не универсальное улучшение, а обмен: неопределённость управления меняется на детерминированную зависимость по данным. Ключевое свойство cmov/csel в том, что они не спекулируют: результат нельзя использовать, пока не готовы оба входа и условие. Значит, операция ложится в критический путь по задержке.

Практические правила, которые почти всегда выполняются:

1. Не оптимизируйте предсказуемое. Ветка, которая в 99 % случаев идёт одинаково, бесплатна; замена её на cmov только удлинит критический путь.
2. Бесветочный код считает обе стороны. Если одна сторона дорогая (обращение в память, вызов, деление), выигрыш съедается. Отдельно: обе стороны обязаны быть безопасными — разыменовать указатель «на всякий случай» нельзя.
3. Лучше устранить неопределённость, чем ветку. Сортировка, группировка, разделение разнородных элементов по отдельным контейнерам делают ветки предсказуемыми — и попутно улучшают локальность (Кэш и локальность).
4. Выносите инвариантные условия из циклов. Проверка флага, не меняющегося по ходу цикла, должна стать двумя специализированными циклами, а не веткой внутри одного.
5. Меряйте после каждого шага. Бесветочные варианты особенно легко «улучшают» микробенч и ухудшают настоящую нагрузку — там другие данные и другое давление на таблицы.

Отдельный крупный случай — векторизация. SIMD по своей природе бесветочна: элементы обрабатываются под маской, а не через условия (SIMD и векторные расширения). Часто правильный ход не «убрать одну ветку», а «переписать цикл так, чтобы он векторизовался».

Спекуляция шире, чем переходы

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

Предсказание зависимостей по памяти. Загрузка не знает, не пишет ли в тот же адрес более старая запись, чей адрес ещё не вычислен. Ждать все старые записи — потерять весь смысл внеочередного исполнения. Поэтому есть предсказатель: «эта загрузка обычно ни с кем не конфликтует, пускаем вперёд». Если конфликт всё же случится, загрузку и всё, что от неё зависит, откатывают. Симптом в профиле — дорогие загрузки в коде, где память формально не пересекается, но компилятор и железо этого не знают.

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

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

Общая формула ставки проста и стоит того, чтобы держать её в голове при любом проектном решении, не только в железе: спекуляция окупается, когда вероятность × выигрыш больше, чем (1 − вероятность) × цена отката, и когда откат вообще возможен.

Когда спекуляция становится дырой в безопасности

До 2018 года считалось, что спекуляция безопасна: неверно исполненные команды не меняют архитектурное состояние — регистры и память откатываются, будто ничего не было. Атаки Spectre и Meltdown показали, что архитектурное состояние — не всё состояние. Спекулятивное исполнение оставляет микроархитектурные следы: строки, подтянутые в кэш, обновлённые таблицы предсказателя, занятые буферы. Откат их не убирает, а измерить их можно временем.

Разновидностей несколько, и различать их полезно:

• Spectre v1 (обход проверки границ). Ровно сценарий на диаграмме: предсказатель обучен тем, что проверка обычно проходит, и код за проверкой исполняется спекулятивно с недопустимым индексом. Защита — не давать спекуляции добраться до данных: барьер спекуляции, либо маскирование индекса так, чтобы даже спекулятивно он оставался в границах.
• Spectre v2 (внедрение цели перехода). Таблицы предсказателя — общий ресурс, и если они не разделены между контекстами, посторонний код может обучить их так, чтобы косвенный переход в жертве спекулятивно ушёл по выбранному адресу. Отсюда программные обходы вроде retpoline (косвенный переход подменяется конструкцией, чья спекуляция заведомо безвредна) и аппаратные режимы изоляции предсказателя между привилегиями и потоками.
• Meltdown — родственная, но другая проблема: там спекуляция позволяла прочитать данные до проверки прав доступа. Лечится в основном разделением таблиц страниц ядра и пользователя, а в новых ядрах — исправлением самой проверки.

Отсюда два инженерных вывода. Первый: у некоторых защит есть цена, и она измерима — часть обходов ограничивает именно спекуляцию, то есть напрямую отнимает то, ради чего всё это строилось; наибольший эффект — на нагрузках с частыми переходами в ядро. Второй, более общий: изоляция должна учитывать разделяемое микроархитектурное состояние. Со стороны операционной системы это разобрано в главе про изоляцию (Безопасность и изоляция), а модель угроз в целом — в треке безопасности (Моделирование угроз).

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

Разные классы устройств — разные ответы

Предсказатель есть не везде, и это не «недоделка», а осознанный выбор.

Микроконтроллеры. У ядра класса Cortex-M0/M3 конвейер из трёх стадий, штраф ошибки — единицы тактов, площадь дорога, а энергия ещё дороже. Полноценный предсказатель здесь не окупается: он занял бы заметную долю кристалла ради выигрыша в проценты. Более крупные ядра того же семейства уже содержат небольшие предсказательные структуры — граница проходит по глубине конвейера и целевой частоте (Основы аппаратуры).

Жёсткое реальное время. Здесь спекуляция мешает не производительности, а анализу: оценка худшего времени исполнения (WCET) должна быть доказуемой, а предсказатель делает время зависимым от истории. Поэтому в системах с сертификацией динамические механизмы либо отключают, либо анализируют с пессимистичными допущениями — платят средней производительностью за предсказуемость (Прерывания и тайминги).

Графические процессоры. Классического предсказания переходов там нет: модель исполнения другая. Группа потоков идёт одной командой, и расхождение путей внутри группы (дивергенция) обрабатывается маской — обе ветви исполняются по очереди, ненужные потоки простаивают. Цена ветвления есть, но она устроена иначе, и оптимизируют её тоже иначе (Ускорители).

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

Инженерные компромиссы предсказателя

Полезно смотреть на предсказатель как на кэш, потому что компромиссы у него кэшевые.

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

Точность против энергии. Каждый лишний бит истории и каждая лишняя таблица — это чтение, запись и обновление на каждом переходе, то есть постоянно. При жёстком бюджете мощности выбор смещается в сторону схем попроще (Мощность и пределы).

Разделение состояния против ёмкости. Общие таблицы между потоками SMT и между привилегиями эффективнее по площади и хуже по изоляции — ровно то, за что пришлось платить после 2018 года.

Холодный старт. Предсказатель надо «прогреть». Программы с короткими фазами, частыми переключениями контекста, обилием редко исполняемого кода получают худшую точность, чем обещают бенчмарки с длинными циклами. Это же делает опасными микробенчмарки: они меряют предсказатель в идеальных для него условиях.

Мини-итог

• Предсказание переходов — не оптимизация, а условие работы конвейера: без него глубокий конвейер простаивает на каждой пятой команде.
• Задач три: заметить переход (BTB), угадать направление (счётчики и история) и угадать цель (BTB, RAS, предсказатель косвенных целей). Ломаются они по-разному.
• Эволюция шла от двухбитного счётчика к схемам с историей (gshare), затем к турнирным, TAGE и перцептронным. Главные враги — интерференция в таблицах и разная нужная длина истории.
• Штраф ошибки на большом внеочередном ядре 2010–2020-х — порядка 15–20 тактов, а с учётом ширины ядра это порядка сотни потерянных слотов исполнения. На микроконтроллере — единицы тактов, и там предсказателя может не быть вовсе.
• Меряйте, а не гадайте: branch-misses, MPKI, категория «плохая спекуляция» в top-down.
• Бесветочный код — обмен неопределённости на зависимость по данным. Помогает на непредсказуемых ветках, вредит на предсказуемых.
• Сильнее любых микроприёмов работает устранение самой неопределённости: сортировка и группировка данных, специализация горячего пути, вынос инвариантных условий, сборка с профилем.
• Спекуляция — общий принцип ядра (память, предвыборка), и у него есть цена в безопасности: откат архитектурного состояния не стирает микроархитектурные следы.

Источники

• T.-Y. Yeh, Y. N. Patt. Two-Level Adaptive Training Branch Prediction. MICRO, 1991 — работа, с которой начались предсказатели с историей.
• S. McFarling. Combining Branch Predictors. WRL Technical Note TN-36, 1993 — PDF, первоисточник gshare.
• R. E. Kessler. The Alpha 21264 Microprocessor. IEEE Micro, 1999 — турнирная схема в металле.
• D. Jiménez, C. Lin. Dynamic Branch Prediction with Perceptrons. HPCA, 2001 — PDF.
• A. Seznec, P. Michaud. A case for (partially) TAgged GEometric history length branch prediction. JILP, 2006 — PDF.
• Championship Branch Prediction — jilp.org/cbp2016, площадка, где схемы сравнивают при фиксированном бюджете памяти.
• E. Rohou, B. Narasimha Swamy, A. Seznec. Branch Prediction and the Performance of Interpreters — Don’t Trust Folklore. CGO, 2015 — PDF.
• A. Yasin. A Top-Down Method for Performance Analysis and Counters Architecture. ISPASS, 2014 — откуда взялась категория «плохая спекуляция».
• P. Kocher et al. Spectre Attacks: Exploiting Speculative Execution, 2018 — spectreattack.com.
• M. Lipp et al. Meltdown: Reading Kernel Memory from User Space, 2018 — meltdownattack.com.
• Документация ядра Linux по аппаратным уязвимостям — kernel.org.
• A. Fog. The Microarchitecture of Intel, AMD and VIA CPUs — agner.org, подробности по конкретным поколениям, включая структуры предсказания.
• J. Hennessy, D. Patterson. Computer Architecture: A Quantitative Approach — глава про использование параллелизма на уровне команд, базовый разбор всей темы.
• Stack Overflow: Why is processing a sorted array faster than processing an unsorted array? — stackoverflow.com, самая известная иллюстрация темы.

Что дальше

Мы всю главу исходили из того, что нужные команды и данные лежат рядом и достаются быстро. Это неправда: обращение в память — единственная операция, которая может стоить дороже ошибочного предсказания на порядок, и вся конструкция из кэшей, буферов и предвыборки существует ровно для того, чтобы это скрыть. Следующая глава разбирает подсистему памяти со стороны железа: уровни кэша и их организацию, когерентность между ядрами и то, чем занят контроллер памяти.

Подсистема памяти: кэши, когерентность, контроллер