Почему обработка отсортированного массива выполняется быстрее, чем неотсортированного?

Краткий ответ

Разница в скорости связана с предсказанием переходов (branch prediction) — механизмом современных процессоров, который пытается угадать, какая ветвь условного оператора будет выполнена. В отсортированном массиве условие data[i] >= 128 сначала ложно (все элементы < 128), а затем истинно (все элементы >= 128) — такое поведение легко предсказать. В неотсортированном массиве истинность условия меняется случайным образом, что приводит к частым ошибкам предсказания и сбросу конвейера.

Подробное объяснение

Современные процессоры используют конвейерную архитектуру: выполнение инструкции разбивается на несколько этапов (выборка, декодирование, выполнение, запись результата). Чтобы конвейер не простаивал, процессор начинает выполнять следующие инструкции ещё до завершения текущих. Но когда встречается условный переход (например, if), процессор не знает, какая ветка будет выполнена, пока не закончится вычисление условия. Поэтому он предсказывает результат и начинает выполнять соответствующую ветку. Если предсказание неверно — конвейер очищается, и процессор теряет 10–20 тактов.

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

• Сначала все элементы меньше 128 — предсказание "ложь" всегда верно.
• Затем все элементы больше или равны 128 — предсказание "истина" всегда верно.
• Единственная ошибка происходит на границе перехода.

Для неотсортированного массива:

• Каждый элемент может быть как меньше, так и больше 128 с вероятностью ~50%.
• Процессор ошибается примерно в каждом втором случае, теряя такты на сброс конвейера.

Как это проверить

Можно заменить условие на безусловное вычисление, которое не требует ветвления. Например, используя тернарный оператор или битовые маски:

// Вместо if
for (int i = 0; i < SIZE; ++i) {
    sum += (data[i] >= 128) * data[i];  // умножение на 0 или 1
}

Или через std::accumulate с лямбдой, но компилятор может оптимизировать это в условное перемещение (conditional move):

#include <numeric>
sum = std::accumulate(data.begin(), data.end(), 0, 
    [](int acc, int x) { return acc + (x >= 128 ? x : 0); });

Такие подходы устраняют ветвление и делают скорость одинаковой для обоих массивов.

Что делать в реальных проектах

• Не пытайтесь "бороться" с предсказанием без профилирования. Для большинства приложений разница незаметна.
• Используйте профилировщики (например, perf, Valgrind) для поиска реальных узких мест.
• Рассмотрите сортировку данных перед обработкой, если порядок не важен и данные стабильны.
• Применяйте безусловные вычисления только в критических циклах с высокой частотой ошибок предсказания.
• Помните про читаемость кода: преждевременная оптимизация — корень всех зол.

Дополнительные факты

• Современные процессоры (Intel Haswell и новее) имеют сложные предсказатели с точностью до 95% для типичного кода.
• В C++ можно использовать __builtin_expect (GCC/Clang) или [[likely]]/[[unlikely]] (C++20) для подсказок компилятору.
• Векторизация (SIMD) также может устранять ветвления, но требует специальных инструкций.

for (int i = 0; i < SIZE; ++i) {
    int mask = (data[i] - 128) >> 31;  // -1 если <128, 0 если >=128
    sum += data[i] & ~mask;            // обнуляем элемент, если mask = -1
}