... están contiguos en memoria.
Cuando la CPU necesita datos, primero va a la caché a buscarlos. Si los encuentra, todos contentos — pero ¿y si no los encuentra?
En esta lección comprenderás el mecanismo central del funcionamiento de la caché, así como el principio clave que la hace eficaz:El principio de localidad。
Analogía cotidiana: el escritorio en la biblioteca
Estás escribiendo una tesis en la biblioteca. En el escritorio caben como máximo 4 libros — esto es tu«caché», de capacidad muy pequeña pero al alcance de la mano.
Cuando necesitas un libro, primero miras si está en el escritorio:
- En el escritorio (acierto de caché): lo abres directamente y lo usas, cero espera.
- No está en el escritorio (fallo de caché): te levantas a buscarlo en la estantería, lo traes y lo pones en el escritorio. Si el escritorio está lleno, tienes que devolver a la estantería el libro que llevas más tiempo sin consultar.
Esta sencilla regla es precisamente la esencia de los sistemas de caché informáticos:«Lo usado recientemente se queda, lo que no se usa con frecuencia se elimina»。
Yendo más lejos, descubrirás que al escribir una tesis no hojeas libros irrelevantes al azar. Durante un período de tiempo consultas repetidamente el mismo conjunto de materiales de referencia. De los miles de libros en las estanterías de la biblioteca, quizás solo tocas veinte o treinta. Esto es elprincipio de localidaden acción.
Concepto central: aciertos y fallos de caché
Terminología básica
| Término | Inglés | Significado |
|---|---|---|
| Acierto de caché | Cache Hit | Los datos solicitados por la CPU se encuentran justamente en la caché; se usan directamente. |
| Fallo de caché | Cache Miss | Los datos solicitados por la CPU no están en la caché; deben cargarse desde el siguiente nivel de almacenamiento (más lento). |
| Tasa de aciertos | Hit Rate | Número de aciertos / número total de accesos; cuanto más alta, mejor (el valor ideal se acerca al 100%). |
| Penalización por fallo | Miss Penalty | Tiempo adicional necesario para cargar datos desde el siguiente nivel después de un fallo. |
| Tiempo de acierto | Hit Time | Tiempo requerido para leer datos cuando la caché acierta. |
Un ejemplo sencillo
Supongamos que la caché tiene 3 ranuras y la CPU accede secuencialmente a las direcciones [10, 20, 10, 30, 10]:
| Paso | Dirección accedida | Estado de la caché (antes del acceso) | Resultado | Motivo |
|---|---|---|---|---|
| 1 | 10 | [] | Fallo | La caché está vacía; la dirección 10 no está. |
| 2 | 20 | [10] | Fallo | La dirección 20 no está en la caché. |
| 3 | 10 | [10, 20] | Acierto | ¡La dirección 10 está en la caché! (localidad temporal) |
| 4 | 30 | [10, 20] | Fallo | La dirección 30 no está en la caché. |
| 5 | 10 | [10, 20, 30] | Acierto | La dirección 10 acierta de nuevo. |
De 5 accesos, hay 2 aciertos; tasa de aciertos = 40%. Aunque no es alta, ya demuestra el principio de la caché.
Por qué la caché es eficaz: el principio de localidad
Si el acceso de un programa a la memoria fuera completamente aleatorio, la caché sería casi inútil — apenas se carga algo, ya no se necesita.
Pero el comportamiento de los programas reales no es aleatorio. Muestran una fuertelocalidad (Locality), y esta es la razón fundamental de que la caché sea eficaz.
Localidad temporal (Temporal Locality)
Si se accede a un dato, es muy probable que se vuelva a acceder a él en un futuro próximo.
Escenarios típicos:
- Variables en bucles:
for i in range(1000000): total += i— la variableiytotalse accede a ella un millón de veces en poco tiempo. - Código caliente (hot spot) de funciones: el 20% del código de un programa se ejecuta durante el 80% del tiempo; estas instrucciones se reacceden con frecuencia.
- Parámetros de funciones llamadas con frecuencia: las variables locales de funciones recursivas se acumulan en la pila en cada llamada.
Localidad espacial (Spatial Locality)
Si se accede a un dato, es muy probable que también se acceda a los datos cercanos a él.
Escenarios típicos:
- Recorrido secuencial de arrays:
for i in range(len(arr)): sum += arr[i]— arr - Campos de estructuras/objetos: al acceder a
student.namedespués, es muy probable que se acceda astudent.age, están adyacentes en memoria. - Instrucciones ejecutadas en secuencia: cuando la CPU ejecuta la instrucción en la dirección 100, la siguiente con alta probabilidad es la instrucción en la dirección 104.
Visualización de los dos tipos de localidad
时间局部性示意图:
时间轴: t1 t2 t3 t4 t5 t6 t7 t8
访问地址: A B A C A D B A
|_____|_____|_____|
地址 A 在短时间内被多次访问——时间局部性
空间局部性示意图:
内存地址: 100 104 108 112 116 120 124 128
访问顺序: *1 *2 *3 *4 *5
|_____________________________|
连续访问相邻地址——空间局部性
Las CPU modernas aprovechan precisamente la localidad espacial para mejorar el rendimiento: al cargar desde la memoria los datos de la dirección 100, también se cargan en la caché las direcciones 100~164 (una línea de caché completa, normalmente 64 bytes). De este modo, al acceder a la dirección 104, ya está en la caché.
Política de reemplazo de caché: ¿qué hacer cuando está llena?
Los espacios de la caché son limitados; cuando la caché está llena y llegan nuevos datos, es necesariodesalojar un dato antiguo. Esta decisión de «a quién desalojar» es la política de reemplazo de caché.
| Estrategia | Inglés | Regla | Evaluación |
|---|---|---|---|
| Menos recientemente usado | LRU (Least Recently Used) | Desaloja el dato que lleva más tiempo sin ser accedido. | El más usado; funciona muy bien. |
| Primero en entrar, primero en salir | FIFO (First In First Out) | Desaloja el dato que entró primero en la caché. | Simple pero de rendimiento medio. |
| Menos frecuentemente usado | LFU (Least Frequently Used) | Desaloja el dato con menos accesos. | Amigable con los datos calientes, pero los datos antiguos pueden «negarse a irse». |
| Reemplazo aleatorio | Random | Elige uno al azar para desalojar. | El más simple de implementar, con buenos resultados. |
El LRU es el que mejor funciona en la práctica porque aprovecha directamente la localidad temporal: «lo que no se ha usado recientemente, probablemente tampoco se use en el corto plazo».
Las cachés reales de CPU suelen usar variantes aproximadas de LRU (como el pseudo-LRU) para reducir la complejidad de la implementación en hardware.
Demostración interactiva: Simulador de caché LRU
El siguiente programa en Python simula por completo el proceso de funcionamiento de una caché LRU. Puedes modificar la secuencia de accesos y la capacidad de la caché para observar cómo cambia la tasa de aciertos.
Ejemplo
Simulador de caché LRU (demostración de ejemplo)
Funciones:
1. Simular la secuencia de accesos de la CPU a direcciones de memoria.
2. Usar la estrategia LRU para gestionar la caché.
3. Marcar en tiempo real si cada acceso es «acierto» o «fallo».
4. Calcular y mostrar la tasa de aciertos.
"""
from collections import OrderedDict
class LRUCache:
"""
Simulador de caché LRU (Least Recently Used, menos recientemente usado)
Usa OrderedDict para mantener el orden de acceso; cuanto más cerca del final, más reciente es el acceso.
"""
def __init__(self, capacity):
"""
Inicializar la caché
:param capacity: Capacidad de la caché (número de entradas que puede almacenar).
"""
self.capacity = capacity
self.cache = OrderedDict() # Diccionario ordenado: key=dirección, value=dato
self.hits = 0 # Contador de aciertos
self.misses = 0 # Contador de fallos
self.evictions = 0 # Contador de desalojos
def access(self, address):
"""
Simular un acceso a memoria
:param address: La dirección de memoria a la que se va a acceder.
:return: (result_str, is_hit)
"""
if address in self.cache:
# ¡Acierto de caché!
self.hits += 1
# Estrategia LRU: mover la entrada acertada al final (marcada como usada recientemente).
self.cache.move_to_end(address)
return "HIT", True
else:
# Fallo de caché
self.misses += 1
evicted = None
if len(self.cache) >= self.capacity:
# La caché está llena; hay que desalojar la entrada menos usada recientemente (la primera del OrderedDict).
evicted_addr, _ = self.cache.popitem(last=False)
self.evictions += 1
evicted = evicted_addr
# Cargar el nuevo dato desde el «siguiente nivel de almacenamiento» (simulado como obtención directa del dato).
data = f"DATA_AT_{address}"
self.cache[address] = data
return "MISS", False
def hit_rate(self):
"""Calcula la tasa de aciertos actual (porcentaje)."""
total = self.hits + self.misses
if total == 0:
return 0.0
return (self.hits / total) * 100
def current_state(self):
"""Devuelve el contenido actual de la caché (del más antiguo al más reciente)."""
return list(self.cache.keys())
def run_simulation(access_sequence, cache_capacity):
"""
Ejecutar una simulación completa de caché
:param access_sequence: La secuencia de accesos a memoria a simular (lista de enteros).
:param cache_capacity: Capacidad de la caché.
"""
cache = LRUCache(cache_capacity)
print("=" * 70)
print(fSimulador de caché LRU de EJEMPLO)
print(f)
print(fporque cambia de fila))
print("=" * 70)
print(f{'Paso':<6} {'Dirección':<8} {'Resultado':<8} {'Estado de caché (antiguo→nuevo)':<40})
print("-" * 70)
for i, addr in enumerate(access_sequence, 1):
result, is_hit = cache.access(addr)
state = cache.current_state()
hit_mark = "HIT [OK]" if is_hit else "MISS X"
print(f"{i:<6} {addr:<8} {hit_mark:<8} {str(state):<40}")
# Salida de estadísticas
print("-" * 70)
print(f"\nResultados de la estadística:)
print(fAciertos (Hits) : {cache.hits})
print(fFallos (Misses): {cache.misses})
print(fDesalojos (Evictions): {cache.evictions})
print(fTasa de aciertos (Hit Rate) : {cache.hit_rate():.1f}%)
print()
return cache
# ============================================================
# Demostración 1: Comportamiento básico de LRU
# ============================================================
print("\n>>> Demostración 1: Comportamiento básico de caché LRU)
print(La secuencia de acceso muestra localidad temporal: la dirección 10 se accede repetidamente\n")
run_simulation(
access_sequence=[10, 20, 10, 30, 40, 10, 20, 50, 10, 20],
cache_capacity=4
)
# ============================================================
# Demostración 2: Efecto de la capacidad de caché en la tasa de aciertos
# ============================================================
print("\n>>> Demostración 2: Efecto de la capacidad de caché en la tasa de aciertos)
print(La misma secuencia de acceso con diferentes capacidades de caché\n")
test_sequence = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5,
1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7]
print(fLongitud de la secuencia de acceso: {len(test_sequence)})
print(f{'Capacidad':<8} {'Aciertos':<8} {'Fallos':<8} {'Tasa de aciertos':<10})
print("-" * 35)
for cap in [1, 2, 3, 4, 5, 8, 16]:
c = LRUCache(cap)
for addr in test_sequence:
c.access(addr)
print(f"{cap:<8} {c.hits:<8} {c.misses:<8} {c.hit_rate():<8.1f}%")
# ============================================================
# Demostración 3: Comparación entre 'acceso aleatorio' vs 'acceso con localidad'
# ============================================================
print("\n>>> Demostración 3: Acceso con localidad vs acceso aleatorio)
print(La misma capacidad de caché (8), diferencia en la tasa de aciertos bajo diferentes patrones de acceso\n")
import random
random.seed(42)
# Modo A: Acceso con localidad (simula recorrido cíclico de un array)
local_access = []
for _ in range(20):
# En cada ciclo, se accede consecutivamente en el rango 0-15 y luego se salta
base = random.randint(0, 50)
for offset in range(5):
local_access.append(base + offset)
# Modo B: Acceso completamente aleatorio
random_access = [random.randint(0, 100) for _ in range(100)]
for label, seq in [(Acceso con localidad, local_access), (Acceso aleatorio, random_access)]:
c = LRUCache(8)
for addr in seq:
c.access(addr)
print(f{label}: tasa de aciertos = {c.hit_rate():.1f}% (total de accesos {len(seq)}))
Demostración interactiva: Simulación en tiempo real de aciertos / fallos de caché
Genera aleatoriamente una secuencia de accesos a memoria con localidad (30 accesos), demuestra animadamente cada búsqueda en caché, calcula en tiempo real la tasa de aciertos y dibuja la curva de evolución.
Si ejecutas este código, notarás:
- Cuanto mayor es la capacidad de caché, mayor es la tasa de aciertos, pero la mejora disminuye gradualmente (efecto marginal).
- El patrón de acceso con localidad tiene una tasa de aciertos mucho mayor que el acceso aleatorio.— esta es la razón por la que el caché es efectivo.
- Con la política LRU, las direcciones accedidas repetidamente permanecen en la caché y casi nunca son expulsadas.
Los tres tipos de fallos de caché
No todos los 'fallos de caché' son iguales. Los ingenieros de hardware los dividen en tres categorías:
| Tipo | Inglés | Cuándo ocurre | ¿Se puede evitar? |
|---|---|---|---|
| Fallo forzoso | Compulsory Miss (Cold Miss) | Al acceder por primera vez a un dato, aún no está en la caché. | Inevitable (el primer acceso siempre es en frío). |
| Fallo de capacidad | Capacity Miss | El conjunto de trabajo (los datos usados activamente por el programa) es mayor que la capacidad de la caché. | Aumentar la caché o reducir el conjunto de trabajo. |
| Fallo de conflicto | Conflict Miss | Diferentes direcciones se asignan a la misma posición en la caché (común en caché de asignación directa). | Usar asignación asociativa por conjuntos o totalmente asociativa. |
Para los programadores comunes, se interactúa más con los dos primeros tipos:
- Fallo forzoso: No se puede evitar, pero cuanto más tiempo se ejecute tu programa, menor será su impacto.
- Fallo de capacidad: Se puede mitigar optimizando el tamaño de las estructuras de datos y los patrones de acceso. Por ejemplo, usar tipos de datos más compactos y procesar arrays grandes por bloques.
Entender los fallos de caché es clave para escribir código de alto rendimiento. Una regla simple: intenta que tus patrones de acceso a datos sean amigables con la caché: al recorrer un array, accede en el orden del diseño de memoria, evita accesos saltarines y mantén juntos en memoria los datos que se usan con frecuencia.
Práctica de programación: código amigable con la caché
Veamos un ejemplo clásico: al recorrer un array bidimensional, recorrer por filas vs recorrer por columnas tiene una enorme diferencia de rendimiento.
Ejemplo
Recorrido de arrays amigable vs no amigable con la caché (demostración de ejemplo)
Demuestra cómo diferentes formas de acceder a los mismos datos afectan el rendimiento de la caché.
"""
import time
# La forma en que Python almacena las listas: array bidimensional = lista de listas
# En arr[i][j], arr[i] es una fila completa, contigua en memoria
# Por tanto, recorrer por filas = amigable con la caché; recorrer por columnas = no amigable con la caché.
def traverse_row_major(arr):
"""
Recorrido por filas: primero se fija el índice de fila i, luego se recorren las columnas j.
Patrón de acceso: arr
Diseño de memoria: estos elementos son contiguos en memoria -- ¡buena localidad espacial!
"""
total = 0
rows = len(arr)
cols = len(arr[0])
for i in range(rows):
for j in range(cols):
total += arr[i][j]
return total
def traverse_column_major(arr):
"""
Recorrido por columnas: primero se fija el índice de columna j, luego se recorren las filas i.
Patrón de acceso: arr
Diseño de memoria: estos elementos saltan por la memoria -- ¡mala localidad espacial!
"""
total = 0
rows = len(arr)
cols = len(arr[0])
for j in range(cols):
for i in range(rows):
total += arr[i][j]
return total
# Crear un array grande (1000 x 1000)
SIZE = 1000
print(fCreando array bidimensional de {SIZE}x{SIZE}...)
arr = [[i * SIZE + j for j in range(SIZE)] for i in range(SIZE)]
# Primero calentar para evitar sesgo de arranque en frío
traverse_row_major(arr)
traverse_column_major(arr)
# Prueba formal
print("\nIniciando comparación de rendimiento (promedio de 3 ejecuciones):)
print("-" * 50)
def benchmark(func, arr, trials=3):
"""Promediar el tiempo de varias ejecuciones"""
times = []
for _ in range(trials):
start = time.perf_counter()
func(arr)
elapsed = time.perf_counter() - start
times.append(elapsed)
return sum(times) / len(times)
row_time = benchmark(traverse_row_major, arr)
col_time = benchmark(traverse_column_major, arr)
print(fRecorrido por filas (amigable con caché): {row_time:.4f} segundos)
print(fRecorrido por columnas (no amigable con caché): {col_time:.4f} segundos)
print(fPor columnas es más lento que por filas: {col_time / row_time:.1f} veces)
print()
print(Análisis de causa:)
print(Al recorrer por filas, arr[i])
print(Al acceder por primera vez a arr[i])
print(Los accesos posteriores a arr[i])
print()
print(Al recorrer por columnas, arr)
print(Casi cada acceso requiere cargar desde memoria, la tasa de aciertos de caché es muy baja.)
# Complemento: prueba simple - usar id() de Python para verificar direcciones de memoria
print("\nVerificación del diseño de memoria (demostración con array pequeño):)
small = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(fid de arr)
print(fid de arr)
print(fid de arr)
print(fid de arr)