FR
RU
EN
ES
ZH
DE
PT
AR
HI
Introduction : L'une des questions les plus surprenantes dans le monde du C++
\n\nImaginez la situation : vous écrivez une simple boucle en C++ qui additionne les éléments d'un grand tableau, mais uniquement ceux qui dépassent un certain seuil. Vous exécutez le code, il fonctionne... normalement. Ensuite, vous décidez de trier le tableau au préalable et vous relancez l'exécution. Et soudain, vous remarquez que le code s'exécute 2 à 3 fois plus rapidement ! Où est le piège ? Magie du compilateur ? Erreur dans le benchmark ?
\n\nCette question, posée sur Stack Overflow il y a plus de dix ans, a rassemblé des milliers de vues et suscite encore des débats animés. Aujourd'hui, sur PythonLib, nous allons l'analyser en profondeur, avec des exemples concrets en C++ et une plongée dans l'architecture des processeurs modernes. Vous découvrirez non seulement pourquoi cela se produit, mais aussi comment utiliser cet effet pour accélérer votre code.
\n\n1. Reproduire le phénomène : un code qui surprend
\n\nÉcrivons un programme simple qui illustre clairement cet effet. Nous aurons besoin d'un tableau de 100 000 entiers. Nous le remplirons de valeurs aléatoires, puis nous mesurerons le temps d'addition de tous les éléments supérieurs à 128.
\n\n#include <iostream>\n#include <vector>\n#include <algorithm>\n#include <chrono>\n#include <random>\n\nint main() {\n const int SIZE = 100000;\n const int THRESHOLD = 128;\n \n // Création d'un tableau non trié\n std::vector<int> data(SIZE);\n std::mt19937 rng(42);\n std::uniform_int_distribution<int> dist(0, 255);\n for (auto& val : data) {\n val = dist(rng);\n }\n\n // Addition pour le tableau non trié\n auto start = std::chrono::high_resolution_clock::now();\n long long sum_unsorted = 0;\n for (int i = 0; i < SIZE; ++i) {\n if (data[i] >= THRESHOLD) {\n sum_unsorted += data[i];\n }\n }\n auto end = std::chrono::high_resolution_clock::now();\n auto time_unsorted = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();\n std::cout << "Tableau non trié : " << time_unsorted << " µs, somme = " << sum_unsorted << std::endl;\n\n // Tri du tableau\n std::sort(data.begin(), data.end());\n\n // Addition pour le tableau trié\n start = std::chrono::high_resolution_clock::now();\n long long sum_sorted = 0;\n for (int i = 0; i < SIZE; ++i) {\n if (data[i] >= THRESHOLD) {\n sum_sorted += data[i];\n }\n }\n end = std::chrono::high_resolution_clock::now();\n auto time_sorted = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();\n std::cout << "Tableau trié : " << time_sorted << " µs, somme = " << sum_sorted << std::endl;\n\n std::cout << "Accélération : " << (double)time_unsorted / time_sorted << "x" << std::endl;\n return 0;\n}Lors de la compilation sans optimisations (drapeau -O0), la différence sera faible, mais si vous activez -O2 ou -O3 dans GCC/Clang, vous obtiendrez un résultat impressionnant : le tableau trié est traité 3 à 6 fois plus rapidement.
2. Anatomie du processeur : d'où vient la différence ?
\n\nLa clé du mystère réside dans un mécanisme appelé Branch Prediction (prédiction de branchement). Les processeurs modernes sont des machines à pipeline. Ils n'exécutent pas les instructions une par une, mais les décomposent en étapes (lecture, décodage, exécution, écriture du résultat). Pour éviter que le pipeline ne soit inactif, le processeur tente de deviner quelle branche du code (if ou else) sera exécutée ensuite, et commence à charger les instructions à l'avance.
Dans notre exemple, la condition if (data[i] >= THRESHOLD) est un point de branchement. Pour un tableau trié, la prédiction fonctionne
