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

Question

Je suis tombé sur un #define dans laquelle ils utilisent __builtin_expect .

La documentation dit :

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

Vous pouvez utiliser __builtin_expect pour fournir au compilateur la branche de prédiction de branche. En général, il est préférable d'utiliser le pour cela ( -fprofile-arcs ), car les programmeurs sont programmeurs sont notoirement mauvais pour prédire les performances réelles de leurs programmes. Cependant, il existe des applications pour lesquelles ces données sont difficiles à collecter.

La valeur de retour est la valeur de exp qui devrait être une expression intégrale. La sémantique de l'intégré est que l'on s'attend à ce que exp == c . Par exemple :

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

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

Alors pourquoi ne pas l'utiliser directement :

if (x)
    foo ();

au lieu de la syntaxe compliquée avec __builtin_expect ?

Answer 1

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 les bar précède l'affaire foo (par opposition au code C). Cela permet de mieux utiliser le pipeline du CPU, car un saut détruit les instructions déjà extraites.

Avant que le saut ne soit exécuté, les instructions situées en dessous de celui-ci (les instructions bar ) sont poussés vers le pipeline. Comme le foo est improbable, le saut aussi est improbable, donc la destruction du pipeline est improbable.

Answer 2

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 ? Nous allons le découvrir !

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)
        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 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 était inchangé : d'abord l'instruction puts et ensuite retq retour.

Avec __builtin_expect

Maintenant, remplacez 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 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>

El puts a été déplacée à la toute fin de la fonction, la fonction retq retour !

Le nouveau code est essentiellement le même :

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 rapidement avec __builtin_expect que sans, Les processeurs sont vraiment intelligents de nos jours. . Mes tentatives naïves sont ici .

C++20 [[likely]] y [[unlikely]]

C++20 a normalisé ces modules intégrés C++ : Comment utiliser l'attribut probable/non probable de C++20 dans une instruction if-else ? Ils feront probablement (un jeu de mots !) la même chose.

Answer 3

L'idée de __builtin_expect est de dire au compilateur que vous trouverez généralement que l'expression évalue à c, de sorte que le compilateur peut optimiser pour ce cas.

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

Malheureusement, à moins que la situation ne soit très bien compris (il est probable qu'ils n'ont rien fait de tel), cela pourrait bien avoir empiré les choses. La documentation dit même :

En général, il est préférable d'utiliser le retour d'information du profil réel pour cela ( -fprofile-arcs ), car les programmeurs sont notoirement incapables de prédire les performances réelles de leurs programmes. Cependant, il existe des applications pour lesquelles ces données sont difficiles à collecter.

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

• Vous avez un réel problème de performance
• Vous avez déjà optimisé les algorithmes du système de manière appropriée.
• Vous avez des données de performance pour soutenir votre affirmation qu'un cas particulier est le plus probable

Answer 4

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

En gardant cela à l'esprit, le compilateur peut optimiser la conditionnelle de manière à ce qu'elle nécessite le moins de travail possible lorsque la condition attendue se vérifie, au détriment d'une éventuelle augmentation du travail en cas de condition inattendue.

Regardez comment les conditionnels sont mis en œuvre pendant la phase de compilation, et aussi dans l'assemblage qui en résulte, pour voir comment une branche peut représenter moins de travail que l'autre.

Cependant, je ne m'attends à ce que cette optimisation ait un effet notable que si la condition en question fait partie d'une boucle interne serrée qui est appelée une fois par semaine. lot puisque la différence dans le code résultant est relativement faible. Et si vous l'optimisez dans le mauvais sens, vous risquez de diminuer vos performances.

Answer 5

Je ne vois aucune réponse à la question que vous posez, paraphrasée, je crois :

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 'vrai' est plus probable, il pourrait optimiser pour ne pas appeler foo() .

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