Модуль 12

Prefetch та control flow

Ось урок, створений у стилі CS50: енергійно, з аналогіями та акцентом на "навіщо це нам".

🎓 Урок: Prefetch та Control Flow (Коли процесор намагається вгадати майбутнє)

Привіт, друзі! Це CS50 (умовно 😉), і сьогодні ми зазирнемо туди, де живе справжня магія швидкості — всередину процесора.

1. 🔥 Вступ: Проблема «повільного клієнта»

Уявіть, що ви працюєте в кав’ярні Starbucks у найгарячіший час ранку. Ви — бариста. Ваша мета — видавати каву максимально швидко.

Ви працюєте як конвеєр: поки одна кава наливається, ви вже берете наступний стаканчик, пишете ім'я і грієте молоко. Ви випереджаєте події (prefetching). Ви не чекаєте, поки попередній клієнт піде, щоб почати обслуговувати наступного.

Але тут підходить клієнт, ви берете стаканчик і питаєте: "Вам лате чи еспресо?" А він зависає: "Емм... ну я не знаааю... може, чай?"

🛑 СТОП. Увесь ваш конвеєр зупинився. Ви тримаєте пустий стаканчик і не знаєте, що в нього наливати. Ви не можете робити роботу наперед.

У програмуванні це називається Control Flow Hazard (конфлікт керування). * Prefetch (попереднє завантаження) — це ваше бажання підготувати все заздалегідь. * Control Flow (потік керування) — це той самий if / else, який змушує вас чекати.

Риторичне питання: Чому ваш код може працювати повільно, навіть якщо ви написали ідеальний алгоритм? Тому що іноді процесор (як той бариста) змушений чекати, поки ваш код "визначиться із замовленням".

Сьогодні ми розберемося, як писати код так, щоб процесор ніколи не гальмував.

2. 🧠 Теоретична база (Що під капотом)

Давайте відійдемо від кави до "заліза".

Сучасні процесори працюють за принципом Instruction Pipeline (конвеєр команд). Щоб виконати одну команду, процесору треба зробити кілька кроків: 1. Fetch — завантажити команду з пам'яті. 2. Decode — зрозуміти, що це за команда. 3. Execute — виконати її. 4. Write Back — записати результат.

Щоб не гаяти час, процесор робить Prefetch: поки одна команда виконується (крок 3), він вже завантажує наступну (крок 1).

У чому проблема?

Проблема в інструкціях переходу (if, цикли for/while, виклики функцій). Коли процесор бачить:

if (x > 0) {
    // Шлях А
} else {
    // Шлях Б
}

Він ще не обчислив x > 0, але йому вже треба завантажувати наступні команди в конвеєр. Які завантажувати? Зі Шляху А чи Шляху Б?

Як це вирішує процесор?

Він використовує Branch Prediction (передбачення переходів). Він буквально вгадує. * Якщо вгадав — супер, програма летить. * Якщо не вгадав — він мусить викинути все, що навантажив (Pipeline Flush), і почати заново з правильної гілки. Це дуже дорого (у тактах процесора).

❗️ Запам'ятайте головне: Процесор любить лінійний код. Він ненавидить непередбачувані if-и всередині циклів.

3. 🧪 Приклади: Сортування, яке пришвидшує... додавання?

Давайте подивимось на класичний приклад, який розриває шаблон новачкам.

Задача:

Ми маємо масив випадкових чисел. Ми хочемо порахувати суму всіх чисел, які більші за 128.

Очікування: Чи залежить швидкість сумування від того, чи відсортований масив? Логічно, що ні. Ми ж просто додаємо числа, операцій if і + однакова кількість.

Реальність: Давайте перевіримо. (Приклад мовою C++, бо тут ми ближче до заліза).

#include <algorithm>
#include <ctime>
#include <iostream>
#include <vector>

int main() {
    // 1. Генеруємо 32k випадкових чисел (0-255)
    const int SIZE = 32768;
    std::vector<int> data(SIZE);
    for (int c = 0; c < SIZE; ++c)
        data[c] = std::rand() % 256;

    // !!! МАГІЧНИЙ РЯДОК !!!
    // Якщо його розкоментувати, код працюватиме ВТРИЧІ швидше
    // std::sort(data.begin(), data.end());

    // 2. Тестуємо цикл
    long long sum = 0;
    clock_t start = clock();

    // Робимо багато ітерацій, щоб помітити різницю
    for (int i = 0; i < 100000; ++i) {
        for (int c = 0; c < SIZE; ++c) {
            // Ось наш Control Flow
            if (data[c] >= 128) {
                sum += data[c];
            }
        }
    }

    double duration = (double)(clock() - start) / CLOCKS_PER_SEC;
    std::cout << "Час виконання: " << duration << " сек" << std::endl;
    std::cout << "Сума: " << sum << std::endl;
}

Чому так відбувається?

  1. Без сортування: Дані йдуть хаотично: 10, 200, 5, 150.... Умова if (data[c] >= 128) спрацьовує випадково (True, False, False, True...). Процесор не може передбачити патерн. Він часто помиляється -> постійні збої конвеєра -> повільно.
  2. Із сортуванням: Дані йдуть так: 0, 5, 10... 128, 130, 200.... Спочатку умова завжди False, потім завжди True. Процесор бачить патерн, ідеально робить Prefetch інструкцій -> дуже швидко.

4. 🛠 Практична частина

Час попрацювати руками.

Завдання 1: Відчуй різницю Скопіюйте код вище. Запустіть його без std::sort, а потім з ним. Запишіть різницю в часі. (Зазвичай різниця у 3-6 разів!).

Завдання 2: Branchless Programming (Програмування без розгалужень) Спробуйте позбутися if у циклі. Підказка: Використовуйте бітові операції. Рішення: Замість if (data[c] >= 128) sum += data[c]; Напишіть:

int t = (data[c] - 128) >> 31; // Буде маска 0 або -1 (залежно від знаку)
sum += ~t & data[c];

Питання: Чи швидше це працює на несортованому масиві, ніж версія з if?

Завдання 3: Підказка компілятору У C++ (GCC/Clang) є макроси __builtin_expect. Спробуйте змінити умову на: if (__builtin_expect(data[c] >= 128, 0)) Ми кажемо процесору: "Швидше за все, ця умова буде хибною". Перевірте, як це вплине на швидкість, якщо масив складається переважно з маленьких чисел.

Завдання 4: Міні-кейс У вас є масив об'єктів User. У кожного є поле isActive (bool). Вам треба обробити тільки активних юзерів. Що краще для продуктивності: 1. Зберігати всіх у купі і перевіряти if (user.isActive). 2. Тримати два окремі масиви: activeUsers та inactiveUsers. Обгрунтуйте відповідь, спираючись на тему уроку.

5. 💡 Мислення як у розробника

Як ця тема відрізняє джуна від сеньйора?

❌ Помилка новачка: Думає тільки про складність алгоритму ($O(n)$, $O(\log n)$). "Я написав один цикл, чому воно гальмує?"

✅ Думка профі: Розуміє, як дані лежать у пам'яті і як тече потік виконання. "Ага, тут у мене випадкові стрибки пам'яті (cache miss) і непередбачувані умови (branch misprediction). Треба спробувати відсортувати дані або використати техніку Data Oriented Design".

Поради з практики: 1. Передбачуваність — друг швидкості. Якщо ви можете впорядкувати дані перед обробкою — зробіть це. 2. Уникайте розгалужень у "гарячих" циклах. Якщо цикл крутиться мільйони разів, кожен if — це потенційне гальмо. 3. Не оптимізуйте передчасно. Сучасні процесори дуже розумні. Робіть такі трюки тільки там, де профайлер показав "вузьке місце".

6. 🧩 Підсумок

Отже, що ми сьогодні зрозуміли: 1. Процесор — це конвеєр. Він хоче знати наперед, що робити далі. 2. Prefetch — це коли процесор бере інструкції "із запасом". 3. Control Flow (if/else) — це ворог Prefetch-а, якщо він непередбачуваний. 4. Сортування даних може прискорити код не тому, що алгоритм кращий, а тому що процесору легше вгадувати.

Тепер ви вмієте: Бачити приховане гальмо у простому коді та розуміти, чому "лінійний" код завжди виграє у "розгалуженого".

🔜 У наступній серії: Ми говорили про те, як процесор читає команди. Але що, якщо дані лежать далеко? Наступного разу розберемо Кеш процесора (L1, L2, L3) і чому ваш масив насправді "дірявий".

Це був CS50. (Стук по коду). Побачимось!

← До списку уроків Наступний урок →