Ils suggèrent au compilateur d'émettre des instructions qui feront que la prédiction de branchement favorisera le côté "probable" d'une instruction de saut. Cela peut être une grande victoire, si la prédiction est correcte, cela signifie que l'instruction de saut est fondamentalement gratuite et ne prendra aucun cycle. D'autre part, si la prédiction est erronée, cela signifie que le pipeline du processeur doit être vidé et cela peut coûter plusieurs cycles. Tant que la prédiction est correcte la plupart du temps, cela aura tendance à être bon pour les performances.
Comme toutes ces optimisations de performances, vous ne devriez le faire qu'après un profilage approfondi pour vous assurer que le code est vraiment dans un goulot d'étranglement, et probablement compte tenu de la nature micro, qu'il est exécuté dans une boucle serrée. Généralement, les développeurs Linux sont assez expérimentés, donc j'imagine qu'ils l'auraient fait. Ils ne se soucient pas vraiment de la portabilité car ils ne ciblent que gcc, et ils ont une idée très précise de l'assembly qu'ils veulent qu'il génère.
Décompilons pour voir ce que GCC 4.8 en fait
Sans __builtin_expect
#include "stdio.h"
#include "time.h"
int main() {
/* Use time to prevent it from being optimized away. */
int i = !time(NULL);
if (i)
printf("%d\n", i);
puts("a");
return 0;
}
Compiler et décompiler avec GCC 4.8.2 x86_64 Linux :
gcc -c -O3 -std=gnu11 main.c
objdump -dr main.o
Sortie :
0000000000000000 <main>:
0: 48 83 ec 08 sub $0x8,%rsp
4: 31 ff xor %edi,%edi
6: e8 00 00 00 00 callq b <main+0xb>
7: R_X86_64_PC32 time-0x4
b: 48 85 c0 test %rax,%rax
e: 75 14 jne 24 <main+0x24>
10: ba 01 00 00 00 mov $0x1,%edx
15: be 00 00 00 00 mov $0x0,%esi
16: R_X86_64_32 .rodata.str1.1
1a: bf 01 00 00 00 mov $0x1,%edi
1f: e8 00 00 00 00 callq 24 <main+0x24>
20: R_X86_64_PC32 __printf_chk-0x4
24: bf 00 00 00 00 mov $0x0,%edi
25: R_X86_64_32 .rodata.str1.1+0x4
29: e8 00 00 00 00 callq 2e <main+0x2e>
2a: R_X86_64_PC32 puts-0x4
2e: 31 c0 xor %eax,%eax
30: 48 83 c4 08 add $0x8,%rsp
34: c3 retq
L'ordre des instructions en mémoire était inchangé :d'abord le printf puis puts et le retq retour.
Avec __builtin_expect
Remplacez maintenant if (i) avec :
if (__builtin_expect(i, 0))
et on obtient :
0000000000000000 <main>:
0: 48 83 ec 08 sub $0x8,%rsp
4: 31 ff xor %edi,%edi
6: e8 00 00 00 00 callq b <main+0xb>
7: R_X86_64_PC32 time-0x4
b: 48 85 c0 test %rax,%rax
e: 74 11 je 21 <main+0x21>
10: bf 00 00 00 00 mov $0x0,%edi
11: R_X86_64_32 .rodata.str1.1+0x4
15: e8 00 00 00 00 callq 1a <main+0x1a>
16: R_X86_64_PC32 puts-0x4
1a: 31 c0 xor %eax,%eax
1c: 48 83 c4 08 add $0x8,%rsp
20: c3 retq
21: ba 01 00 00 00 mov $0x1,%edx
26: be 00 00 00 00 mov $0x0,%esi
27: R_X86_64_32 .rodata.str1.1
2b: bf 01 00 00 00 mov $0x1,%edi
30: e8 00 00 00 00 callq 35 <main+0x35>
31: R_X86_64_PC32 __printf_chk-0x4
35: eb d9 jmp 10 <main+0x10>
Le printf (compilé en __printf_chk ) a été déplacé à la toute fin de la fonction, après puts et le retour pour améliorer la prédiction de branche comme mentionné par d'autres réponses.
Donc, c'est fondamentalement la même chose que :
int main() {
int i = !time(NULL);
if (i)
goto printf;
puts:
puts("a");
return 0;
printf:
printf("%d\n", i);
goto puts;
}
Cette optimisation n'a pas été faite avec -O0 .
Mais bonne chance pour écrire un exemple qui s'exécute plus rapidement avec __builtin_expect que sans, les processeurs sont vraiment intelligents de nos jours. Mes tentatives naïves sont là.
C++20 [[likely]] et [[unlikely]]
C++20 a standardisé ces éléments intégrés C++ :Comment utiliser l'attribut probable/improbable de C++20 dans l'instruction if-else Ils feront probablement (un jeu de mots !) La même chose.
Ce sont des macros qui donnent des indications au compilateur sur la manière dont une branche peut aller. Les macros s'étendent aux extensions spécifiques à GCC, si elles sont disponibles.
GCC les utilise pour optimiser la prédiction de branche. Par exemple, si vous avez quelque chose comme ce qui suit
if (unlikely(x)) {
dosomething();
}
return x;
Ensuite, il peut restructurer ce code pour qu'il ressemble davantage à :
if (!x) {
return x;
}
dosomething();
return x;
L'avantage de ceci est que lorsque le processeur prend une branche pour la première fois, il y a une surcharge importante, car il peut avoir chargé et exécuté de manière spéculative du code plus loin. Lorsqu'il détermine qu'il prendra la branche, il doit l'invalider et commencer à la cible de la branche.
La plupart des processeurs modernes ont maintenant une sorte de prédiction de branche, mais cela n'aide que lorsque vous avez déjà parcouru la branche et que la branche est toujours dans le cache de prédiction de branche.
Il existe un certain nombre d'autres stratégies que le compilateur et le processeur peuvent utiliser dans ces scénarios. Vous pouvez trouver plus de détails sur le fonctionnement des prédicteurs de branche sur Wikipedia :http://en.wikipedia.org/wiki/Branch_predictor