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

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

Всё дело в конвейере (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

📦 Иллюзия объектов: Как мы морим процессор голодом

Представьте, что вы пишете симуляцию (или игру). По заветам ООП вы создаете сущность:

struct Particle {
    position: [f32; 3], // 12 байт
    velocity: [f32; 3], // 12 байт
    color: [u8; 4],     // 4 байта
    life: f32,          // 4 байта
    name: String,       // 24 байта
} 
// Итого: 56 байт

Затем складываете их в массив: Vec<Particle>. Это называется Array of Structs (AoS).

Теперь нам нужно в цикле обновить позицию (position += velocity). Нам нужны только 24 байта из 56. Но процессор так не умеет!

Процессор читает память из RAM в свой сверхбыстрый L1 кэш кусками по 64 байта (Cache Line).
Когда он берет первую частицу, он затягивает в кэш её position, velocity, а заодно color, life и половину name.

Результат:

1. Cache Miss: Больше половины кэша забито мусором (color, name), который в данном цикле не нужен. Процессору приходится постоянно бегать в медленную RAM за новыми частицами.

2. Bandwidth: Вы сжигаете пропускную способность памяти впустую.

Мы пишем код для людей, забывая, что исполнять его железу. Железо любит однородные, плотно упакованные данные. Как это исправить? Об этом в следующем посте.

#rust #architecture #dop #performance #cpu

👉 @rust_lib