Tableaux et cache : optimisation d'accès O(1)

Optimiser les tableaux pour minimiser les défauts de cache

L'accès séquentiel aux éléments d'un tableau est 7 à 10 fois plus rapide que l'accès aléatoire en raison du fonctionnement de la mémoire cache. Une seule ligne de cache de 64 octets charge 16 entiers séquentiels, ce qui minimise les défauts de cache lorsqu'on utilise le bon schéma de traversée. Le profilage avec perf stat met en évidence le problème : 450k cache-misses pour 1M d'instructions indiquent une utilisation sous-optimale des tableaux même dans des tâches simples de traitement de paquets.

Impact du pas d'accès sur les performances

Le pas d'accès détermine l'efficacité de chargement des lignes de cache. Avec un pas de 1, les 64 octets sont pleinement utilisés, et le préchargeur reconnaît le schéma pour accélérer la récupération.

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

Une telle séquence prend 107 cycles pour 8 éléments (13,4 cycles/élément). L'accès aléatoire par indices fait grimper le coût à 800 cycles (100 cycles/élément).

Benchmark sur un tableau de 1M d'éléments :

• Pas 1 : 1,2 ms (utilisation 100 % des lignes)
• Pas 2 : 1,3 ms (utilisation 50 %)
• Pas 4 : 1,5 ms
• Pas 8 : 2,1 ms
• Pas 16 : 3,8 ms (utilisation 6,25 %)
• Pas 64 : 8,5 ms

Recommandation : pas ≤8 éléments pour des performances acceptables. L'outil lmbench lat_mem_rd confirme : les petits pas (128–512 octets) gardent les données en L1 (3–4 ns), les grands (64 Ko) les renvoient vers la DRAM (100+ ns).

Tableaux multidimensionnels : l'ordre de traversée est critique

C utilise l'ordre par lignes : les éléments d'une ligne sont contigus en mémoire. La traversée par lignes assure un accès séquentiel, tandis que par colonnes introduit un pas de 16+ octets.

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

Pour une matrice 1024×1024, la traversée par lignes prend 12 ms, par colonnes 45 ms (3,75× plus lente).

Optimisation de la multiplication matricielle

Ordre ijk naïf :

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];
        }
    }
}

Problème : B[k][j] est lu par colonnes (pas N=1024, 4096 octets). L'ordre ikj corrige cela :

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];
        }
    }
}

Résultats pour 512×512 : ijk — 2450 ms, ikj — 680 ms (accélération 3,6×).

Pour les grandes matrices — tuilage avec 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];
                    }
                }
            }
        }
    }
}

Les blocs tiennent en L1, avec réutilisation des données. Pour 1024×1024 : 1800 ms (10× plus rapide que le naïf).

AoS vs SoA : organisation des données

Le Tableau de Structures (AoS) regroupe les champs des particules, mais une ligne de cache contient des données inutilisées (utilisation 37,5 %).

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

La Structure de Tableaux (SoA) sépare par type :

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

Les mises à jour de position en SoA utilisent les lignes de cache à 100 %. Benchmark sur 1M de particules, 1000 itérations : AoS — 2850 ms, SoA — 1200 ms (accélération 2,4×).

Points clés

• L'accès séquentiel aux tableaux minimise les défauts de cache 7+ fois par rapport à l'aléatoire
• Pas d'accès ≤8 éléments assure >90 % d'utilisation des lignes de cache
• L'ordre par lignes en C nécessite une traversée par lignes ; l'accès par colonnes ralentit 3–4 fois
• Changer l'ordre des boucles dans les opérations matricielles donne une accélération 3–4×
• SoA surpasse AoS avec le traitement SIMD et l'accès fréquent à des sous-ensembles de champs

— Editorial Team