Saltar al contenido
wandres.dev
Iniciar sesión

Modelo por capas

La caché

El procesador no lee la memoria valor a valor. Cuando lee una dirección, trae a una memoria pequeña y muy rápida, la caché, un bloque entero de direcciones vecinas (típicamente 64 bytes). Leer algo que ya está en la caché es decenas de veces más rápido que ir a la memoria principal.

  • En un array, los valores siguientes están en el mismo bloque: un viaje a memoria trae varios valores. A esto se le llama localidad.
  • En una lista, el siguiente nodo puede estar en cualquier sitio: cada salto puede ser un viaje a memoria.

En la figura, el borde punteado rodea un bloque que la caché trae de una vez.

Un array y una lista frente a los bloques de la cachéArriba, un array con ocho valores contiguos (12, 7, 31, 9, 4, 15, 22 y 6) dentro de un solo bloque de caché de 64 bytes, con borde punteado: un viaje a memoria trae los ocho. Abajo, una lista con cuatro nodos (12, 7, 31 y 9), cada uno dentro de su propio bloque punteado, numerados del viaje 1 al 4: cada salto puede ser un viaje a memoria.Arrayviaje 1127319415226un bloque de 64 bytes: 8 valores de 8 bytes llegan juntosListaviaje 112viaje 27viaje 331viaje 49cada nodo está en un bloque distinto: un viaje por nodo
Borde punteado: un bloque que llega de la memoria a la caché. El array trae ocho valores por viaje; la lista, un nodo.

Es una capa nueva del modelo de costo: además de contar operaciones, importa dónde están los datos.

Un bloque de caché trae 64 bytes y cada entero del array ocupa 4. Recorriendo el array, ¿cuántos enteros consecutivos llegan con cada viaje a memoria?