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

Всё дело в предсказании переходов (branch prediction)

Причина этого удивительного эффекта кроется не в Java, а в архитектуре процессора. Чтобы понять, что происходит, нужно заглянуть на уровень ниже — в то, как CPU выполняет условные переходы (if-else).

Современные процессоры используют конвейерную архитектуру (pipelining). Представьте себе сборочную линию на заводе: вместо того, чтобы выполнять одну инструкцию целиком, процессор разбивает её на этапы (выборка, декодирование, выполнение, запись результата) и обрабатывает несколько инструкций одновременно. Проблема возникает, когда встречается условный переход: процессор не знает, какая ветка кода будет выполнена, пока не завершится предыдущая инструкция. Ждать — значит терять такты, что катастрофически снижает производительность.

Для решения этой проблемы процессоры используют предсказание переходов (branch prediction). CPU пытается угадать, какая ветка if-else будет выбрана, и начинает выполнять инструкции из предсказанной ветки заранее. Если предсказание верно — конвейер работает без простоев. Если ошибка — всё, что было выполнено ошибочно, отбрасывается, и конвейер запускается заново с правильной ветки. Это называется штрафом за неправильное предсказание (branch misprediction penalty).

Теперь вернёмся к вашему примеру:

if (arr[i] > 128) {
    sum += arr[i];
}

В отсортированном массиве сначала идут все числа ≤ 128, а потом все числа > 128. Это значит, что предсказатель переходов очень быстро учится: пока мы в первой половине — предсказывает "ветка не выполнится", а во второй — "ветка выполнится". Переход происходит всего один раз (на границе между частями), и предсказатель ошибается только один раз. Отсюда высокая производительность.

В неотсортированном массиве числа случайно чередуются: то меньше 128, то больше. Предсказатель не может угадать закономерность и ошибается примерно в 50% случаев. Каждая ошибка — это потеря 10-20 тактов процессора на сброс конвейера. Суммарно это даёт огромную разницу во времени выполнения.

Как это проявляется в Java?

Java-код компилируется в байт-код, который затем JIT-компилятором (Just-In-Time) превращается в машинный код. JIT-компилятор может применять оптимизации, но базовое поведение остаётся тем же: условные переходы в машинном коде всё равно подвержены предсказанию.

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

// Пример с порогом 0 — почти все элементы проходят условие
public static int processArrayThreshold0(int[] arr) {
    int sum = 0;
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] > 0) {  // почти всегда true
            sum += arr[i];
        }
    }
    return sum;
}

// Пример с порогом 255 — почти ни один элемент не проходит
public static int processArrayThreshold255(int[] arr) {
    int sum = 0;
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] > 255) {  // почти всегда false
            sum += arr[i];
        }
    }
    return sum;
}

В обоих этих случаях разница между отсортированным и неотсортированным массивом будет минимальной, потому что предсказатель почти всегда прав (99%+ точность) независимо от порядка данных.

Как избежать этой проблемы?

• Сортировка — если данные можно отсортировать без больших накладных расходов, это самый простой способ.
• Линейная обработка без условий — используйте тернарный оператор или битовые операции, которые могут быть скомпилированы в условные перемещения (conditional move), не требующие предсказания.
• Таблицы поиска (lookup tables) — предварительно вычислите результат для всех возможных значений.

// Пример с таблицей поиска (если диапазон значений мал)
public static int processArrayLookup(int[] arr) {
    int sum = 0;
    int[] lookup = new int[256];
    for (int i = 0; i < 256; i++) {
        lookup[i] = (i > 128) ? i : 0;
    }
    for (int i = 0; i < arr.length; i++) {
        sum += lookup[arr[i]];
    }
    return sum;
}

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

В итоге: разница в производительности — это не баг Java, а фундаментальная особенность работы современных процессоров. Понимание этого помогает писать более эффективный код, особенно для критичных к производительности участков.