Почему сортированный массив в C++ обрабатывается быстрее? Секрет Branch Prediction

Вступление: Один из самых неожиданных вопросов в мире C++

Представьте ситуацию: вы пишете простой цикл на C++, который суммирует элементы большого массива, но только те, которые больше определённого порога. Вы запускаете код, он работает... нормально. Потом вы решаете предварительно отсортировать массив и запускаете снова. И вдруг замечаете, что код выполняется в 2-3 раза быстрее! В чём подвох? Магия компилятора? Ошибка в бенчмарке?

Этот вопрос, заданный на Stack Overflow более десяти лет назад, собрал тысячи просмотров и до сих пор вызывает жаркие споры. Сегодня мы на PythonLib разберём его досконально, с реальными примерами на C++ и глубоким погружением в архитектуру современных процессоров. Вы узнаете не только почему это происходит, но и как использовать этот эффект для ускорения своего кода.

1. Воспроизводим феномен: код, который удивляет

Давайте напишем простую программу, которая ярко демонстрирует этот эффект. Нам понадобится массив из 100 000 целых чисел. Мы заполним его случайными значениями, затем замерим время суммирования всех элементов, превышающих 128.

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <random>

int main() {
    const int SIZE = 100000;
    const int THRESHOLD = 128;
    
    // Создаём неотсортированный массив
    std::vector<int> data(SIZE);
    std::mt19937 rng(42);
    std::uniform_int_distribution<int> dist(0, 255);
    for (auto& val : data) {
        val = dist(rng);
    }

    // Суммируем для неотсортированного массива
    auto start = std::chrono::high_resolution_clock::now();
    long long sum_unsorted = 0;
    for (int i = 0; i < SIZE; ++i) {
        if (data[i] >= THRESHOLD) {
            sum_unsorted += data[i];
        }
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto time_unsorted = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
    std::cout << "Неотсортированный массив: " << time_unsorted << " мкс, сумма = " << sum_unsorted << std::endl;

    // Сортируем массив
    std::sort(data.begin(), data.end());

    // Суммируем для отсортированного массива
    start = std::chrono::high_resolution_clock::now();
    long long sum_sorted = 0;
    for (int i = 0; i < SIZE; ++i) {
        if (data[i] >= THRESHOLD) {
            sum_sorted += data[i];
        }
    }
    end = std::chrono::high_resolution_clock::now();
    auto time_sorted = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
    std::cout << "Отсортированный массив: " << time_sorted << " мкс, сумма = " << sum_sorted << std::endl;

    std::cout << "Ускорение: " << (double)time_unsorted / time_sorted << "x" << std::endl;
    return 0;
}

При компиляции без оптимизаций (флаг -O0) разница будет небольшой, но если включить -O2 или -O3 в GCC/Clang, вы получите впечатляющий результат: отсортированный массив обрабатывается в 3-6 раз быстрее.

2. Анатомия процессора: откуда берётся разница?

Ключ к разгадке — это механизм, который называется Branch Prediction (предсказание ветвлений). Современные процессоры — это конвейерные машины. Они выполняют инструкции не по одной, а разбивают их на этапы (выборка, декодирование, выполнение, запись результата). Чтобы конвейер не простаивал, процессор пытается угадать, какая ветка кода (if или else) будет выполнена следующей, и начинает загружать инструкции заранее.

В нашем примере условие if (data[i] >= THRESHOLD) — это точка ветвления. Для отсортированного массива предсказание работает идеально:

• Сначала все элементы меньше порога — процессор быстро учится предсказывать "не брать".
• После порога все элементы больше или равны — процессор переключается на "брать".
• Штраф за неправильное предсказание возникает всего один раз — при переходе через порог.

Для неотсортированного массива ситуация обратная: каждое значение может быть как больше, так и меньше порога. Процессор постоянно ошибается, сбрасывает конвейер и тратит драгоценные такты на перезагрузку. При вероятности 50% на каждое условие, каждая вторая ветка предсказывается неверно.

3. Визуализация: как работает конвейер

Давайте представим конвейер из 5 этапов. Для простоты возьмём идеальный случай (отсортированный массив) и худший (случайный).

Идеальный случай (отсортированный массив):

Такт 1: IF1  (выборка инструкции 1)
Такт 2: ID1  IF2 (декодирование 1, выборка 2)
Такт 3: EX1  ID2 IF3 (выполнение 1, декодирование 2, выборка 3)
Такт 4: MEM1 EX2 ID3 IF4 (память 1, выполнение 2, декодирование 3, выборка 4)
Такт 5: WB1  MEM2 EX3 ID4 IF5 (запись 1, память 2, выполнение 3, декодирование 4, выборка 5)
... конвейер заполнен, каждые такт завершается одна инструкция

Плохой случай (неотсортированный массив):

Такт 1: IF1
Такт 2: ID1  IF2
Такт 3: EX1  ID2 IF3
Такт 4: MEM1 EX2 ID3 IF4 (тут выясняется, что предсказание было неверным!)
Такт 5: WB1  MEM2 EX3 ID4 (конвейер сбрасывается, начинается загрузка правильной ветки)
Такт 6: IF_correct
Такт 7: ID_correct
Такт 8: EX_correct
Такт 9: MEM_correct
Такт 10: WB_correct
... теряем 5 тактов на каждую ошибку предсказания

В реальных процессорах (Intel Core i7, AMD Ryzen) конвейер может содержать 14-19 этапов, а штраф за неправильное предсказание достигает 20-30 тактов. Умножив это на