La jerarquía de memoria

El modelo mental que heredaste dice que la memoria es un array plano de bytes con coste de acceso uniforme. Esa ficción fue aproximadamente cierta hasta mediados de los ochenta y hoy miente por un factor de doscientos. Entre el registro y la DRAM hay cuatro niveles de almacenamiento cuyas latencias abarcan dos órdenes de magnitud, y el rendimiento de casi todo el código que escribirás no lo determina cuántas operaciones haces, sino dónde estaban los datos cuando las hiciste.

La unidad de transferencia no es el byte

Cuando escribes x = a[i], la CPU no trae cuatro bytes. Trae una línea de caché completa: sesenta y cuatro bytes alineados a una frontera de sesenta y cuatro, en prácticamente todas las microarquitecturas contemporáneas de x86-64 y ARM. Esa línea es la partícula elemental del subsistema de memoria; no existe forma de pedir menos, y todo el coste de la transacción —abrir la fila del banco de DRAM, atravesar el bus, ocupar una entrada del búfer de relleno— se paga por línea, no por byte.

De ahí se deduce la consecuencia central de esta lección: un acceso a memoria trae gratis los quince enteros que están al lado. Si los usas, la latencia se amortiza entre dieciséis; si no, la pagas dieciséis veces.

flowchart TD
A[Registros: menos de 1 ciclo] --> B[L1 datos: 32 a 48 KiB, 4 o 5 ciclos]
B --> C[L2 unificada: 512 KiB a 2 MiB, 14 ciclos]
C --> D[L3 compartida: 8 a 64 MiB, 40 a 60 ciclos]
D --> E[DRAM: gigabytes, 200 a 350 ciclos]
style A fill:#a6e3a1,color:#11111b
style B fill:#94e2d5,color:#11111b
style C fill:#89b4fa,color:#11111b
style D fill:#f9e2af,color:#11111b
style E fill:#f38ba8,color:#11111b

Traducido a nanosegundos en una máquina de tres gigahercios: la L1 responde en algo más de un nanosegundo y la DRAM en unos ochenta. Si tu programa emite una instrucción por ciclo, un fallo hasta memoria principal equivale a descartar entre doscientas y trescientas instrucciones de trabajo útil. Ninguna optimización aritmética compite con eso.

El experimento que hace visible la línea es el barrido con paso variable. Recorre un búfer grande tocando un elemento de cada paso y mide el tiempo por elemento tocado:

#include <stdint.h>
#include <stddef.h>

/* Suma con paso variable sobre un buffer que no cabe en L2. */
uint64_t barrido(const uint32_t *v, size_t n, size_t paso) {
    uint64_t s = 0;
    for (size_t i = 0; i < n; i += paso)
        s += v[i];
    return s;
}

Con paso igual a uno tocas los dieciséis enteros de cada línea y el coste por elemento es mínimo. Al aumentar el paso, el tiempo por elemento tocado crece de forma casi lineal hasta que el paso alcanza dieciséis, porque cada acceso empieza a costar una línea entera. A partir de ahí se aplana: ya estás pagando una línea completa por elemento y no hay nada peor que puedas hacer, salvo provocar fallos de TLB. La meseta aparece exactamente en 64 / sizeof(uint32_t), que es la forma más limpia de medir el tamaño de línea de una máquina desconocida sin consultar su documentación.

Localidad espacial y temporal

Las dos formas de reutilización que la jerarquía premia son distintas y se optimizan con técnicas distintas.

La disposición de los datos gobierna la primera. Compara un array de estructuras con una estructura de arrays cuando el bucle solo consume un campo:

/* AoS: 40 bytes por particula, el bucle usa 4. */
struct particula { float x, y, z, vx, vy, vz; uint32_t id, flags, pad0, pad1; };
struct particula p[N];
for (size_t i = 0; i < N; i++) suma += p[i].x;   /* usa 4 de cada 64 bytes */

/* SoA: el bucle recorre memoria densa y ademas se vectoriza solo. */
struct nube { float *x, *y, *z, *vx, *vy, *vz; };
for (size_t i = 0; i < N; i++) suma += nube.x[i]; /* usa 64 de cada 64 bytes */

La primera versión consume un dieciseisavo del ancho de banda que paga. La segunda lo consume entero, y de propina le entrega al compilador un bucle trivialmente vectorizable. La diferencia medida en máquinas reales está entre cuatro y diez veces, con idéntica aritmética.

La estructura del bucle gobierna la segunda. El caso canónico es la multiplicación de matrices: la versión ingenua recorre B por columnas, con paso N, y cuando N es grande cada acceso es un fallo. El bloqueo por mosaicos particiona el problema en submatrices cuyo conjunto de trabajo cabe en la caché:

#define T 64   /* tres bloques de T por T floats deben caber holgados en L2 */

for (size_t ii = 0; ii < N; ii += T)
  for (size_t kk = 0; kk < N; kk += T)
    for (size_t jj = 0; jj < N; jj += T)
      for (size_t i = ii; i < ii + T; i++)
        for (size_t k = kk; k < kk + T; k++) {
            const float a = A[i * N + k];        /* invariante del bucle interno */
            for (size_t j = jj; j < jj + T; j++)
                C[i * N + j] += a * B[k * N + j]; /* B recorrida por filas */
        }

El número de operaciones en coma flotante es idéntico. El número de transferencias desde DRAM cae de un orden cúbico a uno cúbico dividido por la raíz de la capacidad de caché, y el resultado en una matriz de dos mil por dos mil es una aceleración de entre cinco y quince veces. La reordenación de los índices a i, k, j es la mitad del truco: convierte el recorrido por columnas de B en uno por filas.

Cuando el hardware deja de ayudarte

El prefetcher es un predictor de direcciones: detecta accesos con paso constante —hacia delante o hacia atrás, y varios flujos simultáneos— y trae las líneas antes de que las pidas. Mientras tu acceso sea regular, la latencia de DRAM desaparece casi por completo y solo queda el límite de ancho de banda. Pero el prefetcher no puede predecir lo que depende de un dato aún no cargado: en p = p->siguiente la dirección del acceso siguiente es el resultado del acceso actual, y esa dependencia de punteros serializa los fallos uno tras otro sin solapamiento posible. Es el peor caso del subsistema de memoria y la razón de que las estructuras enlazadas sean caras más allá de lo que sugiere su recuento de operaciones.

Cuando el patrón es irregular pero conocido con antelación, puedes hacer tú el trabajo que el hardware no puede. La precarga explícita pide una línea sin consumirla, de modo que su latencia se solape con el cómputo de las iteraciones anteriores:

/* Recorrido indexado: el prefetcher no ve el patron, pero tu si.
   La distancia de precarga se ajusta empiricamente, no se deduce. */
for (size_t i = 0; i < n; i++) {
    __builtin_prefetch(&tabla[idx[i + 24]], 0, 1);  /* lectura, localidad media */
    acumulador += tabla[idx[i]];
}

Los dos últimos argumentos declaran si el acceso será de lectura o escritura y cuánta localidad temporal esperas, lo que determina en qué nivel se aloja la línea. Es una herramienta afilada y fácil de empeorar: una distancia demasiado corta no oculta nada y una demasiado larga expulsa datos vivos. Sin medición no la toques.

Dos límites más aparecen cuando el conjunto de trabajo crece:

• Asociatividad. Una caché de ocho vías reparte las líneas en conjuntos según bits medios de la dirección. Si tu bucle toca nueve direcciones que caen en el mismo conjunto, se expulsan mutuamente aunque la caché esté casi vacía: son los fallos por conflicto. Se provocan con facilidad al recorrer matrices cuya fila mide una potencia de dos exacta, y se curan añadiendo relleno para desplazar el paso.
• TLB. La traducción de virtual a física también se cachea, y la TLB de primer nivel guarda del orden de sesenta y cuatro entradas. Con páginas de cuatro kibibytes eso cubre apenas un cuarto de mebibyte. Un recorrido aleatorio sobre un gigabyte falla en TLB casi en cada acceso, y cada fallo cuesta un recorrido de la tabla de páginas. Las páginas enormes de dos mebibytes multiplican por quinientos doce la cobertura y son la única cura real.

Y un último efecto, invisible en código monohilo: la compartición falsa. Dos hilos que escriben variables distintas alojadas en la misma línea fuerzan al protocolo de coherencia a rebotar esa línea entre núcleos en cada escritura. El código es correcto, no hay carrera de datos, y el rendimiento cae un orden de magnitud sin que ninguna herramienta de corrección se queje.

#include <stdalign.h>

/* Mal: los ocho contadores caben en una linea. Ocho hilos escribiendo
   provocan invalidaciones cruzadas continuas. */
static uint64_t cuenta_mala[8];

/* Bien: cada contador ocupa su propia linea. Se desperdicia memoria
   a proposito, y es la compra mas rentable del programa. */
struct alignas(64) contador { uint64_t v; };
static struct contador cuenta[8];

La regla general es que los datos compartidos entre hilos se separan y los datos privados se compactan, exactamente al revés de lo que sugiere la intuición de ahorrar memoria. Nótese que alignas es palabra clave en C23 y ya no necesita la cabecera, aunque incluirla sigue siendo inofensivo.