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

Ключевая причина: предсказание ветвлений (Branch Prediction)

Вы столкнулись с классическим эффектом, который называется branch prediction (предсказание ветвлений). Это не особенность Java или JVM, а фундаментальное свойство современных процессоров. Давайте разберем по порядку.

Как работает процессор с условными переходами

Когда процессор встречает if (arr[i] > 128), он не знает, какая ветка будет выбрана (true или false), пока не вычислит условие. Но современные процессоры используют конвейерную архитектуру (pipeline) — они начинают выполнять следующие инструкции, не дожидаясь завершения текущей. Если процессор угадает ветвление правильно — всё отлично. Если ошибется — нужно очистить конвейер (flush pipeline) и начать заново, что стоит ~10-20 тактов процессора.

Поведение на отсортированном массиве

В отсортированном массиве данные идут так: сначала все значения ≤ 128, потом все > 128. Поэтому:

• Первая половина итераций: условие false (стабильно)
• Один раз: переход от false к true
• Вторая половина: условие true (стабильно)

Процессор быстро "учится" этому паттерну и ошибается только 1 раз за весь цикл. Эффективность предсказания — ~99.99%.

Поведение на неотсортированном массиве

В случайном массиве условие arr[i] > 128 истинно примерно в 50% случаев, причем паттерн абсолютно случайный. Процессор не может предсказать, какое значение будет следующим. Каждый раз, когда он ошибается (~50% случаев), происходит сброс конвейера. Это и вызывает замедление в 2-3 раза.

Демонстрация на Java

Вы можете проверить это, заменив условие на битовую операцию, которая не требует ветвления:

private static long processArrayBitwise(int[] arr) {
    long sum = 0;
    for (int i = 0; i < arr.length; i++) {
        // (arr[i] & 128) даст 0 или 128, сдвиг выделяет знаковый бит
        int mask = (arr[i] & 128) >>> 7; // 0 или 1
        sum += arr[i] * mask; // если mask=0, добавляем 0
    }
    return sum;
}

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

Визуализация работы предсказателя

Представьте, что вы идете по коридору с множеством развилок. Если развилки чередуются предсказуемо (налево-направо-налево-направо), вы можете бежать, не сбавляя скорости. Если же направление каждой следующей развилки случайно — вам придется постоянно тормозить, возвращаться и менять направление.

Практические выводы

• Для критичных к производительности циклов старайтесь избегать ветвлений внутри горячих циклов
• Используйте lookup-таблицы, битовые маски или тернарные операторы (они тоже могут компилироваться в условные переходы, но не всегда)
• В Java 8+ Stream API может частично оптимизировать такие случаи
• Не пытайтесь сортировать данные только ради ускорения — затраты на сортировку O(n log n) обычно перевешивают выигрыш

// Использование IntPredicate и фильтрации
long sum = Arrays.stream(data)
    .filter(x -> x > 128)
    .sum();