Jerarquía de memoria y caché

Un acceso a un registro tarda un ciclo; uno a la memoria principal, unos trescientos. Si el procesador esperara esa cuenta cada vez, su velocidad no importaría. La jerarquía de memoria existe para que, casi siempre, no tenga que esperar.

Los niveles, de chico y rápido a grande y lento

Los niveles van de chico y rápido a grande y lento: registros, caché L1 de decenas de kilobytes, L2 de cientos, L3 compartida de varios megabytes, memoria principal de gigabytes, disco.

Cada salto hacia abajo es aproximadamente un orden de magnitud más lento y varios órdenes más grande. La ilusión que se busca es tener la velocidad del nivel más rápido con la capacidad del más grande, y funciona por una propiedad de los programas reales, no por magia.

La localidad, que es por qué funciona

Esa propiedad es la localidad. Temporal: lo que se usó hace poco probablemente se use de nuevo —una variable dentro de un ciclo—. Espacial: lo que está cerca de lo que se usó probablemente se use también —el elemento siguiente de un arreglo—.

Por eso la caché no trae el byte pedido sino una línea completa, típicamente 64 bytes. Si el programa tiene localidad espacial, esos bytes extra van a hacer falta enseguida y ya están ahí.

Cómo ubica la caché cada línea

Cada línea de caché se ubica según su dirección. En el esquema asociativo por conjuntos, la dirección determina un conjunto y dentro de él la línea puede ir en cualquiera de las vías. Al llenarse, se desaloja alguna, en general la menos usada recientemente.

Eso trae un efecto poco intuitivo: recorrer un arreglo con un paso que coincide con el tamaño del conjunto hace que todos los accesos caigan en el mismo lugar y se desalojen entre sí. Es el conflicto por falta de asociatividad, y explica caídas de rendimiento con tamaños que son potencias de dos.

Qué cambia esto en el código de todos los días

De acá sale la diferencia práctica más citada. Recorrer un arreglo aprovecha cada línea completa; recorrer una lista enlazada salta por la memoria y cada nodo suele ser una línea nueva. Con la misma complejidad asintótica, la diferencia real puede ser de diez veces.

Lo mismo con una matriz: recorrerla por filas sigue el orden en que está guardada, por columnas salta el ancho de una fila en cada paso. Cambiar el orden de dos ciclos anidados es de las optimizaciones más rentables que existen, y no cambia una sola línea de lógica.

Las escrituras tienen su propia mecánica

Las escrituras agregan su propia mecánica. En escritura diferida, el dato se modifica en la caché y baja a memoria al desalojarse: más rápido, y exige marcar la línea como sucia.

En sistemas multinúcleo aparece el problema de coherencia: dos núcleos con copias de la misma línea. Los protocolos lo resuelven invalidando copias, y de ahí sale un problema con nombre propio: la falsa compartición. Dos hilos que escriben variables distintas que cayeron en la misma línea se invalidan mutuamente todo el tiempo, sin compartir nada en realidad. Se arregla separando esos datos con relleno.

Esto se mide, no se adivina

Todo esto se mide, no se adivina. Los contadores de rendimiento del procesador reportan fallos de caché por nivel, y ahí se ve si el problema es el algoritmo o el acceso a memoria.

La regla práctica para diseñar: agrupar lo que se usa junto, recorrer de forma secuencial, preferir estructuras compactas. Muchas veces conviene un arreglo de estructuras chicas antes que punteros a objetos dispersos, aunque el segundo se vea más ordenado en el código.

Los números que conviene tener en la cabeza

Cierre

Niveles cada vez más grandes y lentos, y localidad temporal y espacial como apuesta. La caché trae líneas enteras: por eso el acceso secuencial gana, recorrer una matriz por filas gana, y dos hilos escribiendo en la misma línea se estorban aunque no compartan variables.