Pourquoi l'addition de tableaux est plus rapide en deux boucles qu'en une : analyse des erreurs C++

Pourquoi l'addition de tableaux est plus rapide en deux boucles qu'en une ? Analyse d'une erreur culte en C++

Avez-vous déjà écrit du code qui semblait intuitivement correct, mais qui était lent ? Et puis, en divisant accidentellement une boucle en deux, vous obteniez une accélération de 2 à 3 fois ? Une douleur familière. Sur Stack Overflow, il y a une question légendaire qui a rassemblé des milliers de vues et des centaines de commentaires : « Why are elementwise additions much faster in separate loops than in a combined loop? ». Aujourd'hui, nous allons décortiquer ce phénomène de manière simple, avec des exemples de code en C++ et sans théories absconses.

Ce n'est pas de la magie. Ce sont les défauts de cache (cache misses) et la façon dont le processeur accède réellement à la mémoire. Si vous écrivez en C++ et que vous voulez que votre code vole — lisez attentivement. À la fin de l'article, vous trouverez des actions concrètes à appliquer dès maintenant.

Le cœur du problème : deux boucles vs une seule

Imaginez que nous ayons deux grands tableaux a et b, et que nous voulions effectuer une addition élément par élément, puis une multiplication de chaque élément. L'intuition nous dit : « Faisons une seule boucle pour ne pas faire aller et venir le processeur ! ».

Voici à quoi ressemble la boucle combinée :

const int N = 1000000;\nfloat a[N], b[N];\n\n// Une seule boucle — on fait tout en même temps\nfor (int i = 0; i < N; ++i) {\n    a[i] = a[i] + b[i];  // addition\n    a[i] = a[i] * 2.0f;  // multiplication\n}

Et voici deux boucles séparées :

// Première boucle — seulement l'addition\nfor (int i = 0; i < N; ++i) {\n    a[i] = a[i] + b[i];\n}\n\n// Deuxième boucle — seulement la multiplication\nfor (int i = 0; i < N; ++i) {\n    a[i] = a[i] * 2.0f;\n}

Logiquement, on pourrait penser que la première option est plus rapide : moins de frais généraux pour l'organisation de la boucle. Mais en pratique, c'est l'inverse — la deuxième option est souvent 2 à 3 fois plus rapide. Pourquoi ? Bienvenue dans le monde de la hiérarchie du cache.

Les défauts de cache : l'ennemi numéro un de la performance

Les processeurs modernes n'accèdent pas directement à la mémoire vive à chaque fois. Ils utilisent le cache — une mémoire rapide située directement sur la puce. Le cache a plusieurs niveaux (L1, L2, L3), et chaque niveau suivant est plus lent mais plus grand.

Lorsque votre code lit ou écrit des données, le processeur charge dans le cache un bloc entier (cache line) — généralement 64 octets. Si la demande suivante tombe dans le même bloc, c'est un hit (succès). Sinon, c'est un miss (échec), et le processeur doit attendre les données de la RAM lente. Un seul miss peut coûter des centaines de cycles.

Revenons maintenant à notre exemple. Dans la boucle combinée, à chaque itération, nous accédons à a[i] et b[i] deux fois : d'abord pour la lecture, puis pour l'écriture. Pendant que nous travaillons avec a[0] et b[0], le cache charge leurs cache lines. Mais à l'itération suivante, nous allons vers a[1] et b[1] — un miss est possible si les données se trouvent dans des lignes de cache différentes. En conséquence, nous « sollicitons » constamment la mémoire, forçant le cache à se recharger.

Dans deux boucles séparées, c'est différent. La première boucle lit séquentiellement a[i] et b[i] et écrit le résultat. Les données sont linéaires — le cache est prévisible et fonctionne parfaitement (localité spatiale). La deuxième boucle parcourt à nouveau le même tableau a — les données sont déjà chaudes dans le cache L1. Il n'y a pratiquement pas de misses.

Les principales erreurs qui tuent la performance

Erreur n°1 — mélanger des opérations sur différents tableaux dans une seule boucle. Si vous pouvez séparer la logique en deux passes (surtout avec de grandes données) — faites-le. Le cache vous remerciera.

Erreur n°2 — ignorer la taille de la cache line. 64 octets correspondent à environ 16 float ou 8 double. Si vos tableaux ont des pas étranges ou si vous sautez sur des index de manière non séquentielle, vous êtes assuré d'avoir des défauts de cache.

Erreur n°3