English · Español

Break — Reventar la cache L1 con un cambio de stride

Una sola línea cambia el paso de un bucle de 1 a 1024 y la velocidad cae más de 10×. Sirve para ver la latencia de la memoria, no leerla en una tabla.

Este /break es para el lab de cache-walk (lab/02-cache-walks.md). Enseña haciendo deliberadamente que la memoria sea el cuello de botella y luego observando el reloj de pared.

Hipótesis

El aprendiz predice: "Incrementar el stride de la suma de un array de 1M doubles de 1 a 1024 incrementará el tiempo de pared al menos en un orden de magnitud, aunque el número de sumas realizadas caiga 1024×."

La idea es que menos sumas por segundo pueden ser más lentas en tiempo de pared, porque cada suma cuesta ahora una traída completa de cache line desde DRAM.

El break

En tu script de cache-walk (benchmarks/cache_walk.py si escribiste uno en el lab 02, o un archivo fresco en otro caso), cambia el stride del bucle interno de 1 a 1024:

-for i in range(0, N):
+for i in range(0, N, 1024):
     total += arr[i]

No reduzcas N a la vez — el objetivo es mantener el tamaño del array fijo y solo variar el patrón de acceso.

Procedimiento de ejecución

uv run python -c "
import time, numpy as np
N = 1 << 22  # 4M doubles = 32 MiB, cómodamente mayor que L2
arr = np.ones(N, dtype=np.float64)

for stride in (1, 8, 64, 512, 1024):
    t0 = time.perf_counter()
    s = 0.0
    for i in range(0, N, stride):
        s += arr[i]
    dt = time.perf_counter() - t0
    elems = N // stride
    print(f'stride={stride:5d}  elems={elems:8d}  wall={dt*1000:8.2f} ms  ns/elem={dt*1e9/elems:7.1f}')
"

Nota: un bucle puro de Python está bien aquí porque el objetivo es aislar la latencia de memoria, no medir el throughput pico. (Para una versión vectorizada, usa arr[::stride].sum() — pero entonces el overhead del intérprete de Python desaparece y puede que quieras un numba.njit para hacer aflorar el efecto del stride limpiamente.)

Modo de fallo esperado

En el i5-8250U (L1d = 32 KiB, L2 = 256 KiB, L3 = 6 MiB, latencia DRAM ~80 ns):

• stride=1 — secuencial, prefetcher-friendly. ns/elem ≈ 3–5 ns (el bucle de Python es el cuello de botella, no la memoria).
• stride=8 — un elemento por línea de 64 bytes, prefetcher todavía activo. ns/elem ≈ 10–20 ns.
• stride=64 — ocho elementos por línea saltados, rango medio. ns/elem ≈ 50–80 ns.
• stride=1024 — cada elemento en una página distinta; la TLB empieza a fallar. ns/elem ≈ 200–400 ns.

La caída del tiempo de pared es la sorpresa: stride 1024 visita 1024× menos elementos pero cada uno es ~100× más lento por visita, así que el tiempo de pared disminuye solo ~10×, no 1024×.

Diagnóstico

Solo desde los logs, la pista clave es la columna ns/elem subiendo a medida que crece el stride. Un modelo mental ingenuo (erróneo) predeciría que ns/elem sea aproximadamente constante a través de los strides — eso solo es cierto mientras estás dentro de L1.

Comprueba de forma cruzada con perf stat si está disponible:

perf stat -e cache-misses,cache-references uv run python your_script.py

Una subida 10× en la tasa de cache-miss confirma el diagnóstico: la memoria es el cuello de botella, no el bucle.

Lección

Dos lecciones en una:

1. "Menos trabajo" no es siempre "menos tiempo". Cuando el trabajo está dominado por accesos a memoria, el patrón de accesos empequeñece al recuento. Secuencial bate a strided incluso cuando strided hace 1000× menos aritmética.
2. Los precipicios L1 / L2 / L3 / DRAM son reales. No son abstracciones de libro de texto — los acabas de medir con un cronómetro en tu portátil.

Cuando el lab de matmul de la Fase 3 te pida comparar un matmul con orden de bucle traspuesto con un matmul tileado, ya sabrás por qué la diferencia es tan grande: es este experimento escrito ligeramente más grande.

Referencias

• Drepper, What Every Programmer Should Know About Memory (2007) — la referencia canónica, esp. §3 (jerarquía de cache).
• Intel 64 and IA-32 Architectures Optimization Reference Manual, §2.5 (organización de cache en Skylake/Kaby Lake).