Quel est l'avantage de __builtin_expect de GCC dans les instructions if else?

144

Je suis tombé sur un #definedans lequel ils utilisent __builtin_expect.

La documentation dit:

Fonction intégrée: long __builtin_expect (long exp, long c)

Vous pouvez utiliser __builtin_expectpour fournir au compilateur des informations de prédiction de branche. En général, vous devriez préférer utiliser les commentaires de profil réels pour cela ( -fprofile-arcs), car les programmeurs sont notoirement mauvais pour prédire les performances réelles de leurs programmes. Cependant, il existe des applications dans lesquelles ces données sont difficiles à collecter.

La valeur de retour est la valeur de exp, qui doit être une expression intégrale. La sémantique du intégré est que cela est attendu exp == c. Par exemple:

      if (__builtin_expect (x, 0))
        foo ();

indiquerait que nous ne nous attendons pas à appeler foo, puisque nous nous attendons xà être à zéro.

Alors pourquoi ne pas utiliser directement:

if (x)
    foo ();

au lieu de la syntaxe compliquée avec __builtin_expect?

kingsmasher1
la source
2
duplication possible de macros probables () / improbables () dans le noyau Linux - comment fonctionnent-elles? Quel est leur avantage?
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
3
Je pense que votre code direct aurait dû être if ( x == 0) {} else foo();.. ou tout simplement if ( x != 0 ) foo();qui est équivalent au code de la documentation GCC.
Nawaz

Réponses:

187

Imaginez le code d'assemblage qui serait généré à partir de:

if (__builtin_expect(x, 0)) {
    foo();
    ...
} else {
    bar();
    ...
}

Je suppose que ça devrait être quelque chose comme:

  cmp   $x, 0
  jne   _foo
_bar:
  call  bar
  ...
  jmp   after_if
_foo:
  call  foo
  ...
after_if:

Vous pouvez voir que les instructions sont disposées dans un ordre tel que le barcas précède le foocas (par opposition au code C). Cela peut mieux utiliser le pipeline du processeur, car un saut écrase les instructions déjà extraites.

Avant que le saut ne soit exécuté, les instructions en dessous (le barcas) sont poussées vers le pipeline. Comme le foocas est peu probable, sauter aussi est peu probable, il est donc peu probable que le pipeline soit écrasé.

Blagovest Buyukliev
la source
1
Ça marche vraiment comme ça? Pourquoi la définition foo ne peut pas venir en premier? L'ordre des définitions de fonction n'est pas pertinent, dans la mesure où vous avez un prototype, non?
kingsmasher1
63
Il ne s’agit pas de définitions de fonctions. Il s'agit de réorganiser le code machine de manière à réduire la probabilité que le CPU récupère des instructions qui ne seront pas exécutées.
Blagovest Buyukliev
4
Ohh je comprends. Donc, vous voulez dire puisqu'il y a une forte probabilité pour x = 0que la barre soit donnée en premier. Et foo, est défini plus tard car ses chances (plutôt utiliser la probabilité) sont moindres, non?
kingsmasher1
1
Ahhh ... merci. C'est la meilleure explication. Le code d'assemblage a vraiment fait l'affaire :)
kingsmasher1
5
Cela peut également intégrer des astuces pour le prédicteur de branche du processeur , améliorant ainsi le pipeline
Hasturkun
50

Décompilons pour voir ce que GCC 4.8 en fait

Blagovest a mentionné l'inversion de branche pour améliorer le pipeline, mais les compilateurs actuels le font-ils vraiment? Découvrons-le!

Sans pour autant __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)
        puts("a");
    return 0;
}

Compilez et décompilez avec GCC 4.8.2 x86_64 Linux:

gcc -c -O3 -std=gnu11 main.c
objdump -dr main.o

Production:

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 0a                   jne    1a <main+0x1a>
  10:       bf 00 00 00 00          mov    $0x0,%edi
                    11: R_X86_64_32 .rodata.str1.1
  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

L'ordre des instructions en mémoire est resté inchangé: d'abord puts, puis retqretour.

Avec __builtin_expect

Remplacez maintenant if (i)par:

if (__builtin_expect(i, 0))

et nous obtenons:

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 07                   je     17 <main+0x17>
  10:       31 c0                   xor    %eax,%eax
  12:       48 83 c4 08             add    $0x8,%rsp
  16:       c3                      retq
  17:       bf 00 00 00 00          mov    $0x0,%edi
                    18: R_X86_64_32 .rodata.str1.1
  1c:       e8 00 00 00 00          callq  21 <main+0x21>
                    1d: R_X86_64_PC32       puts-0x4
  21:       eb ed                   jmp    10 <main+0x10>

Le a putsété déplacé à la toute fin de la fonction, le retqretour!

Le nouveau code est fondamentalement le même que:

int i = !time(NULL);
if (i)
    goto puts;
ret:
return 0;
puts:
puts("a");
goto ret;

Cette optimisation n'a pas été faite avec -O0.

Mais bonne chance pour écrire un exemple qui fonctionne plus vite avec __builtin_expectque sans, les processeurs sont vraiment intelligents ces jours-ci . Mes tentatives naïves sont là .

C ++ 20 [[likely]]et[[unlikely]]

C ++ 20 a normalisé ces composants 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.

Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
la source
1
Consultez la fonction dispatch_once de libdispatch, qui utilise __builtin_expect pour une optimisation pratique. Le chemin lent s'exécute une seule fois et exploite __builtin_expect pour indiquer au prédicteur de branche que le chemin rapide doit être pris. Le chemin rapide fonctionne sans utiliser de verrous du tout! mikeash.com/pyblog/…
Adam Kaplan
Ne semble pas faire de différence dans GCC 9.2: gcc.godbolt.org/z/GzP6cx (en fait, déjà en 8.1)
Ruslan
40

L'idée de __builtin_expectest de dire au compilateur que vous trouverez généralement que l'expression est évaluée à c, afin que le compilateur puisse optimiser pour ce cas.

Je suppose que quelqu'un a pensé qu'il était intelligent et qu'il accélérait les choses en faisant cela.

Malheureusement, à moins que la situation ne soit très bien comprise (il est probable qu'ils n'aient rien fait de tel), cela aurait pu aggraver les choses. La documentation dit même:

En général, vous devriez préférer utiliser les commentaires de profil réels pour cela ( -fprofile-arcs), car les programmeurs sont notoirement mauvais pour prédire les performances réelles de leurs programmes. Cependant, il existe des applications dans lesquelles ces données sont difficiles à collecter.

En général, vous ne devriez pas utiliser à __builtin_expectmoins que:

  • Vous avez un problème de performances très réel
  • Vous avez déjà optimisé les algorithmes du système de manière appropriée
  • Vous disposez de données de performances pour étayer votre affirmation selon laquelle un cas particulier est le plus probable
Michael Kohne
la source
7
@Michael: Ce n'est pas vraiment une description de la prédiction de branche.
Oliver Charlesworth
3
"la plupart des programmeurs sont mauvais" ou de toute façon pas mieux que le compilateur. N'importe quel idiot peut dire que dans une boucle for, la condition de continuation est susceptible d'être vraie, mais le compilateur le sait aussi, il n'y a donc aucun avantage à le dire. Si, pour une raison quelconque, vous avez écrit une boucle qui s'arrêterait presque toujours immédiatement et si vous ne pouvez pas fournir de données de profil au compilateur pour PGO, alors peut-être que le programmeur sait quelque chose que le compilateur ne sait pas.
Steve Jessop
15
Dans certaines situations, peu importe quelle branche est la plus probable, mais plutôt quelle branche compte. Si la branche inattendue conduit à abort (), alors la probabilité n'a pas d'importance et la branche attendue doit avoir la priorité en termes de performances lors de l'optimisation.
Neowizard
1
Le problème avec votre affirmation est que les optimisations que le processeur peut effectuer en ce qui concerne la probabilité de branchement sont à peu près limitées à une: la prédiction de branchement, et cette optimisation se produit que vous l'utilisiez __builtin_expectou non . D'un autre côté, le compilateur peut effectuer de nombreuses optimisations en fonction de la probabilité de branchement, comme organiser le code de sorte que le chemin actif soit contigu, déplacer le code peu susceptible d'être optimisé plus loin ou réduire sa taille, prendre des décisions sur les branches à vectoriser, mieux planifier le chemin chaud, et ainsi de suite.
BeeOnRope
1
... sans information du développeur, il est aveugle et choisit une stratégie neutre. Si le développeur a raison sur les probabilités (et dans de nombreux cas, il est trivial de comprendre qu'une branche est généralement prise / non prise) - vous obtenez ces avantages. Si vous n'êtes pas, vous obtenez une pénalité, mais ce n'est pas beaucoup plus important que les avantages, et surtout, rien de tout cela ne remplace la prédiction de la branche du processeur.
BeeOnRope
13

Eh bien, comme il est dit dans la description, la première version ajoute un élément prédictif à la construction, indiquant au compilateur que la x == 0branche est la plus probable - c'est-à-dire que c'est la branche qui sera prise le plus souvent par votre programme.

Dans cet esprit, le compilateur peut optimiser le conditionnel afin qu'il nécessite le moins de travail lorsque la condition attendue est satisfaite, au détriment peut-être d'avoir à faire plus de travail en cas de condition inattendue.

Regardez comment les conditions sont implémentées pendant la phase de compilation, ainsi que dans l'assembly résultant, pour voir comment une branche peut être moins efficace que l'autre.

Cependant, je n'attendre cette optimisation ait un effet notable si la condition en question fait partie d'une boucle intérieure étanche qui est appelé un grand nombre , puisque la différence dans le code qui en résulte est relativement faible. Et si vous l'optimisez dans le mauvais sens, vous risquez de diminuer vos performances.

Kerrek SB
la source
Mais à la fin, il s'agit de vérifier la condition par le compilateur, voulez-vous dire que le compilateur assume toujours cette branche et continue, et plus tard s'il n'y a pas de correspondance alors? Ce qui se produit? Je pense qu'il y a quelque chose de plus sur ce truc de prédiction de branche dans la conception du compilateur, et comment cela fonctionne.
kingsmasher1
2
C'est vraiment une micro-optimisation. Regardez comment les conditions sont implémentées, il y a un petit biais vers une branche. À titre d'exemple hypothétique, supposons qu'un conditionnel devienne un test plus un saut dans l'assemblage. Ensuite, la branche sauteuse est plus lente que celle qui ne saute pas, vous préférez donc faire de la branche attendue la branche non sautante.
Kerrek SB
Merci, votre et Michael, je pense, ont des points de vue similaires mais mis en mots différents :-) Je comprends que les internes du compilateur exact sur Test-and-branch ne sont pas possibles à expliquer ici :)
kingsmasher1
Ils sont également très faciles à apprendre en recherchant sur Internet :-)
Kerrek SB
Je ferais mieux de retourner à mon livre d'université de compiler design - Aho, Ullmann, Sethi:-)
kingsmasher1
1

Je ne vois aucune des réponses à la question que je pense que vous posiez, paraphrasée:

Existe-t-il un moyen plus portable d'indiquer la prédiction de branche au compilateur?

Le titre de votre question m'a fait penser à le faire de cette façon:

if ( !x ) {} else foo();

Si le compilateur suppose que «true» est plus probable, il pourrait être optimisé pour ne pas appeler foo().

Le problème ici est simplement que vous ne savez pas, en général, ce que le compilateur supposera - donc tout code qui utilise ce type de technique devrait être soigneusement mesuré (et éventuellement surveillé au fil du temps si le contexte change).

Brent Bradburn
la source
C'est peut-être en fait exactement ce que le PO avait initialement prévu de taper (comme indiqué par le titre) - mais pour une raison quelconque, l'utilisation de a elseété omise du corps du message.
Brent Bradburn
1

Je le teste sur Mac selon @Blagovest Buyukliev et @Ciro. Les assemblages semblent clairs et j'ajoute des commentaires;

Les commandes sont gcc -c -O3 -std=gnu11 testOpt.c; otool -tVI testOpt.o

Quand j'utilise -O3 , ça a la même apparence, peu importe que __builtin_expect (i, 0) existe ou non.

testOpt.o:
(__TEXT,__text) section
_main:
0000000000000000    pushq   %rbp     
0000000000000001    movq    %rsp, %rbp    // open function stack
0000000000000004    xorl    %edi, %edi       // set time args 0 (NULL)
0000000000000006    callq   _time      // call time(NULL)
000000000000000b    testq   %rax, %rax   // check time(NULL)  result
000000000000000e    je  0x14           //  jump 0x14 if testq result = 0, namely jump to puts
0000000000000010    xorl    %eax, %eax   //  return 0   ,  return appear first 
0000000000000012    popq    %rbp    //  return 0
0000000000000013    retq                     //  return 0
0000000000000014    leaq    0x9(%rip), %rdi  ## literal pool for: "a"  // puts  part, afterwards
000000000000001b    callq   _puts
0000000000000020    xorl    %eax, %eax
0000000000000022    popq    %rbp
0000000000000023    retq

Lors de la compilation avec -O2 ,, il semble différent avec et sans __builtin_expect (i, 0)

D'abord sans

testOpt.o:
(__TEXT,__text) section
_main:
0000000000000000    pushq   %rbp
0000000000000001    movq    %rsp, %rbp
0000000000000004    xorl    %edi, %edi
0000000000000006    callq   _time
000000000000000b    testq   %rax, %rax
000000000000000e    jne 0x1c       //   jump to 0x1c if not zero, then return
0000000000000010    leaq    0x9(%rip), %rdi ## literal pool for: "a"   //   put part appear first ,  following   jne 0x1c
0000000000000017    callq   _puts
000000000000001c    xorl    %eax, %eax     // return part appear  afterwards
000000000000001e    popq    %rbp
000000000000001f    retq

Maintenant avec __builtin_expect (i, 0)

testOpt.o:
(__TEXT,__text) section
_main:
0000000000000000    pushq   %rbp
0000000000000001    movq    %rsp, %rbp
0000000000000004    xorl    %edi, %edi
0000000000000006    callq   _time
000000000000000b    testq   %rax, %rax
000000000000000e    je  0x14   // jump to 0x14 if zero  then put. otherwise return 
0000000000000010    xorl    %eax, %eax   // return appear first 
0000000000000012    popq    %rbp
0000000000000013    retq
0000000000000014    leaq    0x7(%rip), %rdi ## literal pool for: "a"
000000000000001b    callq   _puts
0000000000000020    jmp 0x10

Pour résumer, __builtin_expect fonctionne dans le dernier cas.

Victor Choy
la source