¿Por qué la suma de arrays es más rápida en dos bucles que en uno? Análisis de errores en C++

¿Por qué la suma de arrays es más rápida en dos bucles que en uno? Análisis del famoso error en C++

¿Alguna vez has escrito código que intuitivamente parecía correcto, pero funcionaba lento? ¿Y luego, al dividir accidentalmente un bucle en dos, obtenías una aceleración de 2 a 3 veces? Un dolor familiar. En Stack Overflow hay una pregunta legendaria que ha acumulado miles de visitas y cientos de comentarios: «Why are elementwise additions much faster in separate loops than in a combined loop?». Hoy analizaremos este fenómeno de forma sencilla, con ejemplos de código en C++ y sin teorías complicadas.

Esto no es magia. Son los fallos de caché (cache misses) y la forma en que el procesador accede realmente a la memoria. Si programas en C++ y quieres que tu código vuele, presta atención. Al final del artículo encontrarás acciones concretas que puedes aplicar ahora mismo.

El núcleo del problema: dos bucles vs uno

Imagina que tenemos dos arrays grandes a y b, y queremos realizar una suma elemento a elemento, seguida de una multiplicación de cada elemento. La intuición dice: «Hagamos un solo bucle para no hacer que el procesador vaya de un lado a otro».

Así es como se ve el bucle combinado:

const int N = 1000000;\nfloat a[N], b[N];\n\n// Un solo bucle — hacemos todo de una vez\nfor (int i = 0; i < N; ++i) {\n    a[i] = a[i] + b[i];  // suma\n    a[i] = a[i] * 2.0f;  // multiplicación\n}

Y aquí están dos bucles separados:

// Primer bucle — solo suma\nfor (int i = 0; i < N; ++i) {\n    a[i] = a[i] + b[i];\n}\n\n// Segundo bucle — solo multiplicación\nfor (int i = 0; i < N; ++i) {\n    a[i] = a[i] * 2.0f;\n}

Es lógico suponer que la primera opción es más rápida: menos sobrecarga en la organización del bucle. Pero en la práctica ocurre lo contrario: la segunda opción suele ser de 2 a 3 veces más rápida. ¿Por qué? Bienvenido al mundo de la jerarquía de caché.

Fallos de caché: el principal enemigo del rendimiento

Los procesadores modernos no acceden directamente a la memoria RAM cada vez. Utilizan la caché, una memoria rápida ubicada directamente en el chip. La caché tiene varios niveles (L1, L2, L3), y cada nivel siguiente es más lento pero más grande.

Cuando tu código lee o escribe datos, el procesador carga en la caché un bloque completo (cache line), normalmente de 64 bytes. Si la siguiente solicitud cae en el mismo bloque, es un acierto (hit). Si no, es un fallo (miss), y el procesador tiene que esperar los datos desde la RAM lenta. Un solo fallo puede costar cientos de ciclos.

Ahora volvamos a nuestro ejemplo. En el bucle combinado, en cada iteración accedemos a a[i] y b[i] dos veces: primero para leer, luego para escribir. Mientras trabajamos con a[0] y b[0], la caché carga sus líneas de caché. Pero en la siguiente iteración vamos a a[1] y b[1] — es posible un fallo si los datos están en diferentes líneas de caché. Como resultado, estamos constantemente «tirando» de la memoria, obligando a la caché a recargarse.

En dos bucles separados es diferente. El primer bucle lee secuencialmente a[i] y b[i] y escribe el resultado de vuelta. Los datos van de forma lineal: la caché es predecible y funciona de manera ideal (localidad espacial). El segundo bucle vuelve a recorrer el mismo array a — los datos ya están calientes en la caché L1. Prácticamente no hay fallos.

Principales errores que matan el rendimiento

Error n.º 1 — mezclar operaciones con diferentes arrays en un mismo bucle. Si puedes dividir la lógica en dos pasadas (especialmente si son datos grandes), hazlo. La caché te lo agradecerá.

Error n.º 2 — ignorar el tamaño de la línea de caché. 64 bytes son aproximadamente 16 float u 8 double. Si tus arrays tienen pasos extraños o saltas entre índices de forma no secuencial, estás garantizando fallos de caché.

Error n.º 3