Você é uma vítima do preditor de branches.
O que é a predição de branches?
Considere uma entroncamento ferroviário:
Imagem por Mecanismo, da Wikimedia Commons
Agora, para o meu argumento fazer algum sentido suponha que estamos no século XVIII, antes da invenção do rádio e de outros meios de comunicação.
Você é o operador do entroncamento e você nota que há um trem vindo. Você não faz ideia de para qual lado ele pretende ir e qual é o seu destino. Você então faz o trem parar, pergunta do maquinista o destino, ajusta a alavanca e libera o trem para partir.
O problema desde método é que o trem é um monstro pesadíssimo cheio de inercia e parar/partir é um processo que pode levar minutos.
Existe uma forma melhor? Sim! Chute para onde o trem vai sem perguntar.
- Se você acertar o trem vai continuar em frente e todos saem ganhando.
- Mas se você errar o trem precisará parar, regridir e partir.
Se você acertar sempre o trem nunca precisará parar.
Se você errar muito frequentemente o trem perderá tempo parando e regredindo. Mas isso é quase tão ruim quanto parar para perguntar.
Admito que a analogia pode não ser tão boa, afinal o trem poderia sinalizar a direção com uma bandeira ou algo do tipo. Mas em computadores não há como saber que direção o seu código tomará até o momento que a execução chegar até ele. Este é o preditor de branches.
Mas antes de mais nada, o que é uma branch?
Considere essa condicional, uma branch:

Para decidir se r += array[i]
será ou não executado deve-se primeiro ler o valor de array[i]
e verificar se ele é menor que 500
. O problema aqui é que processadores modernos podem executar multiplas instruções ao mesmo tempo desde que não haja dependencias entre elas. Para isso funcionar direito ele precisa saber quais são as próximas instruções, e esperar até que a condicional tenha se resolvido é subutilizar o poder computacional.
Mas processadores modernos são melhores que isso. Eles cegamente chutam e tomam um caminho antes do cálculo estar pronto. Quando a condicional estiver pronta se verifica:
- Se o chute foi certeiro, apenas continuar a executar.
- Se o chute estava errado, deve-se parar tudo que está sendo feito, desfazer o que foi executado erroneamente e continuar do ponto logo depois da condicional;
Se ele acertar sempre a execução nunca precisará parar.
Se ele errar muito frequentemente a execução perderá tempo parando e regredindo. Mas isso é quase tão ruim quanto parar para esperar a decisão.
O que os processadores fazem aqui é tentar identificar um padrão e seguir ele para aumentar as chances de obter um chute certeiro. O operador do entroncamento pode notar, por exemplo, que de manhã a maioria dos trens estão indo para um lado, enquanto que trens pintados de vermelho costumam seguir pelo outro caminho.
Quando sua lista não está ordenada a distribuição de valores será proximadamente randomica e uniforme. Sendo assim o resultado de array[i] < 500
é totalmente imprevisível. Isso resultará em cerca de 50% de erro no preditor.
Mas se sua lista está ordenada, acontecerá que para os primeiros valores de i
o resultado será sempre true
já que todos esses valores são baixos. O preditor aprenderá que a condição é sempre verdade e constante. No momento em que a execução passar de metade da array, o resultado começará a ser false
e o preditor vai errar por alguns ciclos até notar a mudança e passar a assumir que será sempre falso. Isso dá uma taxa de acerto quase total.
O truque é fazer com que todos os branches dentro de seções críticas sejam facilmente previsíveis, podendo lhe proporcionar bastante ganho de performance, mesmo ao custo de previamente ordenar seus dados.
Embora eu não indique escrever código assim a menos que seja realmente necessário, você pode escapar de depender do preditor escrevendo o mesmo código sem branch alguma:
if (array[i] < 500)
r += array[i];
int flag = (array[i] - 500) >> 31; // right shift em valores signed não é portável
r += flag & array[i]; // Se a flag for zero, some zero
Não há condicionais envolvidas aqui, apenas manipulações de bits. O primeiro problema é que o comportamento desse código não é imediatamente óbvil para quem o lê, diferente do original. O segundo, e talvez mais importante, é que isso só funciona se o right shift for implementado como um arithmetic shift, que implica que o sinal será preservado e fará toda a palavra ser 1
s.
Testando com o GCC 4.8.1, sem otimização:
- Randomico, com branch: 22.82s
- Ordenado, com branch: 8.483s
- Randomico, sem branch: 9.474s
- Ordenado, sem branch: 9.448s
Note que embora a ordem não faça mais nenhuma diferença, o resultado é mais lento do que quando o preditor estava em ação e acertando, pois temos mais operações para executar.
Mas e se ligarmos as otimizações?
Então os números do seu teste mudam um pouco:
- Randomico, com branch: 3.249s
- Ordenado, com branch: 3.242s
- Randomico, sem branch: 2.565s
- Ordenado, sem branch: 2.569s
Aqui o GCC é esperto o bastante para transformar a branch em um conditional move:
mov ecx, DWORD PTR [esi+edx*4] ; a = array[i]
cmp ecx, 499 ; c = a <= 499
lea ebx, [ecx+eax] ; t = r + a
cmovle eax, ebx ; if (c) r = t
A mágica aqui é que a última instrução não é um branch, é executada como apenas uma instrução e não impede o processador de começar a executar as instruções que vem em seguida, não há saltos para outras partes do código, é tudo linear.
Ainda assim ele não foi bom o bastante para superar nosso hack com operações de bits, que fica assim:
mov ebx, DWORD PTR [esi+edx*4] ; a = array[i]
lea ecx, [ebx-500] ; b = a - 500
sar ecx, 31 ; b = b << 31
and ecx, ebx ; b = b & a
add eax, ecx ; r += b
Embora possua mais instruções, é executado mais rapidamente nos meus testes.
Você pode também ajudar o compilador e o preditor dizendo no código o resultado provável de uma branch. O código é diferente para cada compilador, mas no GCC você pode escrever o seguinte:
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
if (likely(array[i] < 950))
r += array[i];
É uma técnica amplamente utilizada no kernel do linux. Mas é preciso testar para saber se será realmente mais rápido que deixar a cargo do preditor no seu cado específico. Pode também contribuir para otimizações por parte do compilador.
Vale ressaltar que todos os testes aqui podem e vão variar de processador para processador. Resultados que são melhores no meu podem não ser melhores no seu. Para a maioria dos casos o melhor é escrever código simples e legível e deixar para o compilador a tarefa de decidir como o executar.
Baseado em uma resposta do SO