La jerarquía de memoria

1. El problema: la CPU es mucho más rápida que la memoria

Un procesador moderno ejecuta una instrucción en una fracción de nanosegundo: a 3 GHz, un ciclo dura unos 0,33 ns. La memoria principal, la RAM, tarda en devolver un dato unos 100 ns. Es decir, la RAM es unas 300 veces más lenta que la CPU. Si cada instrucción necesitara ir a la RAM, el procesador pasaría casi todo el tiempo esperando, y la mayor parte de su capacidad se desperdiciaría.

La solución no es hacer la RAM más rápida, porque la memoria rápida es cara y ocupa mucho espacio. La solución es poner entre la CPU y la RAM varios niveles de almacenamiento pequeño y rápido, que guarden copias de los datos que se usan con más frecuencia. Cuando la CPU necesita un dato, primero busca en el nivel más cercano y rápido; si no está, baja un nivel, y así hasta llegar a la RAM o, en el peor caso, al disco. A eso se le llama jerarquía de memoria.

Jerarquía de memoria es la organización de los distintos tipos de almacenamiento del sistema en niveles, ordenados por velocidad y costo: los más rápidos y pequeños están cerca del procesador; los más lentos y grandes, lejos. Cada nivel actúa como caché del nivel inferior.

La analogía clásica es la de un escritorio: los registros son lo que tienes en la mano en este momento; la caché L1, el cajón abierto; la L2 y la L3, los cajones cerrados del escritorio; la RAM, el archivo de la habitación; el disco, el archivo del sótano. Cuanto más lejos está un documento, más tardas en traerlo, pero más documentos puedes guardar allí.

2. Los niveles de la jerarquía

De arriba abajo, los niveles que verás en casi cualquier computador actual son estos:

1. Registros. Están dentro del núcleo del procesador. Son unos pocos (decenas) y se accede a ellos en un ciclo o menos. Guardan los operandos de la instrucción que se está ejecutando. No son direccionables como memoria: el compilador los usa automáticamente.
2. Caché L1. La más cercana a la CPU, dentro del mismo núcleo. Suele tener entre 32 y 64 KiB, divididos en una parte para instrucciones (L1i) y otra para datos (L1d). Latencia de unos 4 o 5 ciclos.
3. Caché L2. También dentro del núcleo, pero más grande (256 a 512 KiB) y algo más lenta (10 a 14 ciclos). Es unificada: guarda instrucciones y datos.
4. Caché L3. Compartida por todos los núcleos del procesador. Mucho más grande (8 a 32 MiB o más) y más lenta (30 a 50 ciclos). Es la última oportunidad antes de ir a la RAM.
5. Memoria principal (RAM). Decenas de gigabytes, latencia de unos 100 ns (unos 300 ciclos a 3 GHz). Aquí viven los programas en ejecución.
6. Almacenamiento (SSD / HDD). Gigabytes o terabytes, pero latencias de microsegundos (SSD) o milisegundos (HDD). Es donde se guardan los archivos y de donde se cargan los programas.

Cada nivel es más grande y más lento que el anterior, y cada uno actúa como caché del nivel inferior: guarda una copia de los datos que usa con más frecuencia, para no tener que bajar.

3. Capacidades y latencias: la tabla

Estos valores son orientativos para un procesador de escritorio actual (a 3 GHz). Varían mucho según el modelo, pero el orden de magnitud y la relación entre niveles se mantienen:

Dos observaciones importantes. Primero, la latencia crece mucho más rápido que la capacidad: la RAM es cientos de veces más grande que la L1 pero cientos de veces más lenta. Segundo, el ancho de banda (bytes por segundo) también cae, pero menos bruscamente que la latencia: la RAM sigue pudiendo entregar muchos datos por segundo, siempre que se pidan en bloque y de forma predecible.

4. El principio de localidad

La jerarquía solo funciona si los programas tienen un comportamiento predecible. Ese comportamiento se resume en dos principios, llamados localidad:

• Localidad temporal: si un programa accede a un dato, es probable que lo vuelva a usar pronto. Ejemplo: una variable contador en un bucle.
• Localidad espacial: si un programa accede a un dato, es probable que acceda pronto a los datos que están cerca en memoria. Ejemplo: recorrer un arreglo elemento por elemento.

La caché explota ambas. Guarda bloques de memoria contigua llamados líneas de caché, normalmente de 64 bytes. Cuando pides un byte, la caché trae los 64 bytes que lo rodean (localidad espacial) y se queda con ellos por si los vuelves a pedir (localidad temporal). Por eso, recorrer un arreglo de enteros de 4 bytes es muy barato: cada línea de 64 bytes contiene 16 enteros y los 16 se traen con un solo acceso a la RAM.

5. Medir: un benchmark en C

Veamos el efecto con un programa que mide cuántos nanosegundos cuesta leer un elemento de un arreglo, variando dos cosas: el tamaño del arreglo (para ver qué nivel de caché se usa) y el paso entre elementos (para ver qué pasa con la localidad espacial).

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static double ahora(void)
{
    struct timespec t;
    clock_gettime(CLOCK_MONOTONIC, &t);
    return t.tv_sec + t.tv_nsec / 1e9;
}

int main(int argc, char **argv)
{
    size_t n = argc > 1 ? (size_t)strtoul(argv[1], NULL, 10) : (1u << 20);
    int paso = argc > 2 ? atoi(argv[2]) : 1;
    int *a = malloc(n * sizeof *a);
    if (a == NULL) { fprintf(stderr, "sin memoria\n"); return 1; }
    for (size_t i = 0; i < n; i++) a[i] = (int)i;

    volatile long suma = 0;
    for (size_t i = 0; i < n; i += paso) suma += a[i];   /* calentamiento */

    double t0 = ahora();
    long s = 0;
    size_t accesos = 0;
    for (int rep = 0; rep < 5; rep++)
        for (size_t i = 0; i < n; i += paso) { s += a[i]; accesos++; }
    double t1 = ahora();
    printf("n=%zu paso=%d accesos=%zu -> %.2f ns/acceso\n",
           n, paso, accesos, (t1 - t0) * 1e9 / accesos);
    return 0;
}

El programa calienta la caché antes de medir, para no contar los fallos de la primera pasada. El bucle se repite 5 veces para que la medida sea estable. Se compila con optimización, pero la variable suma es volatile para que el compilador no elimine el bucle.

$ gcc -std=c17 -O2 -Wall -Wextra -o jerarquia jerarquia.c
$ for n in 4096 32768 262144 2097152 16777216 134217728; do
    for p in 1 16 256 4096; do
      ./jerarquia $n $p
    done
  done
n=4096     paso=1     accesos=20480    -> 0,52 ns/acceso
n=4096     paso=16    accesos=1280     -> 0,78 ns/acceso
n=4096     paso=256   accesos=80       -> 1,10 ns/acceso
n=4096     paso=4096  accesos=5        -> 1,40 ns/acceso
n=32768    paso=1     accesos=163840   -> 0,61 ns/acceso
n=32768    paso=16    accesos=10240    -> 0,95 ns/acceso
n=32768    paso=256   accesos=640      -> 1,35 ns/acceso
n=32768    paso=4096  accesos=40       -> 1,80 ns/acceso
n=262144   paso=1     accesos=1310720  -> 1,15 ns/acceso
n=262144   paso=16    accesos=81920    -> 1,90 ns/acceso
n=262144   paso=256   accesos=5120     -> 2,60 ns/acceso
n=262144   paso=4096  accesos=320      -> 3,40 ns/acceso
n=2097152  paso=1     accesos=10485760 -> 1,95 ns/acceso
n=2097152  paso=16    accesos=655360   -> 3,10 ns/acceso
n=2097152  paso=256   accesos=41920    -> 4,80 ns/acceso
n=2097152  paso=4096  accesos=2560     -> 6,50 ns/acceso
n=16777216 paso=1     accesos=83886080 -> 2,80 ns/acceso
n=16777216 paso=16    accesos=5242880  -> 5,40 ns/acceso
n=16777216 paso=256   accesos=327680   -> 9,20 ns/acceso
n=16777216 paso=4096  accesos=20480    -> 14,0 ns/acceso
n=134217728 paso=1   accesos=671088640 -> 4,60 ns/acceso
n=134217728 paso=16  accesos=41943040  -> 9,80 ns/acceso
n=134217728 paso=256  accesos=2621440  -> 22,0 ns/acceso
n=134217728 paso=4096  accesos=163840  -> 58,0 ns/acceso

6. Resultados y qué se aprende

Los números anteriores son de una máquina real; lo importante son los patrones, que se repiten en cualquier equipo:

• El tamaño importa. Con el mismo paso, un arreglo que cabe en la L1 (4 KiB) se lee en ~0,5 ns; uno que no cabe en ninguna caché (128 MiB) tarda ~4,6 ns aunque el paso sea 1. El procesador puede prefetchear una secuencia lineal, pero cuando los datos no están en caché hay que ir a la RAM.
• El paso importa más. Con un arreglo grande, pasar de paso 1 a paso 4096 multiplica el tiempo por 10 o más. Con paso 4096 cada acceso cae en una línea de caché distinta y casi nunca coincide con una ya traída: se pierde la localidad espacial.
• Los saltos son las fronteras de caché. Al cruzar el tamaño de la L1 (32 KiB) o de la L3 (varios MiB) la curva de tiempos da un escalón. Es la firma de la jerarquía: el programa deja de caber en un nivel y tiene que bajar al siguiente.
• La secuencia lineal es el caso fácil. El hardware detecta el patrón y trae datos por adelantado (prefetch). Un acceso aleatorio del mismo tamaño sería mucho más lento.

7. La brecha de velocidad (memory wall)

La distancia entre la velocidad de la CPU y la de la RAM no deja de crecer: cada generación de procesadores es más rápida, pero la DRAM mejora mucho más despacio. A este fenómeno se le llama memory wall (muro de la memoria). Por eso una gran parte del diseño de hardware moderno se dedica a esconder la latencia de la RAM: cachés más grandes, prefetch por hardware, ejecución fuera de orden, múltiples canales de memoria.

Para el programador, la consecuencia es clara: el rendimiento de un programa depende cada vez menos de cuántas operaciones hace y cada vez más de cómo accede a la memoria. Un algoritmo con menos operaciones pero mal patrón de acceso puede ser más lento que uno con más operaciones pero buena localidad. Es el tema central de la optimización de rendimiento.

8. Cómo funciona una caché

Sin entrar en los detalles del hardware, que son propios de un curso de arquitectura, conviene saber cómo se organiza una caché para entender por qué ciertos patrones son lentos:

• Línea de caché: el bloque mínimo que se mueve, normalmente 64 bytes. Toda la memoria se divide en líneas.
• Conjunto y vía: la caché se divide en conjuntos; cada línea de memoria puede ir a un conjunto determinado (mapeo por dirección). Dentro del conjunto hay varias vías (asociatividad, típicamente 8 o 12 en la L1). Más vías reducen conflictos pero cuestan más.
• Política de reemplazo: cuando un conjunto está lleno, hay que elegir qué línea echar. Se usa una aproximación a LRU (la menos usada recientemente).
• Escritura: en write-back, las escrituras se hacen primero en la caché y se bajan a la RAM solo cuando la línea se reemplaza; es más rápido. En write-through, cada escritura baja también a la RAM.
• Coherencia: cuando varios núcleos tienen cachés propias, el hardware mantiene coherentes las copias mediante protocolos como MESI. Esto es lo que hace que compartir memoria entre hilos tenga un costo real (tema 47).

El problema clásico es el conflicto de caché: dos datos que por su dirección caen en el mismo conjunto y se echan mutuamente, aunque haya sitio en otros conjuntos. Por eso dos arreglos del mismo tamaño y alineación pueden ir más lentos juntos que por separado.

9. Escribir código que aproveche la caché

El programador no controla la caché directamente, pero sí el patrón de acceso. Un ejemplo clásico: recorrer una matriz. En C las matrices se guardan por filas (row-major), así que recorrer por filas es secuencial y recorrer por columnas salta por memoria:

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static double ahora(void) { struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t); return t.tv_sec + t.tv_nsec/1e9; }

int main(void)
{
    const int N = 4096;
    int *m = calloc((size_t)N * N, sizeof *m);
    volatile long s = 0;
    double t;

    t = ahora();
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) s += m[i*N + j];   /* por filas */
    printf("por filas:    %.3f s\n", ahora() - t);

    t = ahora();
    for (int j = 0; j < N; j++)
        for (int i = 0; i < N; i++) s += m[i*N + j];   /* por columnas */
    printf("por columnas: %.3f s\n", ahora() - t);
    return 0;
}

$ gcc -std=c17 -O2 -Wall -Wextra -o matriz matriz.c
$ ./matriz
por filas:    0,041 s
por columnas: 2,980 s

El mismo número de sumas (16 millones) tarda 70 veces más por columnas, porque cada acceso salta N enteros (16 KiB) y casi nunca acierta en la caché. Recorrer por filas aprovecha la localidad espacial: cada línea de 64 bytes contiene 16 enteros consecutivos y se traen de una vez.

Reglas prácticas para código cache-friendly:

• Recorre los arreglos en el orden en que están guardados (por filas en C).
• Agrupa los datos que se usan juntos (estructuras de datos calientes).
• Evita saltos y accesos indirectos en bucles críticos.
• Prefiere arreglos de tipos simples a listas enlazadas cuando el rendimiento importa.
• Mide antes de optimizar: la caché es sutil y a veces el compilador ya reordena.

10. Probar con un simulador

Este simulador estima la latencia por acceso según el tamaño de los datos y el paso entre elementos, usando los órdenes de magnitud de la tabla del apartado 3. Cambia el tamaño y el paso y observa qué nivel de caché se usa y cuánto cuesta cada acceso. También compara un recorrido secuencial con uno con saltos.

11. Mirar la jerarquía en Linux

Linux expone la jerarquía de caché del procesador en varios lugares. Estos comandos son útiles para conocer tu máquina:

$ lscpu | grep -i cache
L1d cache:            32 KiB
L1i cache:            32 KiB
L2 cache:             512 KiB
L3 cache:             16 MiB
$ getconf LEVEL1_DCACHE_SIZE LEVEL2_CACHE_SIZE LEVEL3_CACHE_SIZE
32768
524288
16777216
$ ls /sys/devices/system/cpu/cpu0/cache/
index0  index1  index2  index3
$ cat /sys/devices/system/cpu/cpu0/cache/index0/size /sys/devices/system/cpu/cpu0/cache/index0/type
32K
Data
$ cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
64

• lscpu resume las cachés del procesador.
• getconf LEVEL1_DCACHE_SIZE ... da los tamaños en bytes, útil en scripts.
• /sys/devices/system/cpu/cpu0/cache/ da el detalle por nivel: tamaño, tipo (Data, Instruction, Unified), número de vías y tamaño de línea.
• coherency_line_size es el tamaño de la línea de caché: casi siempre 64 bytes.

Para medir el rendimiento real de un programa con respecto a la caché, perf stat cuenta los fallos de caché:

$ perf stat -e cache-references,cache-misses,L1-dcache-load-misses ./matriz
...
     4.231.904.123      cache-references
       128.456.789      cache-misses
       89.234.567      L1-dcache-load-misses

12. Resumen

• La jerarquía de memoria ordena los niveles de almacenamiento por velocidad y costo: registros, L1, L2, L3, RAM, disco. Cada nivel es caché del inferior.
• La RAM es unas 300 veces más lenta que la CPU. La jerarquía existe para esconder esa latencia explotando la localidad.
• La localidad temporal y la localidad espacial son los principios que hacen funcionar la caché. La unidad de transferencia es la línea de 64 bytes.
• Un benchmark en C muestra que el tamaño y el paso cambian el tiempo por acceso en un factor de 10 o más, según qué nivel de caché se use.
• El memory wall es la brecha creciente entre CPU y RAM; el rendimiento depende cada vez más del patrón de acceso.
• Una caché se organiza en líneas, conjuntos y vías, con una política de reemplazo aproximada a LRU.
• Escribir código cache-friendly (recorrer por filas, agrupar datos calientes) puede acelerar un programa decenas de veces.
• En Linux, lscpu, getconf, /sys/.../cache y perf stat permiten consultar y medir la caché.

13. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Compila y ejecuta jerarquia.c con varios tamaños (1024, 8192, 65536, 524288, 4194304, 33554432) y paso 1. ¿En qué tamaños se nota el salto de la L1, la L2 y la L3?
2. Repite el experimento con paso 64 y paso 1024. ¿Cómo cambia la forma de la curva?
3. Modifica jerarquia.c para que acceda a los elementos en orden aleatorio (genera un arreglo de índices permutados). Mide y compara con el acceso secuencial del mismo tamaño.
4. Ejecuta matriz.c con N = 1024, 2048 y 4096. ¿Se mantiene la diferencia por filas y por columnas?
5. Consulta la caché de tu procesador con lscpu y /sys/devices/system/cpu/cpu0/cache/. Anota los tamaños y el tamaño de línea.
6. Usa perf stat sobre ./matriz para contar los fallos de caché de cada recorrido. ¿Cuántos fallos más tiene el recorrido por columnas?
7. Modifica matriz.c para transponer la matriz antes de recorrer por columnas (así el recorrido por columnas se vuelve secuencial en memoria). Mide la diferencia.