Código cache-friendly en C++: qué es y por qué es importante para la velocidad

¿Tu código funciona lento, aunque el algoritmo es ideal? Quizás no es "amigable" con el caché

¿Alguna vez has escrito código en C++ que en teoría debería funcionar a la velocidad del rayo, pero en la práctica se ralentiza? ¿O has notado que recorrer una matriz bidimensional por filas y por columnas da velocidades diferentes, aunque la complejidad del algoritmo sea la misma? Si es así, te has encontrado con el código cache-friendly (amigable con el caché) y su opuesto, el código cache-unfriendly (no amigable con el caché).

Hoy analizaremos qué significa esto a nivel de hardware, por qué el caché no es solo "otra memoria", sino la clave del rendimiento, y cómo escribir código que el procesador "ame". Sin abstracciones complejas, solo C++ y ejemplos claros.

¿Por qué el procesador no puede simplemente leer de la memoria RAM?

La velocidad del procesador se ha multiplicado por miles en las últimas décadas, mientras que la velocidad de la memoria RAM (DRAM) solo lo ha hecho por decenas. Imagina un piloto de Fórmula 1 (el procesador) que tiene que detenerse cada segundo para obtener combustible (datos) de un camión que va a 30 km/h (la memoria RAM). Triste y lento.

La solución es el caché del procesador: una memoria pequeña pero muy rápida, integrada directamente en el chip. Almacena copias de los datos utilizados con frecuencia. Cuando el procesador necesita datos, primero verifica el caché (L1, el más rápido; luego L2; luego L3). Solo si los datos no están allí (cache miss, fallo de caché), va a la lenta memoria RAM.

Aquí hay algunas latencias aproximadas (en ciclos de procesador):

\n
• Caché L1: ~3-5 ciclos
\n
• Caché L2: ~10-20 ciclos
\n
• Caché L3: ~30-50 ciclos
\n
• Memoria RAM: ~100-300 ciclos
\n

La diferencia entre L1 y RAM es de 50 a 100 veces. Por eso, el código cache-friendly en C++ puede ser varias veces más rápido que su equivalente "no amigable".

Principio de localidad: cómo decide el caché qué guardar

El caché no copia un solo byte; trabaja con bloques (cache lines), generalmente de 64 bytes. Cuando lees una variable, el procesador carga todo el bloque que contiene esa variable. Y apuesta por dos principios:

\n
• Localidad espacial (Spatial locality): si lees un elemento del arreglo arr[i], es probable que pronto necesites arr[i+1].
\n
• Localidad temporal (Temporal locality): si has leído datos ahora, probablemente volverás a acceder a ellos en un futuro cercano.
\n

El código cache-friendly es código que maximiza el uso de estos principios. Veamos cómo se ve esto en la práctica.

Ejemplo 1: Recorrido de una matriz bidimensional — un clásico

Cache-unfriendly (código malo)

const int SIZE = 1024;\nint matrix[SIZE][SIZE];\n\n// Recorrido por columnas (column-major)\nfor (int j = 0; j < SIZE; ++j) {\n    for (int i = 0; i < SIZE; ++i) {\n        matrix[i][j] = i + j;\n    }\n}\n

En C++, los arreglos se almacenan en orden row-major (por filas). Es decir, los elementos de la fila matrix[0][0], matrix[0][1], matrix[0][2]... están en memoria de forma secuencial. El bucle externo sobre j (columnas) obliga al procesador a saltar a través de toda la fila en cada paso: cada acceso a matrix[i][j] es, muy probablemente, un cache miss. El procesador pierde tiempo cargando nuevos bloques, mientras que los datos anteriores se eliminan del caché.

Cache-friendly (código bueno)

// Recorrido por filas (row-major)\nfor (int i = 0; i < SIZE; ++i) {\n    for (int j = 0; j < SIZE; ++j) {\n        matrix[i][j] = i + j;\n    }\n}\n

Ahora recorremos la memoria de forma secuencial. Tan pronto como cargamos el bloque con matrix[0][0], los siguientes 15 elementos (con un int de 4 bytes) ya están en el caché. ¡Esto proporciona un aumento de velocidad de 5 a 10 veces