Y a-t-il un indice du compilateur pour que GCC force la prédiction de branche à toujours suivre une certaine direction?

118

Pour les architectures Intel, existe-t-il un moyen de demander au compilateur GCC de générer du code qui force toujours la prédiction de branche d'une manière particulière dans mon code? Le matériel Intel prend-il même en charge cela? Qu'en est-il des autres compilateurs ou matériels?

J'utiliserais ceci dans le code C ++ où je connais le cas où je souhaite courir vite et ne me soucie pas du ralentissement lorsque l'autre branche doit être prise même lorsqu'elle a récemment pris cette branche.

for (;;) {
  if (normal) { // How to tell compiler to always branch predict true value?
    doSomethingNormal();
  } else {
    exceptionalCase();
  }
}

En tant que question suivante pour Evdzhan Mustafa, l'indice peut-il simplement spécifier un indice pour la première fois que le processeur rencontre l'instruction, toutes les prédictions de branche ultérieures, fonctionnant normalement?

WilliamKF
la source
pourrait également lever une exception si quelque chose devient anormal (ce qui est indépendant du compilateur)
Shep

Réponses:

9

À partir de C ++ 20, les attributs probables et improbables doivent être normalisés et sont déjà pris en charge dans g ++ 9 . Ainsi, comme discuté ici , vous pouvez écrire

if (a>b) {
  /* code you expect to run often */
  [[likely]] /* last statement */
}

par exemple, dans le code suivant, le bloc else est inséré grâce au [[unlikely]]bloc if

int oftendone( int a, int b );
int rarelydone( int a, int b );
int finaltrafo( int );

int divides( int number, int prime ) {
  int almostreturnvalue;
  if ( ( number % prime ) == 0 ) {
    auto k                         = rarelydone( number, prime );
    auto l                         = rarelydone( number, k );
    [[unlikely]] almostreturnvalue = rarelydone( k, l );
  } else {
    auto a            = oftendone( number, prime );
    almostreturnvalue = oftendone( a, a );
  }
  return finaltrafo( almostreturnvalue );
}

lien godbolt comparant la présence / absence de l'attribut

Pseyfert
la source
Pourquoi utiliser [[unlikely]]dans ifvs [[likely]]dans le else?
WilliamKF
aucune raison, vient de se retrouver dans cette constellation après avoir essayé de savoir où l'attribut doit aller.
pseyfert le
Plutôt cool. Dommage que la méthode ne s'applique pas aux anciennes versions de C ++.
Maxim Egorushkin le
Fantastique lien godbolt
Lewis Kelsey
87

GCC prend en charge la fonction __builtin_expect(long exp, long c)de fournir ce type de fonctionnalité. Vous pouvez consulter la documentation ici .

expest la condition utilisée et cest la valeur attendue. Par exemple, dans votre cas, vous voudriez

if (__builtin_expect(normal, 1))

En raison de la syntaxe peu pratique, cela est généralement utilisé en définissant deux macros personnalisées comme

#define likely(x)    __builtin_expect (!!(x), 1)
#define unlikely(x)  __builtin_expect (!!(x), 0)

juste pour faciliter la tâche.

Faites attention à cela:

  1. ce n'est pas standard
  2. un prédicteur de branche compilateur / cpu est probablement plus habile que vous à décider de telles choses, donc cela pourrait être une micro-optimisation prématurée
Jack
la source
3
Y a-t-il une raison pour laquelle vous affichez une macro et non une constexprfonction?
Columbo
22
@Columbo: Je ne pense pas qu'une constexprfonction puisse remplacer cette macro. Cela doit figurer ifdirectement dans la déclaration, je crois. La même raison assertne pourrait jamais être une constexprfonction.
Mooing Duck
1
@MooingDuck Je suis d'accord, bien qu'il y ait plus de raisons d'affirmer .
Shafik Yaghmour
7
@Columbo une des raisons d'utiliser une macro serait parce que c'est l'un des rares endroits en C ou C ++ où une macro est plus sémantiquement correcte qu'une fonction. La fonction apparaît uniquement au travail en raison de l' optimisation (il est une optimisation: constexprne parle que de la sémantique de valeur, et non l'inline de réunion spécifique à la mise en œuvre); l'interprétation directe (pas en ligne) du code n'a pas de sens. Il n'y a aucune raison d'utiliser une fonction pour cela.
Leushenko
2
@Leushenko Considérez que __builtin_expectlui - même est un indice d'optimisation, donc affirmer qu'une méthode simplifiant son utilisation dépend de l'optimisation n'est ... pas convaincant. De plus, je n'ai pas ajouté le constexprspécificateur pour le faire fonctionner en premier lieu, mais pour le faire fonctionner dans des expressions constantes. Et oui, il y a des raisons d'utiliser une fonction. Par exemple, je ne voudrais pas polluer tout mon espace de noms avec un joli petit nom tel que likely. Je devrais utiliser par exemple LIKELY, pour souligner que c'est une macro et éviter les collisions, mais c'est tout simplement moche.
Columbo
46

gcc a long __builtin_expect (long exp, long c) (c'est moi qui souligne ):

Vous pouvez utiliser __builtin_expect pour 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 comment leurs programmes fonctionnent réellement . 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 de la fonction intégrée est que l'on s'attend à ce que exp == c. Par exemple:

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

indique que nous ne prévoyons pas d'appeler foo, puisque nous nous attendons à ce que x soit nul. Puisque vous êtes limité aux expressions intégrales pour exp, vous devez utiliser des constructions telles que

if (__builtin_expect (ptr != NULL, 1))
   foo (*ptr);

lors du test de pointeur ou de valeurs à virgule flottante.

Comme le note la documentation, vous devriez préférer utiliser les commentaires de profil réels et cet article en montre un exemple pratique et comment cela, dans leur cas, finit au moins par être une amélioration par rapport à l'utilisation __builtin_expect. Voir également Comment utiliser les optimisations guidées par profil dans g ++? .

On peut également trouver un article pour les débutants du noyau Linux sur les macros noyau probable () et improbable () qui utilisent cette fonctionnalité:

#define likely(x)       __builtin_expect(!!(x), 1)
#define unlikely(x)     __builtin_expect(!!(x), 0)

Notez le !!utilisé dans la macro, nous pouvons trouver l'explication pour cela dans Pourquoi utiliser !! (condition) au lieu de (condition)? .

Ce n'est pas parce que cette technique est utilisée dans le noyau Linux qu'il est toujours logique de l'utiliser. Nous pouvons voir à partir de cette question que j'ai récemment répondu à la différence entre les performances de la fonction lors du passage du paramètre en tant que constante de temps de compilation ou variable que de nombreuses techniques d'optimisation roulées à la main ne fonctionnent pas dans le cas général. Nous devons profiler soigneusement le code pour comprendre si une technique est efficace. De nombreuses techniques anciennes peuvent même ne pas être pertinentes avec les optimisations modernes du compilateur.

Remarque, bien que les fonctions intégrées ne soient pas portables clang prend également en charge __builtin_expect .

De plus, sur certaines architectures, cela peut ne pas faire de différence .

Shafik Yaghmour
la source
Ce qui est assez bon pour le noyau Linux ne suffit pas pour C ++ 11.
Maxim Egorushkin
Remarque @MaximEgorushkin, je ne recommande pas réellement son utilisation, en fait la documentation gcc que je cite qui est ma première citation n'utilise même pas cette technique. Je dirais que l’idée maîtresse de ma réponse est d’examiner attentivement les alternatives avant de suivre cette voie.
Shafik Yaghmour
44

Non, il n'y en a pas. (Au moins sur les processeurs x86 modernes.)

__builtin_expectmentionné dans d'autres réponses influence la manière dont gcc organise le code d'assemblage. Il n'influence pas directement le prédicteur de branche du CPU.Bien sûr, il y aura des effets indirects sur la prédiction de branche causés par la réorganisation du code. Mais sur les processeurs x86 modernes, il n'y a aucune instruction qui dit au CPU "suppose que cette branche est / n'est pas prise".

Voir cette question pour plus de détails: Intel x86 0x2E / 0x3E Prefix Branch Prediction réellement utilisé?

Pour être clair, __builtin_expectet / ou l'utilisation de -fprofile-arcs peut améliorer les performances de votre code, à la fois en donnant des conseils au prédicteur de branche via la disposition du code (voir Optimisations des performances de l'assemblage x86-64 - Alignement et prédiction de branche ), et en améliorant également le comportement du cache en gardant le code "improbable" loin du code "probable".

Artelius
la source
9
Ceci est une erreur. Sur toutes les versions modernes de x86, l'algorithme de prédiction par défaut est de prédire que les branches avant ne sont pas prises et que les branches arrière le sont (voir software.intel.com/en-us/articles/… ). Ainsi, en réorganisant votre code, vous pouvez effectivement donner un indice au processeur. C'est exactement ce que fait GCC lorsque vous utilisez __builtin_expect.
Nemo
6
@Nemo, avez-vous lu la première phrase de ma réponse? Tout ce que vous avez dit est couvert par ma réponse ou dans les liens donnés. La question demandait si vous pouviez "forcer la prédiction de branche à toujours suivre un certain chemin", à laquelle la réponse est "non", et je ne pensais pas que les autres réponses étaient assez claires à ce sujet.
Artelius
4
OK, j'aurais dû lire plus attentivement. Il me semble que cette réponse est techniquement correcte, mais inutile, puisque le questionneur recherche évidemment __builtin_expect. Cela devrait donc être juste un commentaire. Mais ce n'est pas faux, j'ai donc supprimé mon vote défavorable.
Nemo
IMO ce n'est pas inutile; c'est une clarification utile du fonctionnement réel des processeurs et des compilateurs, ce qui pourrait être pertinent pour l'analyse des performances avec / sans ces options. par exemple, vous ne pouvez généralement pas utiliser __builtin_expectpour créer de manière triviale un cas de test avec lequel vous pouvez mesurer et perf statqui aura un taux d'erreur de prédiction de branche très élevé. Cela affecte simplement la disposition des branches . Et BTW, Intel depuis Sandybridge ou du moins Haswell n'utilise pas beaucoup / pas du tout la prédiction statique; il y a toujours une prédiction dans le BHT, que ce soit un alias périmé ou non. xania.org/201602/bpu-part-two
Peter Cordes
24

La manière correcte de définir des macros probables / improbables dans C ++ 11 est la suivante:

#define LIKELY(condition) __builtin_expect(static_cast<bool>(condition), 1)
#define UNLIKELY(condition) __builtin_expect(static_cast<bool>(condition), 0)

Cette méthode est compatible avec toutes les versions de C ++, contrairement à [[likely]], mais repose sur une extension non standard __builtin_expect.


Lorsque ces macros sont définies de cette façon:

#define LIKELY(condition) __builtin_expect(!!(condition), 1)

Cela peut changer la signification des ifinstructions et casser le code. Considérez le code suivant:

#include <iostream>

struct A
{
    explicit operator bool() const { return true; }
    operator int() const { return 0; }
};

#define LIKELY(condition) __builtin_expect((condition), 1)

int main() {
    A a;
    if(a)
        std::cout << "if(a) is true\n";
    if(LIKELY(a))
        std::cout << "if(LIKELY(a)) is true\n";
    else
        std::cout << "if(LIKELY(a)) is false\n";
}

Et sa sortie:

if(a) is true
if(LIKELY(a)) is false

Comme vous pouvez le voir, la définition de LIKELY en utilisant !!comme un cast pour boolcasser la sémantique de if.

Le point ici n'est pas cela operator int()et operator bool()devrait être lié. Ce qui est une bonne pratique.

Plutôt que d'utiliser !!(x)au lieu de static_cast<bool>(x)perd le contexte pour les conversions contextuelles C ++ 11 .

Maxim Egorushkin
la source
Notez que les conversions contextuelles sont intervenues via un défaut en 2012 et même à la fin de 2014, il y avait encore des divergences de mise en œuvre. En fait, il semble que le cas auquel j'ai lié ne fonctionne toujours pas pour gcc.
Shafik Yaghmour
@ShafikYaghmour C'est une observation intéressante en ce qui concerne la conversion contextuelle impliquée switch, merci. La conversion contextuelle impliquée ici est partucléaire du type boolet des cinq contextes spécifiques qui y sont répertoriés , qui n'incluent pas le switchcontexte.
Maxim Egorushkin
Cela n'affecte que le C ++, non? Il n'y a donc aucune raison d'aller changer les projets C existants à utiliser (_Bool)(condition), car C n'a pas de surcharge d'opérateurs.
Peter Cordes
2
Dans votre exemple, vous avez utilisé simplement (condition), non !!(condition). Les deux sont trueaprès avoir changé cela (testé avec g ++ 7.1). Pouvez-vous construire un exemple qui démontre réellement le problème dont vous parlez lorsque vous utilisez !!pour booleanize?
Peter Cordes
3
Comme l'a souligné Peter Cordes, vous dites "Lorsque ces macros [sont] définies de cette façon:" et ensuite afficher une macro à l'aide de '!!', "peut changer la signification des instructions if et casser le code. Considérez le code suivant:" ... et puis vous affichez du code qui n'utilise pas '!!' du tout - qui a connu pour être cassé même avant C ++ 11. Veuillez changer la réponse pour montrer un exemple où la macro donnée (en utilisant !!) va mal.
Carlo Wood
18

Comme les autres réponses l'ont toutes suggérées de manière adéquate, vous pouvez utiliser __builtin_expectpour donner au compilateur un indice sur la façon d'organiser le code d'assembly. Comme le soulignent les documents officiels , dans la plupart des cas, l'assembleur intégré à votre cerveau ne sera pas aussi bon que celui conçu par l'équipe GCC. Il est toujours préférable d'utiliser les données de profil réelles pour optimiser votre code, plutôt que de deviner.

Dans le même ordre d'idées, mais pas encore mentionné, il y a une manière spécifique à GCC de forcer le compilateur à générer du code sur un chemin "froid". Cela implique l'utilisation des attributs noinlineet cold, qui font exactement ce qu'ils semblent faire. Ces attributs ne peuvent être appliqués qu'aux fonctions, mais avec C ++ 11, vous pouvez déclarer des fonctions lambda en ligne et ces deux attributs peuvent également être appliqués aux fonctions lambda.

Bien que cela tombe toujours dans la catégorie générale d'une micro-optimisation, et donc le conseil standard s'applique - testez ne pas deviner - je pense que c'est plus généralement utile que __builtin_expect. Presque toutes les générations du processeur x86 utilisent des indices de prédiction de branche ( référence ), donc la seule chose que vous allez pouvoir affecter de toute façon est l'ordre du code d'assemblage. Puisque vous savez ce qu'est la gestion des erreurs ou le code de "cas de bord", vous pouvez utiliser cette annotation pour vous assurer que le compilateur ne prédira jamais une branche vers celui-ci et le liera loin du code "chaud" lors de l'optimisation de la taille.

Exemple d'utilisation:

void FooTheBar(void* pFoo)
{
    if (pFoo == nullptr)
    {
        // Oh no! A null pointer is an error, but maybe this is a public-facing
        // function, so we have to be prepared for anything. Yet, we don't want
        // the error-handling code to fill up the instruction cache, so we will
        // force it out-of-line and onto a "cold" path.
        [&]() __attribute__((noinline,cold)) {
            HandleError(...);
        }();
    }

    // Do normal stuff
    
}

Mieux encore, GCC l'ignorera automatiquement en faveur des commentaires de profil lorsqu'il est disponible (par exemple, lors de la compilation avec -fprofile-use).

Voir la documentation officielle ici: https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#Common-Function-Attributes

Cody Gray
la source
2
Les préfixes d'indication de prédiction de branche sont ignorés car ils ne sont pas nécessaires; vous pouvez obtenir exactement le même effet en réorganisant votre code. (L'algorithme de prédiction de branche par défaut consiste à deviner que les branches arrière sont prises et que les branches avant ne le sont pas.) Vous pouvez donc, en fait, donner un indice au processeur, et c'est ce que __builtin_expectfait. Ce n'est pas du tout inutile. Vous avez raison de dire que l' coldattribut est également utile, mais vous sous-estimez l'utilité de __builtin_expectje pense.
Nemo
Les processeurs Intel modernes n'utilisent pas la prédiction de branche statique. L'algorithme que vous décrivez, @Nemo, dans lequel les branches arrière sont prédites prises et les branches avant sont prédites comme non prises, a été utilisé dans les processeurs précédents, et à travers le Pentium M ou plus, mais les conceptions modernes se contentent de deviner au hasard, en indexant dans leur branche tables où il s'attendrait à trouver des informations sur cette branche et en utilisant toutes les informations qui s'y trouvent (même si elles peuvent être essentiellement des ordures). Ainsi, des conseils de prédiction de branche seraient théoriquement utiles, mais peut-être pas dans la pratique, c'est pourquoi Intel les a supprimés.
Cody Gray
Pour être clair, la mise en œuvre de la prédiction de branche est extrêmement compliquée et les contraintes d'espace dans les commentaires m'ont obligé à trop simplifier. Ce serait vraiment une réponse complète en soi. Il peut encore y avoir des vestiges de prédiction de branche statique dans les microarchitectures modernes, comme Haswell, mais ce n'est pas aussi simple qu'auparavant.
Cody Gray
Avez-vous une référence pour "les processeurs Intel modernes n'utilisent pas la prédiction de branche statique"? Le propre article d'Intel ( software.intel.com/en-us/articles/… ) dit le contraire ... Mais c'est de 2011
Nemo
Je n'ai pas vraiment de référence officielle, @Nemo. Intel est extrêmement discret sur les algorithmes de prédiction de branche utilisés dans ses puces, les traitant comme des secrets commerciaux. La plupart de ce qui est connu a été découvert par des tests empiriques. Comme toujours, les matériaux d'Agner Fog sont les meilleures ressources, mais même lui dit: "Le prédicteur de branche semble avoir été repensé dans le Haswell, mais on en sait très peu sur sa construction." Je ne me souviens plus où j'ai vu pour la première fois les benchmarks démontrant que la BP statique n'était plus utilisée, malheureusement.
Cody Gray
5

__builtin_expect peut être utilisé pour indiquer au compilateur dans quelle direction vous attendez une branche. Cela peut influencer la manière dont le code est généré. Les processeurs typiques exécutent le code plus rapidement de manière séquentielle. Donc si tu écris

if (__builtin_expect (x == 0, 0)) ++count;
if (__builtin_expect (y == 0, 0)) ++count;
if (__builtin_expect (z == 0, 0)) ++count;

le compilateur générera du code comme

if (x == 0) goto if1;
back1: if (y == 0) goto if2;
back2: if (z == 0) goto if3;
back3: ;
...
if1: ++count; goto back1;
if2: ++count; goto back2;
if3: ++count; goto back3;

Si votre indice est correct, cela exécutera le code sans aucune branche réellement effectuée. Il s'exécutera plus rapidement que la séquence normale, où chaque instruction if se ramifierait autour du code conditionnel et exécuterait trois branches.

Les nouveaux processeurs x86 ont des instructions pour les branches qui devraient être prises, ou pour les branches qui ne devraient pas l'être (il y a un préfixe d'instruction; pas sûr des détails). Je ne sais pas si le processeur l'utilise. Ce n'est pas très utile, car la prédiction de branche gérera cela très bien. Je ne pense donc pas que vous puissiez réellement influencer la prédiction de branche .

gnasher729
la source
2

En ce qui concerne l'OP, non, il n'y a aucun moyen dans GCC de dire au processeur de toujours supposer que la branche est ou n'est pas prise. Ce que vous avez, c'est __builtin_expect, qui fait ce que les autres disent. De plus, je pense que vous ne voulez pas dire au processeur si la branche est prise ou pas toujours . Les processeurs actuels, tels que l'architecture Intel, peuvent reconnaître des modèles assez complexes et s'adapter efficacement.

Cependant, vous souhaitez parfois contrôler si par défaut une branche est prédite prise ou non: Lorsque vous savez que le code sera appelé "froid" en ce qui concerne les statistiques de branchement.

Un exemple concret: le code de gestion des exceptions. Par définition, le code de gestion se produira exceptionnellement, mais peut-être que lorsqu'il se produira, des performances maximales sont souhaitées (il peut y avoir une erreur critique à prendre en charge dès que possible), par conséquent, vous voudrez peut-être contrôler la prédiction par défaut.

Un autre exemple: vous pouvez classer votre entrée et sauter dans le code qui gère le résultat de votre classification. S'il existe de nombreuses classifications, le processeur peut collecter des statistiques mais les perdre car la même classification ne se produit pas assez tôt et les ressources de prédiction sont consacrées au code récemment appelé. Je souhaite qu'il y ait une primitive pour dire au processeur "s'il vous plaît ne pas consacrer de ressources de prédiction à ce code" comme vous pouvez parfois dire "ne pas mettre en cache".

TheCppZoo
la source