Predicción de saltos en CPU: el cuello de botella oculto

Hay una respuesta muy conocida en Stack Overflow que ha sido vista más de 3 millones de veces. La pregunta: ¿por qué procesar un array ordenado es más rápido que procesar uno desordenado? El código es idéntico: un bucle con una sentencia if. La única diferencia es si el array de entrada está ordenado. La versión ordenada va 6 veces más rápido. La explicación, la predicción de saltos de la CPU, revela uno de los factores de rendimiento más determinantes en la computación moderna.

Cada sentencia if, cada condición de bucle, cada caso de switch: todos son saltos en tu código. Tu CPU se encuentra miles de millones de ellos por segundo y debe predecir el resultado de cada uno antes de conocer la respuesta real. Cuando acierta, la ejecución continúa a máxima velocidad. Cuando falla, la CPU descarta entre 10 y 20 ciclos de trabajo y empieza de nuevo. Entender este mecanismo cambia la forma en que piensas sobre el código crítico para el rendimiento.

Por qué las CPU necesitan predecir

Las CPU modernas usan pipelines: no esperan a que una instrucción termine antes de empezar la siguiente. Un pipeline típico de CPU tiene entre 12 y 20 etapas. Mientras se ejecuta una instrucción, las siguientes 15 aproximadamente ya se están leyendo, decodificando y preparando. Este pipelining es lo que permite a las CPU ejecutar aproximadamente una instrucción por ciclo de reloj, aunque cada instrucción tarde muchos ciclos en completarse.

Pero cuando la CPU se encuentra con un salto (if x > 0), tiene un problema. La siguiente instrucción depende de si el salto se toma o no. La CPU no conocerá la respuesta durante varios ciclos, porque el resultado de la comparación tiene que recorrer el pipeline. Tiene dos opciones: detener el pipeline y esperar (desperdiciando más de 15 ciclos sin hacer nada), o adivinar la dirección del salto y seguir trabajando.

Las CPU siempre adivinan. El predictor de saltos hace una predicción, y la CPU busca y ejecuta instrucciones por el camino predicho. Si la predicción fue correcta, no se pierde nada. Si fue incorrecta, la CPU tiene que vaciar las instrucciones ejecutadas erróneamente, descartar sus resultados y reiniciar desde el camino correcto. Este «vaciado del pipeline» cuesta unos 15 a 20 ciclos en las CPU x86 modernas, equivalente a 15-20 instrucciones de trabajo perdido.

Cómo funcionan los predictores de saltos

Los predictores de saltos modernos son sorprendentemente sofisticados. Son, esencialmente, hardware de reconocimiento de patrones que aprende del historial de cada instrucción de salto.

El caso simple: saltos sesgados

Muchos saltos están muy sesgados: casi siempre van por el mismo camino. Una comprobación de errores que tiene éxito el 99,9 % de las veces, o una condición de bucle que es verdadera durante 999 iteraciones y falsa una sola vez. El predictor aprende rápidamente estos patrones y alcanza una precisión casi perfecta. Un salto que va por el mismo camino el 99 % de las veces tiene como mucho un 1 % de tasa de fallos.

Reconocimiento de patrones

Los predictores modernos van más allá del simple seguimiento de sesgos. Reconocen patrones repetitivos. Si un salto sigue el patrón tomado-tomado-no tomado-tomado-tomado-no tomado... (periodo 3), el predictor aprenderá este patrón y lo predecirá correctamente. El predictor TAGE (TAgged GEometric history length), usado en las CPU modernas de Intel y AMD, mantiene varias tablas de historial con longitudes distintas, capturando patrones con periodos de 2 hasta varios cientos.

Saltos correlacionados

Los predictores más avanzados también aprenden correlaciones entre saltos. Si el salto A se toma siempre que el salto B (más adelante en el código) no se toma, el predictor puede aprender esta relación. Esto se llama «predicción adaptativa de dos niveles» y maneja patrones de código como:

// These branches are correlated
if (x > 0) {      // Branch A
y = x * 2;
}
// ... some code ...
if (x <= 0) {     // Branch B — always opposite of Branch A
y = -x;
}
// The predictor learns: when A is taken, B is not taken, and vice versa
// Both branches are predicted with near-perfect accuracy

El misterio del array ordenado, explicado

Volvamos a la famosa pregunta de Stack Overflow. El código tiene este aspecto:

int sum = 0;
for (int i = 0; i < arraySize; i++) {
if (data[i] >= 128)    // This is the critical branch
sum += data[i];
}
// With SORTED data [0, 1, 2, ..., 127, 128, 129, ..., 255]:
// Branch pattern: NNNNNN...NNNTTTTTT...TTT
// First half: always NOT taken. Second half: always taken.
// Prediction accuracy: ~99.9% (only mispredicts at the transition)
// With UNSORTED data [random values 0-255]:
// Branch pattern: TNNTTNNTTTNNTNNT... (random)
// Prediction accuracy: ~50% (no pattern to learn)
// Every misprediction costs ~15 cycles

Con datos ordenados, el salto es perfectamente predecible: no se toma durante la primera mitad del array y se toma durante la segunda. El predictor aprende rápidamente cada fase y solo falla en el único punto de transición. Con datos aleatorios, el salto es básicamente una moneda al aire: el predictor no puede superar una precisión de aproximadamente 50 %, y la mitad de las iteraciones desperdician 15 ciclos en vaciados del pipeline.

Con 100.000 iteraciones y una tasa de fallos de ~50 %, son 50.000 fallos × 15 ciclos = 750.000 ciclos desperdiciados. En una CPU de 3 GHz, eso equivale a una cuarta parte de milisegundo, una fracción significativa del tiempo total de ejecución de este bucle tan simple.

¿Cuántos saltos puede gestionar tu CPU?

El predictor de saltos tiene capacidad limitada. Registra el historial de un número finito de ubicaciones de salto mediante una estructura llamada Branch Target Buffer (BTB) y tablas de historial asociadas. Las CPU modernas pueden seguir decenas de miles de ubicaciones de salto, pero las bases de código grandes pueden superar esa cifra.

Cuando dos instrucciones de salto distintas hacen alias en la misma entrada del predictor (porque el BTB se indexa mediante un hash de la dirección de la instrucción), interfieren en sus predicciones mutuas. Esto es raro en código normal, pero cobra relevancia en funciones muy grandes o cuando muchas funciones pequeñas contienen saltos.

Daniel Lemire ha publicado una excelente investigación que mide la capacidad de los predictores de saltos en distintas CPU. Los resultados muestran que las CPU Intel modernas (Alder Lake y posteriores) pueden predecir eficazmente saltos con historiales de hasta unos 200 saltos de profundidad, es decir, el predictor considera el resultado de los últimos ~200 saltos al predecir el actual. Las CPU AMD tienen una capacidad similar. Los chips ARM varían más; los chips Apple de la serie M tienen predictores de saltos especialmente potentes.

Escribir código amigable con la predicción de saltos

En la mayoría del código, la predicción de saltos no importa. El predictor es lo bastante bueno y los saltos no están en bucles críticos. Pero cuando optimizas rutas críticas para el rendimiento (bucles internos, pipelines de procesamiento de datos, parsers, códecs), el comportamiento de los saltos puede dominar el tiempo de ejecución.

Sustituir saltos por aritmética

El salto más rápido es el que no existe. Muchos patrones condicionales pueden reemplazarse por aritmética sin saltos.

// Branching version:
int max_branch(int a, int b) {
if (a > b) return a;
return b;
}
// Branchless version (compiler often does this automatically):
int max_branchless(int a, int b) {
return a ^ ((a ^ b) & -(a < b));
}
// Conditional move — the compiler's favorite trick:
int max_cmov(int a, int b) {
// Most compilers will emit a CMOV instruction for this
return (a > b) ? a : b;
}
// Clamping with branches:
int clamp_branch(int x, int lo, int hi) {
if (x < lo) return lo;
if (x > hi) return hi;
return x;
}
// Clamping branchless:
int clamp_branchless(int x, int lo, int hi) {
// min(max(x, lo), hi)
int t = x > lo ? x : lo;  // CMOV
return t < hi ? t : hi;   // CMOV
}

Los compiladores modernos son, en general, buenos convirtiendo condicionales simples en instrucciones CMOV (conditional move), que evitan los saltos por completo. Pero no siempre pueden hacerlo, sobre todo cuando los saltos tienen efectos secundarios o cuando la rama «then» es costosa. Los patrones explícitos sin saltos ayudan en bucles críticos donde el compilador no genera código óptimo.

Ordena antes de procesar

Si vas a filtrar datos con un salto, ordenarlos primero hace que el salto sea perfectamente predecible. Suena contraintuitivo, ya que ordenar tiene un coste O(n log n), pero en datasets grandes donde el bucle de procesamiento se ejecuta muchas veces o donde el coste del fallo de predicción es alto, ordenar se paga solo.

Usa tablas de búsqueda

La lógica condicional compleja (switch con muchos casos) puede sustituirse por búsquedas en tablas. En lugar de una cadena de comparaciones, indexa un array. El acceso al array puede provocar un fallo de caché, pero normalmente es más barato que una cascada de saltos mal predichos.

// Branch-heavy version:
char to_hex(int nibble) {
if (nibble < 10)
return '0' + nibble;
else
return 'a' + nibble - 10;
}
// Lookup table version (no branches):
static const char hex_table[] = "0123456789abcdef";
char to_hex_lut(int nibble) {
return hex_table[nibble];
}

Dale pistas al compilador

GCC y Clang soportan __builtin_expect para indicar al compilador qué dirección de salto es la más probable. Esto no controla directamente el predictor de la CPU (que aprende en tiempo de ejecución), pero sí afecta a cómo el compilador organiza el código: colocar el camino probable en línea recta, sin saltos, lo que es más rápido gracias a los efectos de la caché de instrucciones.

// Tell the compiler that errors are unlikely
if (__builtin_expect(result == NULL, 0)) {
handle_error();
}
// C++20 provides cleaner syntax:
if (result == NULL) [[unlikely]] {
handle_error();
}
// Linux kernel defines macros for this:
#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
if (unlikely(ptr == NULL)) {
panic("null pointer");
}

Medir el comportamiento de los saltos

Puedes medir directamente el rendimiento del predictor de saltos usando los contadores de rendimiento del hardware. En Linux, perf stat te muestra las tasas de fallo de cualquier programa.

# Measure branch prediction statistics
$ perf stat -e branches,branch-misses ./my_program
Performance counter stats for './my_program':
1,482,937,256  branches          # 892.7M/sec
3,271,842  branch-misses     # 0.22% of all branches
# 0.22% misprediction rate — excellent.
# Anything under 1% is good.
# Over 5% in a hot loop means branch prediction is hurting you.
# Over 10% means you should consider branchless alternatives.

Para microbenchmarks, herramientas como Google Benchmark pueden registrar los branch-misses por iteración, dándote una respuesta precisa sobre si un cambio mejoró el comportamiento de los saltos. Es más útil que el tiempo de reloj, que incluye el ruido de otra actividad del sistema.

Cuándo importa (y cuándo no)

La optimización de la predicción de saltos importa en una categoría de código estrecha pero importante: bucles internos ajustados que procesan grandes cantidades de datos. Parsers, compresores, procesamiento de imágenes, cálculo numérico, evaluación de consultas en bases de datos: aquí es donde el comportamiento de los saltos domina.

Para todo lo demás (lógica de negocio, handlers de API, operaciones CRUD), la predicción de saltos es irrelevante. Los saltos del enrutador de tu servidor web no son tu cuello de botella. No conviertas cadenas if/else legibles en aritmética sin saltos ilegible en código que se ejecuta una vez por petición HTTP. Optimiza donde te indique el profiler, no donde la teoría sugiere que podría haber un problema.

El verdadero valor de entender la predicción de saltos no está en la optimización manual, sino en entender por qué tu código rinde como lo hace. Cuando un profiler muestra que un bucle simple con una sentencia if es más lento de lo esperado, el fallo de predicción de saltos suele ser la explicación. Cuando ordenar tus datos de entrada acelera mágicamente el procesamiento, la predicción de saltos es la razón. Tener este modelo mental te permite diagnosticar problemas de rendimiento que, de otro modo, parecerían misteriosos.