¿Por qué un array ordenado en C++ se procesa más rápido? El secreto de Branch Prediction

Introducción: Una de las preguntas más inesperadas en el mundo de C++

Imagina la situación: escribes un bucle simple en C++ que suma los elementos de un array grande, pero solo aquellos que superan un cierto umbral. Ejecutas el código, funciona... normal. Luego decides ordenar el array previamente y lo ejecutas de nuevo. Y de repente notas que el código se ejecuta 2-3 veces más rápido! ¿Cuál es el truco? ¿Magia del compilador? ¿Un error en el benchmark?

Esta pregunta, formulada en Stack Overflow hace más de diez años, ha acumulado miles de visitas y todavía genera acalorados debates. Hoy en PythonLib la analizaremos a fondo, con ejemplos reales en C++ y una inmersión profunda en la arquitectura de los procesadores modernos. No solo aprenderás por qué ocurre esto, sino también cómo usar este efecto para acelerar tu código.

1. Reproduciendo el fenómeno: el código que sorprende

Escribamos un programa simple que demuestre claramente este efecto. Necesitaremos un array de 100,000 números enteros. Lo llenaremos con valores aleatorios, luego mediremos el tiempo de suma de todos los elementos que superen 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    // Creamos un array desordenado\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    // Sumamos para el array desordenado\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 desordenado: " << time_unsorted << " µs, suma = " << sum_unsorted << std::endl;\n\n    // Ordenamos el array\n    std::sort(data.begin(), data.end());\n\n    // Sumamos para el 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, suma = " << sum_sorted << std::endl;\n\n    std::cout << "Aceleración: " << (double)time_unsorted / time_sorted << "x" << std::endl;\n    return 0;\n}

Al compilar sin optimizaciones (bandera -O0) la diferencia será pequeña, pero si activas -O2 o -O3 en GCC/Clang, obtendrás un resultado impresionante: el array ordenado se procesa de 3 a 6 veces más rápido.

2. Anatomía del procesador: ¿de dónde viene la diferencia?

La clave del misterio es un mecanismo llamado Branch Prediction (predicción de bifurcaciones). Los procesadores modernos son máquinas segmentadas. No ejecutan las instrucciones una por una, sino que las dividen en etapas (búsqueda, decodificación, ejecución, escritura de resultado). Para que la segmentación no se detenga, el procesador intenta adivinar qué rama del código (if o else) se ejecutará a continuación y comienza a cargar las instrucciones por adelantado.

En nuestro ejemplo, la condición if (data[i] >= THRESHOLD) es un punto de bifurcación. Para el array ordenado, la predicción funciona