... 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érminoInglésSignificado
Acierto de cachéCache HitLos datos solicitados por la CPU se encuentran justamente en la caché; se usan directamente.
Fallo de cachéCache MissLos datos solicitados por la CPU no están en la caché; deben cargarse desde el siguiente nivel de almacenamiento (más lento).
Tasa de aciertosHit RateNúmero de aciertos / número total de accesos; cuanto más alta, mejor (el valor ideal se acerca al 100%).
Penalización por falloMiss PenaltyTiempo adicional necesario para cargar datos desde el siguiente nivel después de un fallo.
Tiempo de aciertoHit TimeTiempo 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]:

PasoDirección accedidaEstado de la caché (antes del acceso)ResultadoMotivo
110[]FalloLa caché está vacía; la dirección 10 no está.
220[10]FalloLa dirección 20 no está en la caché.
310[10, 20]Acierto¡La dirección 10 está en la caché! (localidad temporal)
430[10, 20]FalloLa dirección 30 no está en la caché.
510[10, 20, 30]AciertoLa 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 astudent.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é.

EstrategiaInglésReglaEvaluación
Menos recientemente usadoLRU (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 salirFIFO (First In First Out)Desaloja el dato que entró primero en la caché.Simple pero de rendimiento medio.
Menos frecuentemente usadoLFU (Least Frequently Used)Desaloja el dato con menos accesos.Amigable con los datos calientes, pero los datos antiguos pueden «negarse a irse».
Reemplazo aleatorioRandomElige 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)}))
ejemplo Simulador en tiempo real de aciertos/fallos de caché — demostración animada + curva de tasa de aciertos con Chart.js

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.

Izquierda: zona de simulación
Puntos de vista previa de la secuencia de acceso
Dirección de acceso actual
Dirección de acceso actual:--
Indicador de resultado de acierto/fallo
Listo
Cuadrícula de 4 ranuras de caché
Ranura 1Vacío
Ranura 2Vacío
Ranura 3Vacío
Ranura 4Vacío
Botones de control
Derecha: estadísticas + gráficos
Estadísticas de aciertos/fallos/tasa de aciertos
Número de aciertos0
Número de fallos0
Tasa de aciertos--
Curva de evolución de la tasa de aciertos con Chart.js

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:

TipoInglésCuándo ocurre¿Se puede evitar?
Fallo forzosoCompulsory 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 capacidadCapacity MissEl 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 conflictoConflict MissDiferentes 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)
Otras extensiones