Por que um array ordenado em C++ é processado mais rápido? O Segredo do Branch Prediction

Introdução: Uma das perguntas mais inesperadas no mundo do C++

Imagine a situação: você escreve um loop simples em C++ que soma os elementos de um grande array, mas apenas aqueles que são maiores que um determinado limite. Você executa o código, ele funciona... normalmente. Então você decide ordenar o array previamente e executa novamente. E de repente percebe que o código é executado de 2 a 3 vezes mais rápido! Qual é o truque? Magia do compilador? Erro no benchmark?

Esta pergunta, feita no Stack Overflow há mais de dez anos, acumulou milhares de visualizações e ainda gera debates acalorados. Hoje, no PythonLib, vamos analisá-la a fundo, com exemplos reais em C++ e um mergulho profundo na arquitetura dos processadores modernos. Você aprenderá não apenas por que isso acontece, mas também como usar esse efeito para acelerar seu código.

1. Reproduzindo o fenômeno: o código que surpreende

Vamos escrever um programa simples que demonstra claramente esse efeito. Precisaremos de um array de 100.000 números inteiros. Vamos preenchê-lo com valores aleatórios e, em seguida, medir o tempo de soma de todos os elementos que excedem 128.

#include <iostream>\n#include <vector>\n#include <algorithm>\n#include <chrono>\n#include <random>\n\nint main() {\n    const int SIZE = 100000;\n    const int THRESHOLD = 128;\n    \n    // Criando um array não ordenado\n    std::vector<int> data(SIZE);\n    std::mt19937 rng(42);\n    std::uniform_int_distribution<int> dist(0, 255);\n    for (auto& val : data) {\n        val = dist(rng);\n    }\n\n    // Somando para o array não ordenado\n    auto start = std::chrono::high_resolution_clock::now();\n    long long sum_unsorted = 0;\n    for (int i = 0; i < SIZE; ++i) {\n        if (data[i] >= THRESHOLD) {\n            sum_unsorted += data[i];\n        }\n    }\n    auto end = std::chrono::high_resolution_clock::now();\n    auto time_unsorted = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();\n    std::cout << "Array não ordenado: " << time_unsorted << " µs, soma = " << sum_unsorted << std::endl;\n\n    // Ordenando o array\n    std::sort(data.begin(), data.end());\n\n    // Somando para o array ordenado\n    start = std::chrono::high_resolution_clock::now();\n    long long sum_sorted = 0;\n    for (int i = 0; i < SIZE; ++i) {\n        if (data[i] >= THRESHOLD) {\n            sum_sorted += data[i];\n        }\n    }\n    end = std::chrono::high_resolution_clock::now();\n    auto time_sorted = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();\n    std::cout << "Array ordenado: " << time_sorted << " µs, soma = " << sum_sorted << std::endl;\n\n    std::cout << "Aceleração: " << (double)time_unsorted / time_sorted << "x" << std::endl;\n    return 0;\n}

Ao compilar sem otimizações (flag -O0), a diferença será pequena, mas se você ativar -O2 ou -O3 no GCC/Clang, obterá um resultado impressionante: o array ordenado é processado de 3 a 6 vezes mais rápido.

2. Anatomia do processador: de onde vem a diferença?

A chave para o mistério é um mecanismo chamado Branch Prediction (predição de desvios). Os processadores modernos são máquinas pipeline. Eles não executam instruções uma por uma, mas as dividem em estágios (busca, decodificação, execução, gravação do resultado). Para que o pipeline não fique ocioso, o processador tenta adivinhar qual ramo do código (if ou else) será executado em seguida e começa a carregar as instruções antecipadamente.

No nosso exemplo, a condição if (data[i] >= THRESHOLD) é um ponto de desvio. Para o array ordenado, a predição funciona