Por que um array ordenado é processado mais rápido? Explicação com Java

Introdução: o paradoxo que explodiu no Stack Overflow

Imagine: você escreve um loop simples em Java que soma os elementos de um array dependendo de uma condição (por exemplo, se o número for maior que 128). Você executa o código em um array ordenado — e ele é executado 2 a 3 vezes mais rápido do que em um array não ordenado. Parece mágica? Na verdade, não é mágica, mas sim branch prediction (previsão de desvios) — uma das principais características dos processadores modernos.

A pergunta «Why is conditional processing of a sorted array faster than of an unsorted array?» recebeu mais de 30 mil votos no Stack Overflow e se tornou um clássico para o estudo de otimização de baixo nível. Neste artigo, não apenas analisaremos a teoria, mas também escreveremos código real em Java para ver o efeito com nossos próprios olhos. E o mais importante: você aprenderá como usar esse conhecimento na prática.

Se você quer entender mais profundamente como funciona a otimização de código em Java e por que o branch prediction pode tanto acelerar quanto desacelerar seu programa — você está no lugar certo.

1. Experimento: o código que mostra tudo

Vamos começar com uma aplicação Java simples. Criaremos dois arrays: um ordenado e outro aleatório. Em seguida, percorreremos cada um e somaremos os elementos maiores que um valor limite (por exemplo, 128). Mediremos o tempo de execução.

import java.util.Arrays;\nimport java.util.Random;\n\npublic class BranchPredictionDemo {\n    private static final int SIZE = 100_000;\n    private static final int THRESHOLD = 128;\n\n    public static void main(String[] args) {\n        // Criando um array não ordenado\n        int[] unsorted = new int[SIZE];\n        Random rand = new Random();\n        for (int i = 0; i < SIZE; i++) {\n            unsorted[i] = rand.nextInt(256); // 0..255\n        }\n\n        // Criando um array ordenado (copiando e ordenando)\n        int[] sorted = unsorted.clone();\n        Arrays.sort(sorted);\n\n        // Medindo o tempo para o não ordenado\n        long start = System.nanoTime();\n        long sumUnsorted = processArray(unsorted);\n        long end = System.nanoTime();\n        System.out.println("Não ordenado: " + (end - start) / 1_000_000 + " ms, soma = " + sumUnsorted);\n\n        // Medindo o tempo para o ordenado\n        start = System.nanoTime();\n        long sumSorted = processArray(sorted);\n        end = System.nanoTime();\n        System.out.println("Ordenado: " + (end - start) / 1_000_000 + " ms, soma = " + sumSorted);\n    }\n\n    private static long processArray(int[] arr) {\n        long sum = 0;\n        for (int i = 0; i < arr.length; i++) {\n            if (arr[i] >= THRESHOLD) {\n                sum += arr[i];\n            }\n        }\n        return sum;\n    }\n}\n

Resultados no meu notebook (Intel i7, Java 17):

\n
• Array não ordenado: ~22 ms
\n
• Array ordenado: ~8 ms
\n

Uma diferença de quase 3 vezes! Por quê? Afinal, a quantidade de operações é a mesma. A resposta está em como o processador lida com a condição if (arr[i] >= THRESHOLD).

2. Branch Prediction: o cérebro do processador

Os processadores modernos usam uma arquitetura pipeline — eles preveem qual caminho de execução (ramo) será escolhido e começam a executar as instruções antecipadamente. Se a previsão estiver correta — tudo funciona perfeitamente. Se estiver errada — o pipeline é descartado e o processador gasta ciclos para limpeza.

Em um array ordenado, os valores primeiro são menores que 128 por um longo tempo, e depois são maiores. O processador "aprende" rapidamente: se as últimas 1000 vezes foram false, então a próxima provavelmente também será false. A previsão funciona quase perfeitamente.

Em um array não ordenado, os valores saltam aleatoriamente acima e abaixo do limite. O processador erra em cerca de 50% dos casos, le