Prédiction de branchements CPU : le goulot caché du code

Il existe une réponse Stack Overflow célèbre, vue plus de 3 millions de fois. La question : pourquoi traiter un tableau trié est-il plus rapide que traiter un tableau non trié ? Le code est identique, une boucle avec une instruction if. La seule différence est que les données d'entrée sont triées ou non. La version triée tourne 6 fois plus vite. L'explication, la prédiction de branchements du CPU, révèle l'un des facteurs de performance les plus déterminants de l'informatique moderne.

Chaque instruction if, chaque condition de boucle, chaque cas de switch : ce sont autant de branchements dans votre code. Votre CPU en rencontre des milliards par seconde et doit deviner le résultat de chacun avant de connaître la vraie réponse. Quand il devine juste, l'exécution continue à pleine vitesse. Quand il se trompe, le CPU jette 10 à 20 cycles de travail et repart de zéro. Comprendre ce mécanisme change la façon dont on aborde le code critique pour les performances.

Pourquoi les CPU doivent prédire

Les CPU modernes sont pipelinés : ils ne attendent pas la fin d'une instruction pour commencer la suivante. Un pipeline typique comporte 12 à 20 étages. Pendant qu'une instruction s'exécute, une quinzaine d'autres sont déjà en cours de chargement, de décodage et de préparation. C'est ce pipelining qui permet d'exécuter à peu près une instruction par cycle d'horloge, alors que chacune mobilise plusieurs cycles pour se terminer.

Mais quand le CPU rencontre un branchement (if x > 0), il a un problème. L'instruction suivante dépend du fait que le branchement soit pris ou non. Le CPU ne connaît pas la réponse avant plusieurs cycles, car le résultat de la comparaison doit traverser le pipeline. Il a deux options : bloquer le pipeline et attendre (en perdant plus de 15 cycles à ne rien faire), ou deviner la direction du branchement et continuer à travailler.

Les CPU devinent toujours. Le prédicteur de branchements fait une prédiction, et le CPU charge et exécute les instructions du chemin prédit. Si la prédiction est juste, rien n'est perdu. Si elle est fausse, le CPU doit vider le pipeline, jeter les résultats des instructions exécutées à tort et repartir du bon chemin. Ce « vidage de pipeline » coûte environ 15 à 20 cycles sur les CPU x86 modernes, soit l'équivalent de 15 à 20 instructions perdues.

Fonctionnement des prédicteurs de branchements

Les prédicteurs de branchements modernes sont remarquablement sophistiqués. Ce sont en pratique des circuits de reconnaissance de motifs, qui apprennent de l'historique de chaque instruction de branchement.

Le cas simple : les branchements biaisés

Beaucoup de branchements sont fortement biaisés : ils prennent presque toujours la même direction. Une vérification d'erreur qui réussit 99,9 % du temps, une condition de boucle vraie 999 fois sur 1000 et fausse une seule fois. Le prédicteur apprend vite ces schémas et atteint une précision quasi parfaite. Un branchement qui suit la même voie 99 % du temps n'a au pire qu'un taux d'erreur de 1 %.

Reconnaissance de motifs

Les prédicteurs modernes vont bien au-delà du simple suivi de biais. Ils reconnaissent les motifs répétitifs. Si un branchement suit le schéma pris-pris-non pris-pris-pris-non pris... (période 3), le prédicteur apprend ce motif et le prédit correctement. Le prédicteur TAGE (TAgged GEometric history length), utilisé dans les CPU Intel et AMD récents, maintient plusieurs tables d'historique de longueurs différentes, capables de repérer des motifs de période allant de 2 à plusieurs centaines.

Branchements corrélés

Les prédicteurs les plus avancés apprennent aussi les corrélations entre branchements. Si le fait qu'un branchement A soit pris implique toujours qu'un branchement B (plus loin dans le code) ne soit pas pris, le prédicteur peut apprendre cette relation. On appelle cela la « prédiction adaptative à deux niveaux ». Elle gère des motifs de code comme :

// These branches are correlated
if (x > 0) {      // Branch A
y = x * 2;
}
// ... some code ...
if (x <= 0) {     // Branch B — always opposite of Branch A
y = -x;
}
// The predictor learns: when A is taken, B is not taken, and vice versa
// Both branches are predicted with near-perfect accuracy

Le mystère du tableau trié expliqué

Revenons à la fameuse question Stack Overflow. Le code ressemble à ceci :

int sum = 0;
for (int i = 0; i < arraySize; i++) {
if (data[i] >= 128)    // This is the critical branch
sum += data[i];
}
// With SORTED data [0, 1, 2, ..., 127, 128, 129, ..., 255]:
// Branch pattern: NNNNNN...NNNTTTTTT...TTT
// First half: always NOT taken. Second half: always taken.
// Prediction accuracy: ~99.9% (only mispredicts at the transition)
// With UNSORTED data [random values 0-255]:
// Branch pattern: TNNTTNNTTTNNTNNT... (random)
// Prediction accuracy: ~50% (no pattern to learn)
// Every misprediction costs ~15 cycles

Avec des données triées, le branchement est parfaitement prévisible : il n'est pas pris pendant la première moitié du tableau, puis pris pendant la seconde. Le prédicteur apprend vite chaque phase et ne se trompe qu'au point de transition. Avec des données aléatoires, le branchement équivaut à un pile ou face : le prédicteur ne peut guère dépasser une précision d'environ 50 %, et la moitié des itérations gaspillent 15 cycles en vidages de pipeline.

Sur 100 000 itérations avec un taux d'erreur d'environ 50 %, cela fait 50 000 erreurs × 15 cycles = 750 000 cycles perdus. Sur un CPU à 3 GHz, cela représente un quart de milliseconde, soit une part significative du temps d'exécution total de cette simple boucle.

Combien de branchements votre CPU peut-il gérer ?

Le prédicteur de branchements a une capacité de stockage limitée. Il suit l'historique d'un nombre fini d'emplacements de branchement grâce à une structure appelée Branch Target Buffer (BTB), et à des tables d'historique associées. Les CPU modernes peuvent suivre des dizaines de milliers d'emplacements, mais les grosses bases de code peuvent dépasser cette limite.

Quand deux instructions de branchement différentes correspondent à la même entrée du prédicteur (parce que le BTB est indexé par un hachage de l'adresse de l'instruction), elles se perturbent mutuellement. C'est rare dans du code courant, mais cela devient pertinent dans de très grosses fonctions ou quand de nombreuses petites fonctions contiennent chacune des branchements.

Daniel Lemire a publié d'excellentes recherches mesurant la capacité des prédicteurs de branchements sur différents CPU. Les résultats montrent que les CPU Intel modernes (Alder Lake et suivants) savent prédire efficacement les branchements dont l'historique remonte à environ 200 branchements : le prédicteur tient compte des résultats des 200 derniers branchements pour prédire le suivant. Les CPU AMD ont une capacité similaire. Les puces ARM sont plus disparates ; les puces Apple de la série M ont des prédicteurs particulièrement performants.

Écrire du code favorable à la prédiction de branchements

Dans la plupart des codes, la prédiction de branchements n'a pas d'importance. Le prédicteur est assez bon, et les branchements ne se trouvent pas dans des boucles critiques. Mais quand vous optimisez des chemins sensibles aux performances (boucles internes, pipelines de traitement de données, parseurs, codecs), le comportement des branchements peut dominer le temps d'exécution.

Remplacer les branchements par de l'arithmétique

La meilleure branche est celle qui n'existe pas. De nombreux schémas conditionnels peuvent être remplacés par de l'arithmétique sans branchement.

// Branching version:
int max_branch(int a, int b) {
if (a > b) return a;
return b;
}
// Branchless version (compiler often does this automatically):
int max_branchless(int a, int b) {
return a ^ ((a ^ b) & -(a < b));
}
// Conditional move — the compiler's favorite trick:
int max_cmov(int a, int b) {
// Most compilers will emit a CMOV instruction for this
return (a > b) ? a : b;
}
// Clamping with branches:
int clamp_branch(int x, int lo, int hi) {
if (x < lo) return lo;
if (x > hi) return hi;
return x;
}
// Clamping branchless:
int clamp_branchless(int x, int lo, int hi) {
// min(max(x, lo), hi)
int t = x > lo ? x : lo;  // CMOV
return t < hi ? t : hi;   // CMOV
}

Les compilateurs modernes savent généralement convertir les conditions simples en instructions CMOV (conditional move), qui évitent complètement les branchements. Mais ils n'y parviennent pas toujours, surtout quand les branchements ont des effets de bord ou quand le chemin « alors » est coûteux. Les schémas explicitement sans branchement aident dans les boucles critiques où le compilateur ne génère pas un code optimal.

Trier avant de traiter

Si vous devez filtrer des données avec un branchement, trier les données au préalable rend le branchement parfaitement prévisible. Cela semble contre-intuitif, car le tri coûte O(n log n), mais pour de grands jeux de données où la boucle s'exécute souvent, ou quand le coût d'une erreur de branchement est élevé, le tri se rentabilise.

Utiliser des tables de correspondance

Une logique conditionnelle complexe (des switch avec de nombreux cas) peut être remplacée par des recherches dans une table. Au lieu d'une chaîne de comparaisons, on indexe un tableau. L'accès au tableau peut provoquer un défaut de cache, mais c'est généralement moins coûteux qu'une cascade de branchements mal prédits.

// Branch-heavy version:
char to_hex(int nibble) {
if (nibble < 10)
return '0' + nibble;
else
return 'a' + nibble - 10;
}
// Lookup table version (no branches):
static const char hex_table[] = "0123456789abcdef";
char to_hex_lut(int nibble) {
return hex_table[nibble];
}

Donner des indications au compilateur

GCC et Clang prennent en charge __builtin_expect pour indiquer au compilateur la direction de branchement la plus probable. Cela ne contrôle pas directement le prédicteur du CPU (qui apprend à l'exécution), mais cela influence l'agencement du code : le chemin probable est placé en ligne droite, sans sauts, ce qui est plus rapide grâce aux effets du cache d'instructions.

// Tell the compiler that errors are unlikely
if (__builtin_expect(result == NULL, 0)) {
handle_error();
}
// C++20 provides cleaner syntax:
if (result == NULL) [[unlikely]] {
handle_error();
}
// Linux kernel defines macros for this:
#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
if (unlikely(ptr == NULL)) {
panic("null pointer");
}

Mesurer le comportement des branchements

Vous pouvez mesurer directement les performances de prédiction avec les compteurs matériels. Sous Linux, perf stat donne les taux d'erreur de prédiction de n'importe quel programme.

# Measure branch prediction statistics
$ perf stat -e branches,branch-misses ./my_program
Performance counter stats for './my_program':
1,482,937,256  branches          # 892.7M/sec
3,271,842  branch-misses     # 0.22% of all branches
# 0.22% misprediction rate — excellent.
# Anything under 1% is good.
# Over 5% in a hot loop means branch prediction is hurting you.
# Over 10% means you should consider branchless alternatives.

Pour les micro-benchmarks, des outils comme Google Benchmark peuvent suivre les branch-misses par itération, ce qui donne un retour précis sur l'amélioration du comportement des branchements après une modification. C'est plus exploitable que le temps mural, qui inclut le bruit d'autres activités du système.

Quand s'en soucier (et quand non)

L'optimisation de la prédiction de branchements compte dans une catégorie de code étroite mais importante : les boucles internes serrées qui traitent de grandes quantités de données. Parseurs, compresseurs, traitement d'images, calcul numérique, évaluation de requêtes en base : c'est là que le comportement des branchements domine.

Pour le reste (logique métier, gestionnaires d'API, opérations CRUD), la prédiction de branchements n'a aucune importance. Les branchements du routeur de votre serveur web ne sont pas votre goulot d'étranglement. Ne réécrivez pas des chaînes if/else lisibles en arithmétique illisible dans du code qui ne s'exécute qu'une fois par requête HTTP. Optimisez là où le profileur vous le indique, et non là où la théorie suggère qu'il pourrait y avoir un problème.

La vraie valeur de la compréhension de la prédiction de branchements n'est pas dans l'optimisation manuelle, mais dans la compréhension de la raison pour laquelle votre code se comporte comme il le fait. Quand un profileur montre qu'une simple boucle avec une instruction if est plus lente que prévu, la mauvaise prédiction de branchement en est souvent l'explication. Quand trier vos données d'entrée accélère magiquement le traitement, c'est la prédiction de branchements qui en est la raison. Avoir ce modèle mental permet de diagnostiquer des problèmes de performance qui resteraient sinon mystérieux.