De mon cours universitaire, j'ai entendu dire que, par convention, il est préférable de placer les conditions les plus probables dans if
plutôt que dans else
ce qui peut aider le statique prédicteur de branche. Par exemple :
if (check_collision(player, enemy)) { // very unlikely to be true
doA();
} else {
doB();
}
peut être réécrit comme suit :
if (!check_collision(player, enemy)) {
doB();
} else {
doA();
}
J'ai trouvé un article de blog Patrons de branche, utilisation de GCC qui explique ce phénomène plus en détail :
Les branches avant sont générées pour les instructions if. La raison pour laquelle de les rendre peu susceptibles d'être prises est que le processeur peut tirer du fait que les instructions suivant l'instruction de branchement peuvent déjà être placées dans le tampon d'instruction à l'intérieur de l'unité d'instruction. unité d'instruction.
A côté, il est dit (c'est moi qui souligne) :
Lorsque vous écrivez une instruction if-else, toujours faire le bloc "alors" plus d'être exécuté que le bloc else , d'instructions déjà placées dans le tampon d'extraction d'instructions. d'instructions.
En fin de compte, il y a un article, écrit par Intel, Réorganisation des branches et des boucles pour éviter les mauvaises prédictions qui résume cela en deux règles :
La prédiction statique des branches est utilisée lorsque microprocesseur lorsqu'il rencontre un branchement, ce qui est typiquement la première fois qu'un branchement est rencontré. Les règles sont simples :
- Une branche avant a pour valeur par défaut pas pris
- Une branche arrière a pour valeur par défaut prise
Afin d'écrire efficacement votre code pour profiter de ces règles, lorsque vous écrivez si-else o commutateur s les plus courants et descendez progressivement vers les moins courants.
D'après ce que j'ai compris, l'idée est que le CPU en pipeline peut suivre les instructions du cache d'instructions sans les interrompre en sautant à une autre adresse dans le segment de code. Je suis conscient, cependant, que cela peut être largement simplifié dans le cas des microarchitectures modernes de CPU.
Cependant, il semble que GCC ne respecte pas ces règles. Étant donné le code :
extern void foo();
extern void bar();
int some_func(int n)
{
if (n) {
foo();
}
else {
bar();
}
return 0;
}
qu'il génère (version 6.3.0 avec -O3 -mtune=intel
) :
some_func:
lea rsp, [rsp-8]
xor eax, eax
test edi, edi
jne .L6 ; here, forward branch if (n) is (conditionally) taken
call bar
xor eax, eax
lea rsp, [rsp+8]
ret
.L6:
call foo
xor eax, eax
lea rsp, [rsp+8]
ret
La seule façon que j'ai trouvée pour forcer le comportement désiré est de réécrire l'interface de l'utilisateur. if
en utilisant __builtin_expect
comme suit :
if (__builtin_expect(n, 1)) { // force n condition to be treated as true
donc le code d'assemblage deviendrait :
some_func:
lea rsp, [rsp-8]
xor eax, eax
test edi, edi
je .L2 ; here, backward branch is (conditionally) taken
call foo
xor eax, eax
lea rsp, [rsp+8]
ret
.L2:
call bar
xor eax, eax
lea rsp, [rsp+8]
ret