El mismo total, mucho más lento
Una cadena de supermercados suma cada noche una tabla enorme de ventas. Un compañero cambia el orden de los dos bucles: ahora recorre la tabla por columnas en lugar de por filas.
El total sale igual, céntimo a céntimo. Pero el informe tarda varias veces más. El trabajo es el mismo y solo cambia el orden. La explicación está en la caché.
Al final de esta lección
Nota
Puedo explicar por qué una caché hace rápida la memoria.
Palabras clave
| Palabra | Qué significa | Ejemplo |
|---|---|---|
| Jerarquía de memoria | almacenes ordenados de pequeños y rápidos a grandes y lentos | |
| Caché | una memoria pequeña y rápida con copias de datos usados hace poco | |
| Línea de caché | el bloque de bytes que la caché copia de una vez | 64 bytes |
| Acierto | el dato buscado ya está en la caché | |
| Fallo | el dato hay que traerlo de una memoria más lenta | |
| Localidad | los programas suelen volver a usar datos, y datos guardados cerca |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
La memoria va por capas
Un procesador hace una suma en mucho menos de un nanosegundo. Leer la memoria principal tarda unas cien veces más.
Por eso los ordenadores tienen una jerarquía de memoria. Junto al procesador hay cachés pequeñas y rápidas: L1, después L2 y a menudo L3. Detrás está la memoria principal, y detrás de ella el disco. Cada capa es más grande y más lenta que la anterior.
Ejemplo resuelto: un portátil típico
| Capa | Tamaño típico | Tiempo de lectura aproximado |
|---|---|---|
| Registros | 32 de 8 bytes | Menos de 1 nanosegundo |
| Caché L1 | De 32 a 64 KB | Alrededor de 1 nanosegundo |
| Caché L2 | De cientos de KB a unos pocos MB | Unos pocos nanosegundos |
| Caché L3 | De varios MB a decenas de MB | De 10 a 20 nanosegundos |
| Memoria principal | Varios GB | Alrededor de 100 nanosegundos |
| SSD | Cientos de GB | Decenas de miles de nanosegundos |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Entra en la carpeta de arquitectura
cd ~/archSe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
¿Cuánto mide aquí una línea de caché?
getconf LEVEL1_DCACHE_LINESIZESe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Un fallo trae una línea entera
Una caché nunca copia un solo byte. En un fallo copia una línea de caché entera, casi siempre de 64 bytes, desde la capa de abajo.
Compensa gracias a la localidad. Un programa pronto lee datos guardados junto a lo que acaba de leer: es la localidad espacial. También vuelve a leer los mismos datos: es la localidad temporal. En los dos casos, la lectura siguiente es un acierto.
En loop.c gana el orden por filas
loop.c tiene una tabla de 4096 filas de 4096 int. Un int ocupa 4 bytes, así que una fila mide 16384 bytes y una línea de 64 bytes guarda 16 números.
Por filas, cada fallo trae los 16 números siguientes, así que 15 de cada 16 lecturas son aciertos. Por columnas, cada lectura está una fila entera más allá, en otra línea. Cuando el bucle vuelve a esa línea, ya no está en la caché.
Bytes de una fila, números de una línea
python3 -c "print(4096 * 4, 64 // 4)"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Compila el programa loop del laboratorio
gcc -O2 -o loop loop.cSe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Mide los dos órdenes
./loopSe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Un error frecuente
Advertencia
Mucha gente cree que el bucle lento debe de hacer más trabajo. No es así: los dos suman los mismos 16777216 números y dan la misma suma. La diferencia es cuántas veces espera el procesador a la memoria. Cuando un código va lento, cuenta los fallos además de los pasos.
Dónde va una línea en correspondencia directa
En una caché de correspondencia directa, cada dirección solo puede ir a una línea. Para saber cuál, parte la dirección en tres partes.
El desplazamiento es la dirección módulo el tamaño de línea: qué byte de la línea. Divide la dirección por el tamaño de línea y tienes el número de bloque. El índice es el bloque módulo el número de líneas: qué línea. La etiqueta es lo que queda, y dice qué bloque ocupa ahora esa línea.
Ejemplo resuelto: 4 líneas de 16 bytes
| Dirección | Bloque | Índice | Etiqueta | Resultado |
|---|---|---|---|---|
| 8 | 0 | 0 | 0 | Fallo: la línea 0 está vacía |
| 12 | 0 | 0 | 0 | Acierto |
| 36 | 2 | 2 | 0 | Fallo: la línea 2 está vacía |
| 72 | 4 | 0 | 1 | Fallo: sustituye al bloque 0 |
| 8 | 0 | 0 | 0 | Fallo: el bloque 0 ya no está |
| 40 | 2 | 2 | 0 | Acierto |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Parte 0x2f48 para 16 líneas de 64 bytes
python3 -c "print(0x2f48 % 64, 0x2f48 // 64 % 16, 0x2f48 // 1024)"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Para ir más lejos: una tabla más pequeña
Haz una copia de loop.c con una tabla de 1024 por 1024 escribiendo sed 's/4096/1024/' loop.c > cuarto.c. Compílala con gcc -O2 -o cuarto cuarto.c y ejecuta ./cuarto varias veces.
Antes de ejecutarla, predice la suma. Después compara la diferencia entre los dos órdenes con la de ./loop. Usa tu simulador para explicar lo que ves.