Arrays y caché: optimización de acceso O(1)

Optimización de arrays para minimizar fallos de caché

El acceso secuencial a los elementos de un array es 7–10 veces más rápido que el acceso aleatorio debido al funcionamiento de la memoria caché. Una sola línea de caché de 64 bytes carga 16 enteros secuenciales, lo que minimiza los fallos al usar el patrón de recorrido adecuado. El perfilado con perf stat revela el problema: 450k fallos-de-caché por 1M instrucciones indica un uso subóptimo de arrays incluso en tareas simples de procesamiento de paquetes.

Impacto del stride de acceso en el rendimiento

El stride de acceso determina la eficiencia de carga de las líneas de caché. Con stride 1, se utilizan completamente los 64 bytes y el prefetcher reconoce el patrón para acelerar la obtención de datos.

int sum = 0;
for (int i = 0; i < 8; i++) {
    sum += array[i];
}

Dicha secuencia toma 107 ciclos para 8 elementos (13.4 ciclos/elemento). El acceso aleatorio mediante índices eleva los costos a 800 ciclos (100 ciclos/elemento).

Benchmark en un array de 1M elementos:

• Stride 1: 1.2 ms (utilización 100% de la línea)
• Stride 2: 1.3 ms (utilización 50%)
• Stride 4: 1.5 ms
• Stride 8: 2.1 ms
• Stride 16: 3.8 ms (utilización 6.25%)
• Stride 64: 8.5 ms

Recomendación: stride ≤8 elementos para un rendimiento aceptable. La herramienta lmbench lat_mem_rd lo confirma: strides pequeños (128–512 bytes) mantienen los datos en L1 (3–4 ns), mientras que los grandes (64 KB) los envían a DRAM (100+ ns).

Arrays multidimensionales: el orden de recorrido es crítico

C utiliza el orden por filas: los elementos de una fila son contiguos en memoria. Recorrer por filas asegura acceso secuencial, mientras que por columnas introduce un stride de 16+ bytes.

int matrix[4][4] = {
    {0, 1, 2, 3},
    {4, 5, 6, 7},
    {8, 9, 10, 11},
    {12, 13, 14, 15}
};

Para una matriz de 1024×1024, el recorrido por filas toma 12 ms, mientras que por columnas 45 ms (3.75× más lento).

Optimización de la multiplicación de matrices

Orden ijk naive:

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        for (int k = 0; k < N; k++) {
            C[i][j] += A[i][k] * B[k][j];
        }
    }
}

Problema: B[k][j] se lee por columnas (stride N=1024, 4096 bytes). El orden ikj lo soluciona:

for (int i = 0; i < N; i++) {
    for (int k = 0; k < N; k++) {
        int r = A[i][k];
        for (int j = 0; j < N; j++) {
            C[i][j] += r * B[k][j];
        }
    }
}

Resultados para 512×512: ijk — 2450 ms, ikj — 680 ms (aceleración 3.6×).

Para matrices grandes — teselado con BLOCK_SIZE=64:

for (int ii = 0; ii < N; ii += BLOCK_SIZE) {
    for (int jj = 0; jj < N; jj += BLOCK_SIZE) {
        for (int kk = 0; kk < N; kk += BLOCK_SIZE) {
            for (int i = ii; i < min(ii + BLOCK_SIZE, N); i++) {
                for (int k = kk; k < min(kk + BLOCK_SIZE, N); k++) {
                    int r = A[i][k];
                    for (int j = jj; j < min(jj + BLOCK_SIZE, N); j++) {
                        C[i][j] += r * B[k][j];
                    }
                }
            }
        }
    }
}

Los bloques caben en L1, con reutilización de datos. Para 1024×1024: 1800 ms (10× más rápido que el naive).

AoS vs SoA: organización de datos

Array de Estructuras (AoS) agrupa los campos de las partículas, pero una línea de caché contiene datos sin usar (utilización 37.5%).

typedef struct {
    float x, y, z;
    float vx, vy, vz;
    float mass;
    int id;
} particle_t;

Estructura de Arrays (SoA) separa por tipo:

typedef struct {
    float x[1000], y[1000], z[1000];
    float vx[1000], vy[1000], vz[1000];
    float mass[1000];
    int id[1000];
} particles_t;

Las actualizaciones de posición en SoA utilizan las líneas de caché al 100%. Benchmark con 1M partículas, 1000 iteraciones: AoS — 2850 ms, SoA — 1200 ms (aceleración 2.4×).

Lecciones clave

• El acceso secuencial a arrays minimiza los fallos de caché 7+ veces en comparación con el aleatorio
• Stride de acceso ≤8 elementos asegura >90% de utilización de la línea de caché
• El orden por filas en C requiere recorrido por filas; el acceso por columnas lo ralentiza 3–4 veces
• Cambiar el orden de los bucles en operaciones matriciales da una aceleración de 3–4×
• SoA supera a AoS con procesamiento SIMD y acceso frecuente a subconjuntos de campos

— Editorial Team