Передбачення переходів (branch prediction)

Коротко: Передбачення переходів вгадує, яким шляхом піде програма в розгалуженні, щоб конвеєр процесора не чекав на результат.

Докладніше: Сучасні процесори вибирають і запускають команди задовго до того, як відомий результат умови. Якщо передбачення правильне, виконання йде без пауз. Якщо хибне, робота відкидається, що коштує приблизно 10–20 тактів.

Подробиці

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

Див. також: будова CPU