Вы когда-нибудь задумывались, почему обработка отсортированного массива чисел происходит в разы быстрее, чем случайного, даже если логика одна и та же?
Всё дело в конвейере (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
📲 Мы в MAX
👉 @rust_lib