Pourquoi 8192 éléments ralentissent votre code C++ ? Analyse

Introduction : Le nombre magique 8192 et votre code qui ralentit

Avez-vous déjà remarqué que votre code C++, qui fonctionnait parfaitement avec 1000 ou 10000 éléments, commence soudainement à ralentir exactement à 8192 ? Non, ce n'est pas un bug du compilateur ni une malédiction des anciens programmeurs. C'est un exemple classique de la façon dont l'architecture du processeur peut transformer votre algorithme rapide en tortue.

Cette histoire a commencé avec une question légendaire sur Stack Overflow : "Why is my program slow when looping over exactly 8192 elements?", qui a recueilli des milliers de vues et est devenue un véritable mème dans le monde du High Performance Computing. Aujourd'hui, en 2025, alors que les processeurs sont devenus encore plus complexes, comprendre ce problème n'est pas simplement un fait amusant, mais une compétence réelle qui distingue un développeur junior d'un ingénieur écrivant du code rapide.

Dans cet article, nous allons analyser ce qui se passe sous le capot de votre processeur, pourquoi la taille 8192 (et ses multiples) constituent une "zone rouge", et comment écrire un code qui reste stablement rapide sur toutes les données. C'est parti !

1. Anatomie du problème : Défauts de cache et associativité

Pour comprendre la racine du mal, il faut examiner l'architecture d'un processeur moderne. L'opération la plus lente est l'accès à la mémoire vive (RAM). Pour accélérer l'accès, le processeur utilise un cache — une mémoire petite mais très rapide, située directement sur le cristal.

1.1. Comment fonctionne le cache (très brièvement)

\n
• Cache L1 : Le plus rapide et le plus petit (~32 Ko par cœur).
\n
• Cache L2 : Un peu plus lent, mais plus grand (~256-512 Ko).
\n
• Cache L3 : Partagé par tous les cœurs, le plus grand (plusieurs Mo).
\n

Les données sont chargées dans le cache non pas octet par octet, mais par blocs — lignes de cache (généralement 64 octets). Si le processeur demande des données qui ne sont pas dans le cache, un défaut de cache (cache miss) se produit, et il doit attendre le chargement depuis la RAM. Cela peut prendre des centaines de cycles.

1.2. La malédiction de 8192 : L'associativité du cache

Le cache n'est pas simplement un grand panier. Il est organisé en ensembles (sets). Chaque adresse mémoire ne peut être placée que dans un seul de ces ensembles. C'est ce qu'on appelle un cache set-associative.

Imaginez un parking où les places sont regroupées par rangées. Votre voiture (adresse mémoire) ne peut être garée que dans une rangée spécifique (ensemble). Si toutes les places de cette rangée sont occupées, vous devez sortir une des voitures (expulser une ligne de cache) pour libérer de l'espace.

Pour de nombreux processeurs modernes, les caches L1 et L2 sont set-associatifs à 8 voies. Cela signifie que chaque ensemble peut contenir 8 lignes de cache.

Et voici le point clé : la taille d'une ligne de cache est de 64 octets (512 bits). Si vous travaillez avec un tableau d'int (4 octets), une ligne de cache contient 16 éléments.

Lorsque vous parcourez un tableau avec un pas égal à une puissance de deux, tous les éléments auxquels vous accédez peuvent être mappés sur le même ensemble de cache. Par exemple, si vous prenez chaque 16e élément, ils vont tous entrer en compétition pour les mêmes 8 emplacements dans l'ensemble. Lorsque le nombre d'éléments devient supérieur au nombre d'emplacements (par exemple, lorsque vous parcourez un tableau de 8192 éléments qui sont tous mappés sur un seul ensemble), le cache commence constamment à "jeter" les anciennes données et à en charger de nouvelles. C'est ce qu'on appelle le cache thrashing.

8192 est 2^13. Avec une certaine disposition des données en mémoire, c'est exactement ce nombre d'éléments qui "frappe" parfaitement les limites d'associativité d'un cache L1 typique (32 Ko / 64 octets = 512 ensembles, et 8192 / 16 = 512, ce qui correspond parfaitement à chaque ensemble).

2. Démonstration du problème en C++

Regardons le code qui reproduit ce problème. Nous allons mesurer le temps de parcours d'un tableau à deux dimensions avec différents pas.

#include <iostream>\n#include <vector>\n#include <chrono>\n\nconst int SIZE