La plus grande leçon de performance que j’aie apprise, c’est que les processeurs modernes ne sont pas lents à calculer, ils sont lents à attendre la mémoire. Un défaut de cache vers la mémoire principale peut coûter quelques centaines de cycles. Pendant ce temps, le processeur aurait pu faire des centaines d’additions. Une fois cet écart intériorisé, on commence à concevoir les programmes autour de la façon dont les données circulent, pas seulement des opérations qu’on exécute dessus. C’est le cœur de la conception orientée données.
La hiérarchie mémoire est la vraie machine
Entre le processeur et la mémoire principale s’intercalent plusieurs niveaux de cache : L1 est minuscule et presque aussi rapide que les registres, L2 est plus grand et plus lent, L3 plus grand et plus lent encore. Quand le processeur a besoin d’un octet, il n’en cherche pas un seul. Il récupère une ligne de cache entière, typiquement 64 octets, et la range en cache. Si votre accès suivant est dans cette ligne, il est quasi gratuit. S’il est ailleurs au loin, vous payez la pénalité complète du défaut.
Cela veut dire que la disposition de vos données en mémoire contrôle directement votre performance. Deux programmes faisant l’arithmétique identique peuvent différer d’un ordre de grandeur uniquement à cause des schémas d’accès.
Tableau de structures contre structure de tableaux
L’exemple classique est la façon de stocker une collection d’enregistrements. La disposition intuitive, orientée objet, est un tableau de structures :
struct Particle {
float x, y, z; // position
float vx, vy, vz; // vitesse
float mass;
char name[32];
};
struct Particle particles[100000];
// mise à jour des positions
for (int i = 0; i < 100000; i++) {
particles[i].x += particles[i].vx;
}Cette boucle ne touche que x et vx, mais chaque ligne de cache chargée est pleine de mass, name et des autres champs dont vous n'avez pas besoin. Vous traînez des données froides à travers le cache pour rien. La disposition orientée données scinde les champs en tableaux parallèles, une structure de tableaux :
struct Particles {
float x[100000], y[100000], z[100000];
float vx[100000], vy[100000], vz[100000];
float mass[100000];
};
for (int i = 0; i < 100000; i++) {
p.x[i] += p.vx[i];
}Maintenant le tableau x et le tableau vx sont chacun densément empaquetés. Chaque octet tiré en cache est un octet utilisé. Sur du vrai matériel, ce genre de changement donne couramment des accélérations de 3x à 10x sur les boucles chaudes, sans aucun changement d'algorithme.
Pourquoi la poursuite de pointeurs fait mal
Les listes chaînées et les arbres à nœuds sont l'opposé d'amicaux pour le cache. Chaque nœud est une allocation de tas séparée qui peut vivre n'importe où, donc parcourir la liste saute partout en mémoire et rate le cache à presque chaque étape. Si vous comprenez pile contre tas et comment les allocations de tas s'éparpillent, cela découle naturellement. Un tableau plat parcouru linéairement est nettement plus rapide qu'une liste chaînée du même nombre d'éléments, même si les deux sont en O(n), car le préchargeur matériel peut prédire et précharger un accès séquentiel.
- Préférez les tableaux contigus aux structures à nœuds quand vous itérez souvent.
- Regroupez les champs auxquels vous accédez ensemble, et séparez ceux que vous n'utilisez pas.
- Traitez les données dans l'ordre où elles sont en mémoire dès que possible.
- Gardez les données chaudes petites pour qu'il en tienne plus en cache à la fois.
C'est la même idée qu'un bon allocateur
Voilà pourquoi la stratégie d'allocation compte autant. Si vous allouez dix mille objets un par un, ils finissent éparpillés. Si vous les allouez en un seul bloc, ils sont voisins et itèrent vite. L'allocateur sur mesure de écrire un allocateur mémoire simple vous donne exactement ce contrôle : vous décidez la disposition au lieu de la laisser au hasard.
Quand y recourir
Je ne restructure pas tout autour du cache. Pour du code qui tourne une fois ou rarement, la clarté l'emporte. Mais pour les boucles chaudes, les noyaux internes qui tournent des millions de fois, la disposition des données est généralement la première chose que je règle et souvent le meilleur retour. Profilez d'abord, trouvez où sont les défauts de cache, puis disposez les données comme le matériel veut les lire. La machine est ravie d'être rapide si vous cessez de la faire attendre.