Ejecución especulativa vs código sin ramas

Ejecución Especulativa y Código sin Ramificaciones: Compromisos Ocultos de Rendimiento

Los procesadores modernos ejecutan miles de millones de operaciones por segundo, pero la velocidad de acceso a la memoria crece más lentamente. Esta brecha significa que la espera por datos se convierte en una fuente principal de pérdida de rendimiento. Los procesadores han evolucionado de ejecutores pasivos a gestores activos del flujo de datos: ejecución fuera de orden, reordenamiento de dependencias y ejecución especulativa.

La predicción de ramificaciones permite que las cargas comiencen temprano, ocultando la latencia de memoria. Una predicción errónea cuesta 10–20 ciclos, pero esperar por L3 o DRAM toma cientos. El código sin ramificaciones elimina las predicciones erróneas, pero elimina la capacidad del procesador para especular.

Evolución de la Ejecución Secuencial a la Especulativa

Los primeros sistemas ejecutaban instrucciones estrictamente de forma secuencial. El IBM System/360 Model 91 introdujo el algoritmo de Tomasulo para ejecución fuera de orden: las instrucciones comienzan cuando los operandos están listos.

La ejecución especulativa surgió más tarde en procesadores superscalares como el Intel Pentium Pro (1995). Una tubería de 40 micro-operaciones mantiene docenas de instrucciones en vuelo, prediciendo ramificaciones basadas en el historial.

for (size_t i = 0; i < n; i++) {
    if (arr[i] >= 0) {
          ... código_verdadero ...;
    } else {
        ... código_falso ...;
    }
}

Aquí, cargar arr[i] puede causar un bloqueo de 10–100+ ciclos si los datos no están en L1. El procesador predice la ramificación, inicia código_verdadero y comienza la precarga. En una predicción errónea—vacía la tubería y reinicia.

Sin Ramificaciones vs Con Ramificaciones: Dependencia de la Caché

Simplificado con ramificación:

if (arr[i] > 0) {
    resultado++;
}

Se convierte en:

resultado += (arr[i] > 0);

• Datos en L1: sin ramificaciones gana—sin predicción errónea, retraso mínimo.
• L2: neutral, el costo de predicción errónea es bajo.
• L3/DRAM: con ramificaciones es más rápido—la especulación activa la precarga temprano, ocultando la latencia.

Sin ramificaciones mueve el retraso a la ruta crítica: el procesador espera por datos antes de la comparación, sin superponer cálculos.

Búsqueda de Valor: El Costo de las Cargas Incondicionales

Original:

Valor resultado = valor_por_defecto;
for (size_t i = 0; i < n; ++i) {
    if (claves[i] == objetivo) {
        resultado = valores[i];
    }
}
return resultado;

Sin ramificaciones:

Valor resultado = valor_por_defecto;
for (size_t i = 0; i < n; ++i) {
    resultado = (claves[i] == objetivo) ? valores[i] : resultado;
}
return resultado;

En sin ramificaciones, valores[i] carga en cada iteración, desperdiciando ancho de banda en todo el arreglo. El original lee solo hasta una coincidencia.

Búsqueda Binaria: Cadenas de Dependencia

Con ramificaciones:

while (bajo < alto) {
    size_t medio = bajo + (alto - bajo) / 2;
    if (claves[medio] < objetivo)
        bajo = medio + 1;
    else
        alto = medio;
}

El procesador calcula especulativamente el siguiente medio y precarga claves[medio].

Sin ramificaciones:

while (bajo < alto) {
    size_t medio = bajo + (alto - bajo) / 2;
    size_t paso = (alto - bajo) / 2;
    bajo  = (claves[medio] < objetivo) ? medio + 1 : bajo;
    alto = (claves[medio] < objetivo) ? alto    : medio;
}

Las dependencias en el resultado de la comparación bloquean la especulación: el siguiente medio espera por las escrituras de bajo/alto.

• La mitad de las predicciones son incorrectas, pero la precarga temprana superpone el vaciado.
• Sin ramificaciones: más instrucciones, cargas posteriores, retrasos de memoria explícitos.

Conclusiones Clave

• La especulación oculta la latencia de memoria activando la precarga en ramificaciones predichas.
• Sin ramificaciones elimina las predicciones erróneas pero empeora el rendimiento con acceso a L3/DRAM.
• Perfila en hardware objetivo: L1—sin ramificaciones, arreglos grandes—con ramificaciones.
• Los puertos de juegos de consola a menudo sufren por ignorar estos efectos.
• Las dependencias en cadenas sin ramificaciones bloquean optimizaciones fuera de orden.

Con datos aleatorios en L1, sin ramificaciones domina. Con patrones o grandes volúmenes, con ramificaciones gana debido a las cargas especulativas.

— Editorial Team