Предсказание переходов (branch prediction)

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

Подробнее: Современные процессоры выбирают и запускают команды задолго до того, как известен результат условия. Если предсказание верно, выполнение идёт без пауз. Если неверно, работа отбрасывается, что стоит примерно 10–20 тактов.

Подробности

• Простейшая форма: Счётчик на каждый переход запоминает, был ли он в прошлый раз выполнен.
• Лучше: Предикторы на основе истории используют результаты последних переходов как шаблон. Современные процессоры попадают более чем в 95 % переходов.
• Видимый эффект: Суммирование значений больше 128 в массиве быстрее, если массив отсортирован, потому что шаблон переходов становится предсказуемым.
• Контрмеры в коде: Безветвистые формулировки (условные присваивания), отсортированные данные, вынос редких случаев из горячего цикла.
• Безопасность: Спекулятивное выполнение привело к уязвимостям вроде Spectre, потребовавшим программных мер и микрокода.
• Контекст: Часть спекуляции наряду с внеочередным выполнением.

См. также: устройство CPU