🔮 Ты не пройдешь: Магия предсказателя ветвлений

Вы когда-нибудь задумывались, почему обработка отсортированного массива чисел происходит в разы быстрее, чем случайного, даже если логика одна и та же?

Всё дело в конвейере (pipeline). Процессор выполняет инструкции не по одной, а потоком: пока одна декодируется, другая уже выполняется. Но тут появляется if (ветвление).

Процессор не знает, пойдет код в then или в else, пока не вычислит условие. Но ждать он не может - конвейер встанет. Поэтому он угадывает.

• Угадал? Выполнение продолжается без задержек.

• Не угадал? Происходит Pipeline Flush. Процессор выбрасывает все инструкции, которые успел "набрать" по неверному пути, и начинает заново с правильного адреса. Это огромная потеря тактов (10-20 циклов CPU).

Пример на Rust:

// Если data отсортирован: T T T T T F F F F F (паттерн ясен)
// Если data случайный: T F T T F F T F (паттерн непредсказуем)
for &x in &data {
    if x > 128 {
        sum += x;
    }
}

На случайных данных BPU ошибается в 50% случаев. На сортированных почти никогда.

Вывод: Чем предсказуемее ваши данные, тем быстрее работает ваш код. Иногда data.sort() перед обработкой окупается с лихвой.

#rust #cpu #lowlevel #performance #branch_prediction

👉 @rust_lib