Localidad y rendimiento

1. El problema: el orden importa

Dos programas que hacen exactamente el mismo número de operaciones pueden tener rendimientos muy distintos si acceden a la memoria en distinto orden. La diferencia puede ser de 10x, 50x o más. La causa es la localidad: la caché y la TLB premian los accesos predecibles y castigan los aleatorios.

Este es uno de los temas más importantes para el rendimiento de software. Entender la localidad es la base de la optimización de alto rendimiento.

2. Localidad espacial y temporal

La localidad se divide en dos tipos (tema 4):

• Localidad temporal: si accedes a un dato, es probable que lo vuelvas a usar pronto. Ejemplo: una variable en un bucle.
• Localidad espacial: si accedes a un dato, es probable que accedas pronto a los datos cercanos en memoria. Ejemplo: recorrer un arreglo.

La caché explota ambas: guarda líneas de 64 bytes (localidad espacial) y las retiene (localidad temporal). La TLB explota la localidad espacial: si accedes a una página, es probable que accedas a las páginas cercanas.

3. Recorrer una matriz: por filas vs por columnas

En C, las matrices se almacenan en row-major (por filas): los elementos de una fila están contiguos en memoria. Recorrer por filas es secuencial (buena localidad espacial); recorrer por columnas salta por memoria (mala localidad).

4. El efecto de la caché y la TLB

El recorrido por filas aprovecha la localidad espacial: cada línea de caché de 64 bytes contiene 16 enteros, y se traen de una vez. El recorrido por columnas salta N enteros cada vez, cayendo en líneas distintas, provocando fallos de caché y de TLB.

Además, la TLB sufre: el recorrido por columnas accede a una página distinta en cada paso (si N × 4 bytes ≥ 4096), causando fallos de TLB.

El efecto se amplifica con el tamaño de la matriz: para matrices que no caben en la caché, la diferencia es enorme.

5. Ejemplo numérico

Matriz de 4096×4096 enteros (4 bytes cada uno) = 64 MiB. Caché L1 de 32 KiB (8192 enteros, 512 líneas de 64 B). Recorrido por filas:

• Cada línea de caché contiene 16 enteros contiguos.
• Se recorren 4096 enteros por fila: 4096/16 = 256 líneas por fila.
• La fila completa (16 KiB) no cabe en la L1, pero el prefetch por hardware trae las líneas por adelantado.
• Tiempo: ~0,04 s (con prefetch).

Recorrido por columnas:

• Cada acceso salta 4096 enteros (16 KiB), cayendo en una línea distinta.
• Casi ningún acierto de caché ni de TLB.
• Tiempo: ~3 s (70× más lento).

6. Experimento en C

El programa siguiente mide el tiempo de recorrer una matriz por filas y por columnas:

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static double ahora(void) { struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t); return t.tv_sec + t.tv_nsec/1e9; }

int main(void)
{
    const int N = 4096;
    int *m = calloc((size_t)N * N, sizeof *m);
    volatile long s = 0;
    double t;

    t = ahora();
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) s += m[i*N + j];
    printf("por filas:    %.3f s\\n", ahora() - t);

    t = ahora();
    for (int j = 0; j < N; j++)
        for (int i = 0; i < N; i++) s += m[i*N + j];
    printf("por columnas: %.3f s\\n", ahora() - t);

    free(m);
    return 0;
}

$ gcc -std=c17 -O2 -Wall -Wextra -o matriz matriz.c
$ ./matriz
por filas:    0,041 s
por columnas: 2,980 spor columnas: 2,980 s

El mismo número de sumas (16 millones) tarda 70 veces más por columnas, porque cada acceso salta N enteros (16 KiB) y casi nunca acierta en la caché. Recorrer por filas aprovecha la localidad espacial: cada línea de 64 bytes contiene 16 enteros consecutivos y se traen de una vez.

7. Optimizaciones: blocking y transposición

Cuando no se puede cambiar el orden de acceso (ej. multiplicación de matrices), se usan técnicas para mejorar la localidad:

• Blocking (tiling): dividir la matriz en bloques que caben en la caché y procesar bloque por bloque. Mejora la localidad temporal y espacial.
• Transposición: reordenar los datos para que el acceso sea secuencial.
• Prefetching: traer datos por adelantado (manual o por hardware).

Ejemplo de blocking para multiplicación de matrices:

for (int ii = 0; ii < N; ii += B)
  for (int jj = 0; jj < N; jj += B)
    for (int kk = 0; kk < N; kk += B)
      for (int i = ii; i < ii+B; i++)
        for (int j = jj; j < jj+B; j++)
          for (int k = kk; k < kk+B; k++)
            C[i*N+j] += A[i*N+k] * B[k*N+j];

El tamaño del bloque B se elige para que quepa en la caché L1 o L2. Esto puede acelerar la multiplicación en un factor de 5-10.

8. Probar con un simulador

Este simulador estima el tiempo de recorrer una matriz según el tamaño, el orden (filas/columnas) y el tamaño de la caché.

9. En Linux: perf

$ perf stat -e cache-references,cache-misses,L1-dcache-load-misses ./matriz
$ perf stat -e dTLB-load-misses,dTLB-loads ./matriz

• cache-references, cache-misses: referencias y fallos de caché.
• L1-dcache-load-misses: fallos de caché L1 de datos.
• dTLB-load-misses, dTLB-loads: fallos y accesos a la TLB de datos.
• Comparar los resultados por filas y por columnas muestra el efecto de la localidad.

10. Resumen

• El orden de acceso a la memoria afecta drásticamente al rendimiento.
• La localidad espacial y temporal son la base de la caché y la TLB.
• Recorrer una matriz por filas (row-major en C) es secuencial y rápido.
• Recorrer por columnas salta por memoria y es lento (fallos de caché y TLB).
• Blocking y transposición mejoran la localidad cuando no se puede cambiar el orden.
• perf stat permite medir los fallos de caché y TLB.

11. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Ejecuta matriz.c con N = 1024, 2048 y 4096. ¿Se mantiene la diferencia?
2. Usa perf stat sobre ./matriz para contar los fallos de caché de cada recorrido.
3. Implementa el blocking para la multiplicación de matrices y mide la mejora.
4. Transpone la matriz antes de recorrer por columnas y mide la diferencia.
5. Explica por qué el prefetching por hardware ayuda al recorrido por filas.
6. Compara el rendimiento con -O0 y -O2. ¿Cambia la diferencia?
7. Dibuja el patrón de acceso a memoria para una matriz 4×4 por filas y por columnas.