Code cache-friendly en C++ : ce que c'est et pourquoi c'est important pour la vitesse

Votre code fonctionne lentement, même si l'algorithme est parfait ? Il n'est peut-être pas « ami » avec le cache

Avez-vous déjà écrit du code en C++ qui, en théorie, devrait fonctionner à la vitesse de l'éclair, mais qui ralentit en pratique ? Ou avez-vous remarqué que le parcours d'un tableau à deux dimensions par lignes et par colonnes donne des vitesses différentes, bien que la complexité de l'algorithme soit la même ? Si oui, vous avez rencontré le cache-friendly et son opposé — le code cache-unfriendly.

Aujourd'hui, nous allons voir ce que cela signifie au niveau matériel, pourquoi le cache n'est pas simplement « une mémoire de plus », mais la clé des performances, et comment écrire du code que le processeur va « adorer ». Sans abstractions complexes — seulement du C++ et des exemples clairs.

Pourquoi le processeur ne peut-il pas simplement lire dans la mémoire vive ?

La vitesse du processeur a été multipliée par des milliers au cours des dernières décennies, tandis que la vitesse de la mémoire vive (DRAM) ne l'a été que par des dizaines. Imaginez un pilote de Formule 1 (le processeur) qui doit s'arrêter chaque seconde pour obtenir du carburant (les données) d'un camion roulant à 30 km/h (la mémoire vive). Triste et lent.

La solution — le cache du processeur : une mémoire petite mais très rapide, intégrée directement dans la puce. Elle stocke des copies des données fréquemment utilisées. Lorsque le processeur a besoin de données, il vérifie d'abord le cache (L1 — le plus rapide, puis L2, L3). Ce n'est que si les données n'y sont pas (cache miss, défaut de cache) qu'il va dans la mémoire vive lente.

Voici des latences approximatives (en cycles processeur) :

\n
• Cache L1 : ~3-5 cycles
\n
• Cache L2 : ~10-20 cycles
\n
• Cache L3 : ~30-50 cycles
\n
• Mémoire vive : ~100-300 cycles
\n

La différence entre L1 et la RAM est de 50 à 100 fois. C'est pourquoi un code cache-friendly en C++ peut être des fois plus rapide qu'un équivalent « non amical ».

Principe de localité : comment le cache décide quoi conserver

Le cache ne copie pas un seul octet — il fonctionne par blocs (cache lines), généralement de 64 octets. Lorsque vous lisez une variable, le processeur charge tout le bloc contenant cette variable. Et il parie sur deux principes :

\n
• Localité spatiale (Spatial locality) : si vous lisez un élément du tableau arr[i], il est probable que vous aurez bientôt besoin de arr[i+1].
\n
• Localité temporelle (Temporal locality) : si vous avez lu des données maintenant, il est probable que vous y accédiez à nouveau dans un futur proche.
\n

Un code cache-friendly est un code qui utilise au maximum ces principes. Voyons à quoi cela ressemble en pratique.

Exemple 1 : Parcours d'un tableau à deux dimensions — le classique du genre

Cache-unfriendly (mauvais code)

const int SIZE = 1024;\nint matrix[SIZE][SIZE];\n\n// Parcours par colonnes (column-major)\nfor (int j = 0; j < SIZE; ++j) {\n    for (int i = 0; i < SIZE; ++i) {\n        matrix[i][j] = i + j;\n    }\n}\n

En C++, les tableaux sont stockés en ordre row-major (par lignes). Cela signifie que les éléments d'une ligne matrix[0][0], matrix[0][1], matrix[0][2]... sont placés séquentiellement en mémoire. La boucle externe sur j (colonnes) force le processeur à sauter à travers toute la ligne à chaque étape — chaque accès à matrix[i][j] est très probablement un cache miss. Le processeur perd du temps à charger de nouveaux blocs, tandis que les données précédentes sont expulsées du cache.

Cache-friendly (bon code)

// Parcours par lignes (row-major)\nfor (int i = 0; i < SIZE; ++i) {\n    for (int j = 0; j < SIZE; ++j) {\n        matrix[i][j] = i + j;\n    }\n}\n

Maintenant, nous parcourons la mémoire séquentiellement. Dès que nous avons chargé le bloc avec matrix[0][0], les 15 éléments suivants (avec un int de 4 octets) sont déjà dans le cache ! Cela donne un gain de vitesse de 5 à 10 fois