Quel est l'effet d'ordonner si… sinon si des déclarations par probabilité?

189

Plus précisément, si j'ai une série d' instructions if... else ifet que je connais en quelque sorte à l'avance la probabilité relative à laquelle chaque instruction sera évaluée true, quelle différence de temps d'exécution cela fait-il pour les trier par ordre de probabilité? Par exemple, devrais-je préférer ceci:

if (highly_likely)
  //do something
else if (somewhat_likely)
  //do something
else if (unlikely)
  //do something

pour ça?:

if (unlikely)
  //do something
else if (somewhat_likely)
  //do something
else if (highly_likely)
  //do something

Il semble évident que la version triée serait plus rapide, mais pour la lisibilité ou l'existence d'effets secondaires, nous pourrions vouloir les commander de manière non optimale. Il est également difficile de dire à quel point le processeur fonctionnera avec la prédiction de branche jusqu'à ce que vous exécutiez réellement le code.

Donc, au cours de cette expérience, j'ai fini par répondre à ma propre question pour un cas spécifique, mais j'aimerais également entendre d'autres opinions / idées.

Important: cette question suppose que les ifinstructions peuvent être réorganisées arbitrairement sans avoir d'autres effets sur le comportement du programme. Dans ma réponse, les trois tests conditionnels s'excluent mutuellement et ne produisent aucun effet secondaire. Certes, si les déclarations doivent être évaluées dans un certain ordre pour obtenir un comportement souhaité, alors la question de l'efficacité est sans objet.

c++ performance if-statement optimization branch-prediction Carlton
la source
35
vous voudrez peut-être ajouter une note que les conditions sont mutuellement exclusives, sinon les deux versions ne sont pas équivalentes
idclev 463035818
28
Il est assez intéressant de voir comment une question auto-répondue a obtenu plus de 20 votes positifs avec une réponse plutôt médiocre, en une heure. Ne rien appeler sur OP, mais les votants positifs doivent se méfier de sauter sur un chariot à bande. La question peut être intéressante, mais les résultats sont douteux.
luk32
3
Je crois que cela peut être décrit comme une forme d' évaluation de court-circuit parce que frapper une comparaison nie frapper une comparaison différente. Personnellement, je préfère une implémentation comme celle-ci lorsqu'une comparaison rapide, disons booléenne, peut m'empêcher d'entrer dans une comparaison différente qui pourrait impliquer une manipulation de chaînes, une expression régulière ou une interaction avec une base de données.
MonkeyZeus
11
Certains compilateurs offrent la possibilité de collecter des statistiques sur les branches prises et de les renvoyer dans le compilateur pour lui permettre de faire de meilleures optimisations.
11
Si des performances comme celle-ci comptent pour vous, vous devriez probablement essayer l'optimisation guidée par profil et comparer votre résultat manuel avec le résultat du compilateur
Justin

Réponses:

97

En règle générale, la plupart des processeurs Intel, sinon tous, supposent que les branches avant ne sont pas prises la première fois qu'elles les voient. Voir le travail de Godbolt .

Après cela, la branche entre dans un cache de prédiction de branche et le comportement passé est utilisé pour informer la future prédiction de branche.

Donc, dans une boucle serrée, l'effet du désordre sera relativement faible. Le prédicteur de branche va apprendre quel ensemble de branches est le plus probable, et si vous avez une quantité de travail non négligeable dans la boucle, les petites différences ne s'ajouteront pas beaucoup.

Dans le code général, la plupart des compilateurs par défaut (sans autre raison) classeront le code machine produit à peu près comme vous l'avez commandé dans votre code. Ainsi, si les instructions sont des branches en avant lorsqu'elles échouent.

Vous devez donc classer vos branches par ordre décroissant de probabilité pour obtenir la meilleure prédiction de branche à partir d'une "première rencontre".

Un microbenchmark qui boucle étroitement plusieurs fois sur un ensemble de conditions et effectue un travail insignifiant va être dominé par de minuscules effets de nombre d'instructions et autres, et peu de problèmes relatifs de prédiction de branche. Donc, dans ce cas, vous devez profiler , car les règles empiriques ne seront pas fiables.

En plus de cela, la vectorisation et de nombreuses autres optimisations s'appliquent aux minuscules boucles serrées.

Donc, dans le code général, placez le code le plus probable dans le ifbloc, et cela entraînera le moins de ratés de prédiction de branche non mis en cache. Dans les boucles serrées, suivez la règle générale pour commencer, et si vous avez besoin d'en savoir plus, vous n'avez pas d'autre choix que de profiler.

Naturellement, tout cela passe par la fenêtre si certains tests sont beaucoup moins chers que d'autres.

Yakk - Adam Nevraumont
la source
19
Cela vaut également la peine de prendre en compte le coût des tests eux-mêmes: si un test n'est que légèrement plus probable, mais beaucoup plus cher, il peut être intéressant de mettre l'autre test en premier, car les économies réalisées en ne faisant pas le test coûteux l'emporteront probablement économies grâce à la prédiction des succursales, etc.
psmears
Le lien que vous avez fourni ne confirme pas votre conclusion En règle générale, la plupart sinon tous les processeurs Intel supposent que les branches avant ne sont pas prises la première fois qu'elles les voient . En fait, cela n'est vrai que pour le processeur Arrendale relativement obscur dont les résultats sont affichés en premier. Les résultats traditionnels d'Ivy Bridge et Haswell ne soutiennent pas du tout cela. Haswell semble très proche de "toujours prédire la chute" pour les branches invisibles, et Ivy Bridge n'est pas clair du tout.
BeeOnRope
Il est généralement entendu que les processeurs n'utilisent pas vraiment de prédictions statiques comme ils le faisaient dans le passé. En effet, Intel moderne utilise probablement quelque chose comme un prédicteur probabiliste TAGE. Vous n'avez qu'à hacher l'historique des branches dans diverses tables d'historique et en prendre une qui correspond à l'histoire la plus longue. Il utilise une "balise" pour essayer d'éviter les alias, mais la balise ne contient que quelques bits. Si vous manquez à toutes les longueurs d'historique, une prédiction par défaut est probablement faite qui ne dépend pas nécessairement de la direction de la branche (sur Haswell, nous pouvons dire que ce n'est clairement pas le cas).
BeeOnRope
44

J'ai composé le test suivant pour chronométrer l'exécution de deux blocs if... différents else if, l'un trié par ordre de probabilité, l'autre trié dans l'ordre inverse:

#include <chrono>
#include <iostream>
#include <random>
#include <algorithm>
#include <iterator>
#include <functional>

using namespace std;

int main()
{
    long long sortedTime = 0;
    long long reverseTime = 0;

    for (int n = 0; n != 500; ++n)
    {
        //Generate a vector of 5000 random integers from 1 to 100
        random_device rnd_device;
        mt19937 rnd_engine(rnd_device());
        uniform_int_distribution<int> rnd_dist(1, 100);
        auto gen = std::bind(rnd_dist, rnd_engine);
        vector<int> rand_vec(5000);
        generate(begin(rand_vec), end(rand_vec), gen);

        volatile int nLow, nMid, nHigh;
        chrono::time_point<chrono::high_resolution_clock> start, end;

        //Sort the conditional statements in order of increasing likelyhood
        nLow = nMid = nHigh = 0;
        start = chrono::high_resolution_clock::now();
        for (int& i : rand_vec) {
            if (i >= 95) ++nHigh;               //Least likely branch
            else if (i < 20) ++nLow;
            else if (i >= 20 && i < 95) ++nMid; //Most likely branch
        }
        end = chrono::high_resolution_clock::now();
        reverseTime += chrono::duration_cast<chrono::nanoseconds>(end-start).count();

        //Sort the conditional statements in order of decreasing likelyhood
        nLow = nMid = nHigh = 0;
        start = chrono::high_resolution_clock::now();
        for (int& i : rand_vec) {
            if (i >= 20 && i < 95) ++nMid;  //Most likely branch
            else if (i < 20) ++nLow;
            else if (i >= 95) ++nHigh;      //Least likely branch
        }
        end = chrono::high_resolution_clock::now();
        sortedTime += chrono::duration_cast<chrono::nanoseconds>(end-start).count();

    }

    cout << "Percentage difference: " << 100 * (double(reverseTime) - double(sortedTime)) / double(sortedTime) << endl << endl;
}

En utilisant MSVC2017 avec / O2, les résultats montrent que la version triée est systématiquement environ 28% plus rapide que la version non triée. Selon le commentaire de luk32, j'ai également changé l'ordre des deux tests, ce qui fait une différence notable (22% vs 28%). Le code a été exécuté sous Windows 7 sur un Intel Xeon E5-2697 v2. Ceci, bien sûr, est très spécifique au problème et ne doit pas être interprété comme une réponse concluante.

Carlton
la source
9
OP doit cependant être prudent, car la modification d'une if... else ifinstruction peut avoir un effet substantiel sur la façon dont la logique circule dans le code. La unlikelyvérification peut ne pas apparaître souvent, mais il pourrait être nécessaire de vérifier la unlikelycondition avant de vérifier les autres.
Luke T Brooks
21
30% plus rapide? Vous voulez dire que c'était plus rapide d'environ le% de déclarations supplémentaires si cela n'était pas nécessaire? Semble un résultat assez raisonnable.
UKMonkey
5
Comment l'avez-vous évalué? Quel compilateur, cpu, etc.? Je suis presque sûr que ce résultat n'est pas portable.
luk32
12
Un problème avec ce microbenchmark est que le processeur va déterminer laquelle des branches est la plus probable et la mettre en cache lorsque vous la bouclez à plusieurs reprises. Si les branches n'étaient pas examinées dans une petite boucle serrée, le cache de prédiction de branche pourrait ne pas les contenir, et les coûts pourraient être beaucoup plus élevés si le processeur devine mal avec zéro guidage de cache de prédiction de branche.
Yakk - Adam Nevraumont
6
Ce benchmark n'est pas trop fiable. Compiler avec gcc 6.3.0 : g++ -O2 -march=native -std=c++14donne un léger avantage aux instructions conditionnelles triées, mais la plupart du temps, la différence en pourcentage entre les deux exécutions était d'environ 5%. Plusieurs fois, c'était en fait plus lent (en raison de variances). Je suis assez sûr que commander les ifs comme ça ne vaut pas la peine de s'inquiéter; PGO gérera probablement complètement de tels cas
Justin
30

Non, vous ne devriez pas, sauf si vous êtes vraiment sûr que le système cible est affecté. Par défaut, optez pour la lisibilité.

Je doute fortement de vos résultats. J'ai un peu modifié votre exemple, il est donc plus facile d'inverser l'exécution. Ideone montre de manière assez cohérente que l'ordre inverse est plus rapide, mais pas beaucoup. Sur certaines pistes, même cela a parfois changé. Je dirais que les résultats ne sont pas concluants. coliru ne rapporte pas non plus de réelle différence. Je peux vérifier le processeur Exynos5422 sur mon odroid xu4 plus tard.

Le fait est que les processeurs modernes ont des prédicteurs de branche. Il y a beaucoup de logique dédiée à la pré-extraction à la fois des données et des instructions, et les processeurs x86 modernes sont plutôt intelligents à ce sujet. Certaines architectures plus minces comme les ARM ou les GPU peuvent être vulnérables à cela. Mais cela dépend vraiment à la fois du compilateur et du système cible.

Je dirais que l'optimisation des commandes de succursales est assez fragile et éphémère. Ne le faites que comme une étape de réglage vraiment fine.

Code:

#include <chrono>
#include <iostream>
#include <random>
#include <algorithm>
#include <iterator>
#include <functional>

using namespace std;

int main()
{
    //Generate a vector of random integers from 1 to 100
    random_device rnd_device;
    mt19937 rnd_engine(rnd_device());
    uniform_int_distribution<int> rnd_dist(1, 100);
    auto gen = std::bind(rnd_dist, rnd_engine);
    vector<int> rand_vec(5000);
    generate(begin(rand_vec), end(rand_vec), gen);
    volatile int nLow, nMid, nHigh;

    //Count the number of values in each of three different ranges
    //Run the test a few times
    for (int n = 0; n != 10; ++n) {

        //Run the test again, but now sort the conditional statements in reverse-order of likelyhood
        {
          nLow = nMid = nHigh = 0;
          auto start = chrono::high_resolution_clock::now();
          for (int& i : rand_vec) {
              if (i >= 95) ++nHigh;               //Least likely branch
              else if (i < 20) ++nLow;
              else if (i >= 20 && i < 95) ++nMid; //Most likely branch
          }
          auto end = chrono::high_resolution_clock::now();
          cout << "Reverse-sorted: \t" << chrono::duration_cast<chrono::nanoseconds>(end-start).count() << "ns" << endl;
        }

        {
          //Sort the conditional statements in order of likelyhood
          nLow = nMid = nHigh = 0;
          auto start = chrono::high_resolution_clock::now();
          for (int& i : rand_vec) {
              if (i >= 20 && i < 95) ++nMid;  //Most likely branch
              else if (i < 20) ++nLow;
              else if (i >= 95) ++nHigh;      //Least likely branch
          }
          auto end = chrono::high_resolution_clock::now();
          cout << "Sorted:\t\t\t" << chrono::duration_cast<chrono::nanoseconds>(end-start).count() << "ns" << endl;
        }
        cout << endl;
    }
}
luk32
la source
J'obtiens la même différence d'environ 30% de performances lorsque je change l'ordre des blocs if triés et triés inversement, comme cela a été fait dans votre code. Je ne sais pas pourquoi Ideone et coliru ne montrent aucune différence.
Carlton
Certainement intéressant. J'essaierai d'obtenir des données pour d'autres systèmes, mais cela peut prendre un jour avant que je doive jouer avec. La question est intéressante, surtout à la lumière de vos résultats, mais ils sont tellement spectaculaires que j'ai dû la recouper.
luk32
Si la question est quel est l'effet? la réponse ne peut pas être non !
PJTraill
Ouaip. Mais je ne reçois pas de notifications pour les mises à jour de la question d'origine. Ils ont rendu la formulation des réponses obsolète. Pardon. Je modifierai le contenu plus tard, pour souligner qu'il a répondu à la question originale et montré quelques résultats qui ont prouvé le point d'origine.
luk32
Cela vaut la peine de le répéter: "Par défaut, optez pour la lisibilité." L'écriture de code lisible vous donnera souvent de meilleurs résultats que d'essayer d'augmenter les performances (en termes absolus) en rendant votre code plus difficile à analyser pour les humains.
Andrew Brēza
27

Juste mes 5 cents. Il semble que l'effet de l'ordre si les instructions doivent dépendre de:

  1. Probabilité de chaque instruction if.

  2. Nombre d'itérations, de sorte que le prédicteur de branche puisse intervenir.

  3. Conseils de compilation probables / improbables, c'est-à-dire la disposition du code.

Pour explorer ces facteurs, j'ai comparé les fonctions suivantes:

ordonné_ifs ()

for (i = 0; i < data_sz * 1024; i++) {
    if (data[i] < check_point) // highly likely
        s += 3;
    else if (data[i] > check_point) // samewhat likely
        s += 2;
    else if (data[i] == check_point) // very unlikely
        s += 1;
}

reverse_ifs ()

for (i = 0; i < data_sz * 1024; i++) {
    if (data[i] == check_point) // very unlikely
        s += 1;
    else if (data[i] > check_point) // samewhat likely
        s += 2;
    else if (data[i] < check_point) // highly likely
        s += 3;
}

order_ifs_with_hints ()

for (i = 0; i < data_sz * 1024; i++) {
    if (likely(data[i] < check_point)) // highly likely
        s += 3;
    else if (data[i] > check_point) // samewhat likely
        s += 2;
    else if (unlikely(data[i] == check_point)) // very unlikely
        s += 1;
}

reverse_ifs_with_hints ()

for (i = 0; i < data_sz * 1024; i++) {
    if (unlikely(data[i] == check_point)) // very unlikely
        s += 1;
    else if (data[i] > check_point) // samewhat likely
        s += 2;
    else if (likely(data[i] < check_point)) // highly likely
        s += 3;
}

Les données

Le tableau de données contient des nombres aléatoires entre 0 et 100:

const int RANGE_MAX = 100;
uint8_t data[DATA_MAX * 1024];

static void data_init(int data_sz)
{
    int i;
        srand(0);
    for (i = 0; i < data_sz * 1024; i++)
        data[i] = rand() % RANGE_MAX;
}

Les resultats

Les résultats suivants concernent Intel i5 @ 3,2 GHz et G ++ 6.3.0. Le premier argument est le point de contrôle (c'est-à-dire la probabilité en %% pour l'instruction if hautement probable), le second argument est data_sz (c'est-à-dire le nombre d'itérations).

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4                    4660 ns       4658 ns     150948
ordered_ifs/50/8                   25636 ns      25635 ns      27852
ordered_ifs/75/4                    4326 ns       4325 ns     162613
ordered_ifs/75/8                   18242 ns      18242 ns      37931
ordered_ifs/100/4                   1673 ns       1673 ns     417073
ordered_ifs/100/8                   3381 ns       3381 ns     207612
reversed_ifs/50/4                   5342 ns       5341 ns     126800
reversed_ifs/50/8                  26050 ns      26050 ns      26894
reversed_ifs/75/4                   3616 ns       3616 ns     193130
reversed_ifs/75/8                  15697 ns      15696 ns      44618
reversed_ifs/100/4                  3738 ns       3738 ns     188087
reversed_ifs/100/8                  7476 ns       7476 ns      93752
ordered_ifs_with_hints/50/4         5551 ns       5551 ns     125160
ordered_ifs_with_hints/50/8        23191 ns      23190 ns      30028
ordered_ifs_with_hints/75/4         3165 ns       3165 ns     218492
ordered_ifs_with_hints/75/8        13785 ns      13785 ns      50574
ordered_ifs_with_hints/100/4        1575 ns       1575 ns     437687
ordered_ifs_with_hints/100/8        3130 ns       3130 ns     221205
reversed_ifs_with_hints/50/4        6573 ns       6572 ns     105629
reversed_ifs_with_hints/50/8       27351 ns      27351 ns      25568
reversed_ifs_with_hints/75/4        3537 ns       3537 ns     197470
reversed_ifs_with_hints/75/8       16130 ns      16130 ns      43279
reversed_ifs_with_hints/100/4       3737 ns       3737 ns     187583
reversed_ifs_with_hints/100/8       7446 ns       7446 ns      93782

Une analyse

1. La commande compte

Pour les itérations 4K et (presque) 100% de probabilité d'une déclaration très appréciée, la différence est énorme de 223%:

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/100/4                   1673 ns       1673 ns     417073
reversed_ifs/100/4                  3738 ns       3738 ns     188087

Pour les itérations 4K et 50% de probabilité d'énoncé très apprécié, la différence est d'environ 14%:

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4                    4660 ns       4658 ns     150948
reversed_ifs/50/4                   5342 ns       5341 ns     126800

2. Le nombre d'itérations compte

La différence entre les itérations 4K et 8K pour une probabilité (presque) de 100% d'une déclaration très appréciée est environ deux fois (comme prévu):

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/100/4                   1673 ns       1673 ns     417073
ordered_ifs/100/8                   3381 ns       3381 ns     207612

Mais la différence entre les itérations 4K et 8K pour une probabilité de 50% d'une déclaration très appréciée est de 5,5 fois:

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4                    4660 ns       4658 ns     150948
ordered_ifs/50/8                   25636 ns      25635 ns      27852

Pourquoi cela? En raison des échecs du prédicteur de branche. Voici la branche manquante pour chaque cas mentionné ci-dessus:

ordered_ifs/100/4    0.01% of branch-misses
ordered_ifs/100/8    0.01% of branch-misses
ordered_ifs/50/4     3.18% of branch-misses
ordered_ifs/50/8     15.22% of branch-misses

Ainsi, sur mon i5, le prédicteur de branche échoue de manière spectaculaire pour les branches peu probables et les grands ensembles de données.

3. Les astuces aident un peu

Pour les itérations 4K, les résultats sont quelque peu pires pour une probabilité de 50% et un peu meilleurs pour une probabilité proche de 100%:

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4                    4660 ns       4658 ns     150948
ordered_ifs/100/4                   1673 ns       1673 ns     417073
ordered_ifs_with_hints/50/4         5551 ns       5551 ns     125160
ordered_ifs_with_hints/100/4        1575 ns       1575 ns     437687

Mais pour les itérations 8K, les résultats sont toujours un peu meilleurs:

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/8                   25636 ns      25635 ns      27852
ordered_ifs/100/8                   3381 ns       3381 ns     207612
ordered_ifs_with_hints/50/8        23191 ns      23190 ns      30028
ordered_ifs_with_hints/100/8        3130 ns       3130 ns     221205

Donc, les indices aident également, mais juste un tout petit peu.

La conclusion générale est la suivante: comparez toujours le code, car les résultats peuvent surprendre.

J'espère que ça t'as aidé.

Andriy Berestovskyy
la source
1
i5 Nehalem? i5 Skylake? Le simple fait de dire "i5" n'est pas très précis. De plus, je suppose que vous avez utilisé g++ -O2ou -O3 -fno-tree-vectorize, mais vous devriez le dire.
Peter Cordes
Il est intéressant de noter que with_hints est toujours différent pour ordonné et inversé. Ce serait bien si vous vous connectiez à la source quelque part. (par exemple, un lien Godbolt, de préférence un lien complet pour que le raccourcissement du lien ne puisse pas pourrir.)
Peter Cordes
1
Le fait que le prédicteur de branche soit capable de bien prédire même à la taille de données d'entrée 4K, c'est-à-dire qu'il soit capable de «casser» le repère en se souvenant des résultats de branche à travers une boucle avec une période de plusieurs milliers, témoigne de la puissance de la modernité prédicteurs de branche. Gardez à l'esprit que les prédicteurs sont assez sensibles dans certains cas à des choses comme l'alignement, il est donc difficile de tirer des conclusions solides sur certains changements. Par exemple, vous avez remarqué un comportement opposé pour l'indicateur dans différents cas, mais cela pourrait être expliqué par l'indication changeant de manière aléatoire la disposition du code qui affectait le prédicteur.
BeeOnRope
1
@PeterCordes mon point principal est que si nous pouvons essayer de prédire les résultats d'un changement, nous mesurons quand même mieux les performances avant et après le changement ... Et vous avez raison, j'aurais dû mentionner qu'il a été optimisé avec -O3 et le processeur est i5-4460 à 3,20 GHz
Andriy Berestovskyy
19

Sur la base de certaines des autres réponses ici, il semble que la seule vraie réponse soit: cela dépend . Cela dépend au moins des éléments suivants (mais pas nécessairement dans cet ordre d'importance):

  • Probabilité relative de chaque branche. C'est la question initiale qui a été posée. Sur la base des réponses existantes, il semble y avoir certaines conditions dans lesquelles l'ordre par probabilité aide, mais cela ne semble pas toujours être le cas. Si les probabilités relatives ne sont pas très différentes, l'ordre dans lequel elles se trouvent est peu susceptible de faire une différence. Cependant, si la première condition se produit 99,999% du temps et que la suivante est une fraction de ce qui reste, alors je le ferais supposons que mettre le plus probable en premier serait bénéfique en termes de timing.
  • Coût du calcul de la condition vrai / faux pour chaque branche. Si le coût en temps du test des conditions est vraiment élevé pour une branche par rapport à une autre, cela aura probablement un impact significatif sur le calendrier et l'efficacité. Par exemple, considérons une condition qui prend 1 unité de temps à calculer (par exemple, vérifier l'état d'une variable booléenne) par rapport à une autre condition qui prend des dizaines, des centaines, des milliers ou même des millions d'unités de temps à calculer (par exemple, vérifier le contenu de un fichier sur disque ou effectuer une requête SQL complexe sur une base de données volumineuse). En supposant que le code vérifie les conditions dans l'ordre à chaque fois, les conditions les plus rapides devraient probablement être les premières (à moins qu'elles ne dépendent d'autres conditions qui échouent en premier).
  • Compilateur / Interprète Certains compilateurs (ou interprètes) peuvent inclure des optimisations d'un type d'un autre qui peuvent affecter les performances (et certains d'entre eux ne sont présents que si certaines options sont sélectionnées pendant la compilation et / ou l'exécution). Donc, à moins que vous ne compariez deux compilations et exécutions de code par ailleurs identique sur le même système en utilisant exactement le même compilateur où la seule différence est l'ordre des branches en question, vous allez devoir donner une certaine marge de manœuvre pour les variations du compilateur.
  • Système d'exploitation / matériel Comme mentionné par luk32 et Yakk, divers processeurs ont leurs propres optimisations (tout comme les systèmes d'exploitation). Les benchmarks sont donc à nouveau susceptibles de varier ici.
  • Fréquence d'exécution du bloc de code Si le bloc qui comprend les branches est rarement accédé (par exemple, une seule fois au démarrage), alors l'ordre dans lequel vous placez les branches importe probablement très peu. D'un autre côté, si votre code martèle ce bloc de code pendant une partie critique de votre code, la commande peut avoir beaucoup d'importance (en fonction des benchmarks).

Le seul moyen de savoir avec certitude est de comparer votre cas spécifique, de préférence sur un système identique (ou très similaire) au système prévu sur lequel le code fonctionnera finalement. S'il est destiné à fonctionner sur un ensemble de systèmes différents avec un matériel, un système d'exploitation, etc. différents, alors il est judicieux de comparer plusieurs variantes pour voir laquelle est la meilleure. Il peut même être judicieux de compiler le code avec une commande sur un type de système et une autre commande sur un autre type de système.

Ma règle de base personnelle (dans la plupart des cas, en l'absence de référence) est de commander en fonction:

  1. Conditions qui reposent sur le résultat de conditions antérieures,
  2. Coût du calcul de la condition, puis
  3. Probabilité relative de chaque branche.
Ampersat
la source
13

La façon dont je vois généralement cela résolu pour le code haute performance est de garder l'ordre qui est le plus lisible, mais de fournir des conseils au compilateur. Voici un exemple du noyau Linux :

if (likely(access_ok(VERIFY_READ, from, n))) {
    kasan_check_write(to, n);
    res = raw_copy_from_user(to, from, n);
}
if (unlikely(res))
    memset(to + (n - res), 0, res);

Ici, l'hypothèse est que le contrôle d'accès réussira et qu'aucune erreur n'est renvoyée res. Essayer de réorganiser l'une ou l'autre de ces clauses if ne ferait que semer la confusion dans le code, mais les macros likely()et unlikely()facilitent en fait la lisibilité en indiquant quel est le cas normal et quelle est l'exception.

L'implémentation Linux de ces macros utilise des fonctionnalités spécifiques à GCC . Il semble que clang et le compilateur Intel C prennent en charge la même syntaxe, mais MSVC n'a pas une telle fonctionnalité .

jpa
la source
4
Ce serait plus utile si vous pouviez expliquer comment les macros likely()et unlikely()sont définies et inclure des informations sur la fonctionnalité de compilateur correspondante.
Nate Eldredge
1
AFAIK, ces conseils modifient "seulement" la disposition de la mémoire des blocs de code et si un oui ou un non mènera à un saut. Cela peut avoir des avantages en termes de performances, par exemple en raison du besoin (ou de l'absence de celui-ci) de lire des pages de mémoire. Mais cela ne réorganise pas l'ordre dans lequel les conditions dans une longue liste d'autres-ifs sont évaluées
Hagen von Eitzen
@HagenvonEitzen Hmm ouais, c'est un bon point, cela ne peut pas affecter l'ordre de else ifsi le compilateur n'est pas assez intelligent pour savoir que les conditions sont mutuellement exclusives.
jpa
7

Dépend également de votre compilateur et de la plate-forme pour laquelle vous compilez.

En théorie, la condition la plus probable devrait réduire le plus possible le saut de commande.

En règle générale, la condition la plus probable devrait être la première:

if (most_likely) {
     // most likely instructions
} else …

Les asm les plus populaires sont basés sur des branches conditionnelles qui sautent lorsque la condition est vraie . Ce code C sera probablement traduit en un tel pseudo asm:

jump to ELSE if not(most_likely)
// most likely instructions
jump to end
ELSE:
…

C'est parce que les sauts font que le processeur annule le pipeline d'exécution et se bloque parce que le compteur du programme a changé (pour les architectures qui prennent en charge les pipelines qui sont vraiment courants). Ensuite, il s'agit du compilateur, qui peut ou non appliquer des optimisations sophistiquées sur la condition statistiquement la plus probable pour que le contrôle fasse moins de sauts.

NoImaginationGuy
la source
2
Vous avez déclaré que la branche conditionnelle se produit lorsque la condition est vraie, mais l'exemple "pseudo asm" montre le contraire. De plus, on ne peut pas dire que les sauts conditionnels (et encore moins tous les sauts) bloquent le pipeline car les processeurs modernes ont généralement une prédiction de branche. En fait, s'il est prévu que la branche soit prise mais pas prise, le pipeline sera bloqué. J'essaierais toujours de trier les conditions par ordre décroissant de probabilité, mais ce que le compilateur et le processeur en font dépend fortement de la mise en œuvre.
Arne Vogel
1
Je mets «pas (le plus probable)» donc si le plus probable est vrai, le contrôle continuera sans sauter.
NoImaginationGuy
1
"Les asm les plus populaires sont basés sur des branches conditionnelles qui sautent lorsque la condition est vraie" .. de quelles ISA s'agit-il? Ce n'est certainement pas vrai pour x86 ni pour ARM. Enfer pour les processeurs ARM de base (et les très anciens x86, même pour les bps complexes, ils commencent généralement avec cette hypothèse puis s'adaptent), le prédicteur de branche suppose qu'une branche avant n'est pas prise et que les branches arrière le sont toujours, donc le contraire de l'affirmation est vrai.
Voo
1
Les compilateurs que j'ai essayés la plupart du temps ont tous utilisé l'approche que j'ai mentionnée ci-dessus pour un test simple. Notez qu'en clangfait, a adopté une approche différente pour test2et test3: en raison des heuristiques qui indiquent qu'un test < 0ou == 0est susceptible d'être faux, il a décidé de cloner le reste de la fonction sur les deux chemins, de sorte qu'il est capable de faire condition == falsetomber le chemin. Cela n'est faisable que parce que le reste de la fonction est court: test4j'ai ajouté une opération de plus et c'est de retour à l'approche que j'ai décrite ci-dessus.
BeeOnRope
1
@ArneVogel - branches prises prédites correctement ne pas totalement bloquer le pipeline sur les processeurs modernes , mais ils sont encore souvent bien pire que pas pris: (1) ils veulent dire le flux de contrôle ne soit pas accolée de sorte que le reste des instructions après le jmpsont pas utile pour récupérer / décoder la bande passante est gaspillée (2) même avec la prédiction les gros cœurs modernes ne font qu'une extraction par cycle, ce qui met une limite stricte de 1 branche / cycle pris (OTOH moderne Intel peut faire 2 non-pris / cycle) (3 ) il est plus difficile pour la prédiction de branche de gérer les branches consécutives prises et dans le cas de prédicteurs rapides + lents ...
BeeOnRope
6

J'ai décidé de réexécuter le test sur ma propre machine en utilisant le code Lik32. J'ai dû le changer car mes fenêtres ou mon compilateur pensaient que la haute résolution était de 1 ms, en utilisant

mingw32-g ++. exe -O3 -Wall -std = c ++ 11 -fexceptions -g

vector<int> rand_vec(10000000);

GCC a effectué la même transformation sur les deux codes d'origine.

Notez que seules les deux premières conditions sont testées car la troisième doit toujours être vraie, GCC est ici une sorte de Sherlock.

Inverser

.L233:
        mov     DWORD PTR [rsp+104], 0
        mov     DWORD PTR [rsp+100], 0
        mov     DWORD PTR [rsp+96], 0
        call    std::chrono::_V2::system_clock::now()
        mov     rbp, rax
        mov     rax, QWORD PTR [rsp+8]
        jmp     .L219
.L293:
        mov     edx, DWORD PTR [rsp+104]
        add     edx, 1
        mov     DWORD PTR [rsp+104], edx
.L217:
        add     rax, 4
        cmp     r14, rax
        je      .L292
.L219:
        mov     edx, DWORD PTR [rax]
        cmp     edx, 94
        jg      .L293 // >= 95
        cmp     edx, 19
        jg      .L218 // >= 20
        mov     edx, DWORD PTR [rsp+96]
        add     rax, 4
        add     edx, 1 // < 20 Sherlock
        mov     DWORD PTR [rsp+96], edx
        cmp     r14, rax
        jne     .L219
.L292:
        call    std::chrono::_V2::system_clock::now()

.L218: // further down
        mov     edx, DWORD PTR [rsp+100]
        add     edx, 1
        mov     DWORD PTR [rsp+100], edx
        jmp     .L217

And sorted

        mov     DWORD PTR [rsp+104], 0
        mov     DWORD PTR [rsp+100], 0
        mov     DWORD PTR [rsp+96], 0
        call    std::chrono::_V2::system_clock::now()
        mov     rbp, rax
        mov     rax, QWORD PTR [rsp+8]
        jmp     .L226
.L296:
        mov     edx, DWORD PTR [rsp+100]
        add     edx, 1
        mov     DWORD PTR [rsp+100], edx
.L224:
        add     rax, 4
        cmp     r14, rax
        je      .L295
.L226:
        mov     edx, DWORD PTR [rax]
        lea     ecx, [rdx-20]
        cmp     ecx, 74
        jbe     .L296
        cmp     edx, 19
        jle     .L297
        mov     edx, DWORD PTR [rsp+104]
        add     rax, 4
        add     edx, 1
        mov     DWORD PTR [rsp+104], edx
        cmp     r14, rax
        jne     .L226
.L295:
        call    std::chrono::_V2::system_clock::now()

.L297: // further down
        mov     edx, DWORD PTR [rsp+96]
        add     edx, 1
        mov     DWORD PTR [rsp+96], edx
        jmp     .L224

Donc, cela ne nous dit pas grand-chose sauf que le dernier cas n'a pas besoin d'une prédiction de branche.

Maintenant, j'ai essayé les 6 combinaisons de if, les 2 premiers sont l'inverse d'origine et triés. haut est> = 95, bas est <20, milieu est 20-94 avec 10000000 itérations chacun.

high, low, mid: 43000000ns
mid, low, high: 46000000ns
high, mid, low: 45000000ns
low, mid, high: 44000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns

high, low, mid: 44000000ns
mid, low, high: 47000000ns
high, mid, low: 44000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 45000000ns

high, low, mid: 43000000ns
mid, low, high: 47000000ns
high, mid, low: 44000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns

high, low, mid: 42000000ns
mid, low, high: 46000000ns
high, mid, low: 46000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 43000000ns

high, low, mid: 43000000ns
mid, low, high: 47000000ns
high, mid, low: 44000000ns
low, mid, high: 44000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns

high, low, mid: 43000000ns
mid, low, high: 48000000ns
high, mid, low: 44000000ns
low, mid, high: 44000000ns
mid, high, low: 45000000ns
low, high, mid: 45000000ns

high, low, mid: 43000000ns
mid, low, high: 47000000ns
high, mid, low: 45000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns

high, low, mid: 43000000ns
mid, low, high: 47000000ns
high, mid, low: 45000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns

high, low, mid: 43000000ns
mid, low, high: 46000000ns
high, mid, low: 45000000ns
low, mid, high: 45000000ns
mid, high, low: 45000000ns
low, high, mid: 44000000ns

high, low, mid: 42000000ns
mid, low, high: 46000000ns
high, mid, low: 44000000ns
low, mid, high: 45000000ns
mid, high, low: 45000000ns
low, high, mid: 44000000ns

1900020, 7498968, 601012

Process returned 0 (0x0)   execution time : 2.899 s
Press any key to continue.

Alors pourquoi l'ordre est-il haut, bas, moyen puis plus rapide (marginalement)

Parce que le plus imprévisible est le dernier et n'est donc jamais exécuté via un prédicteur de branche.

          if (i >= 95) ++nHigh;               // most predictable with 94% taken
          else if (i < 20) ++nLow; // (94-19)/94% taken ~80% taken
          else if (i >= 20 && i < 95) ++nMid; // never taken as this is the remainder of the outfalls.

Ainsi, les branches seront prédites prises, prises et le reste avec

6% + (0,94 *) 20% de faux pronostics.

"Trié"

          if (i >= 20 && i < 95) ++nMid;  // 75% not taken
          else if (i < 20) ++nLow;        // 19/25 76% not taken
          else if (i >= 95) ++nHigh;      //Least likely branch

Les branches seront prédites avec non prises, non prises et Sherlock.

25% + (0,75 *) 24% de faux pronostics

Donnant une différence de 18 à 23% (différence mesurée de ~ 9%), mais nous devons calculer les cycles au lieu de mal prévoir le%.

Supposons que 17 cycles de pénalité de mauvaise prédiction sur mon processeur Nehalem et que chaque vérification prend 1 cycle à émettre (4-5 instructions) et que la boucle prend également un cycle. Les dépendances de données sont les compteurs et les variables de boucle, mais une fois que les erreurs de prédiction sont écartées, cela ne devrait pas influencer le timing.

Donc, pour "inverser", nous obtenons les horaires (cela devrait être la formule utilisée dans Computer Architecture: A Quantitative Approach IIRC).

mispredict*penalty+count+loop
0.06*17+1+1+    (=3.02)
(propability)*(first check+mispredict*penalty+count+loop)
(0.19)*(1+0.20*17+1+1)+  (= 0.19*6.4=1.22)
(propability)*(first check+second check+count+loop)
(0.75)*(1+1+1+1) (=3)
= 7.24 cycles per iteration

et la même chose pour "trié"

0.25*17+1+1+ (=6.25)
(1-0.75)*(1+0.24*17+1+1)+ (=.25*7.08=1.77)
(1-0.75-0.19)*(1+1+1+1)  (= 0.06*4=0.24)
= 8.26

(8,26-7,24) /8,26 = 13,8% vs ~ 9% mesuré (proche du mesuré!?!).

Donc, l'évidence du PO n'est pas évidente.

Avec ces tests, d'autres tests avec du code plus compliqué ou plus de dépendances de données seront certainement différents alors mesurez votre cas.

La modification de l'ordre du test a changé les résultats, mais cela pourrait être dû à des alignements différents du début de la boucle qui devrait idéalement être aligné sur 16 octets sur tous les nouveaux processeurs Intel, mais ce n'est pas le cas dans ce cas.

Surt
la source
4

Mettez-les dans l'ordre logique de votre choix. Bien sûr, la branche peut être plus lente, mais la branche ne devrait pas être la majorité du travail effectué par votre ordinateur.

Si vous travaillez sur une partie du code critique pour les performances, utilisez certainement l'ordre logique, l'optimisation guidée par le profil et d'autres techniques, mais pour le code général, je pense que c'est vraiment plus un choix stylistique.

Jack
la source
6
Les échecs de prédiction de branche sont coûteux. Dans les microbenchmarks, ils sont sous -évalués, car les x86 ont une grande table de prédicteurs de branche. Une boucle serrée sur les mêmes conditions permet au processeur de savoir mieux que vous lequel est le plus probable. Mais si vous avez des branches partout dans votre code, vous pouvez avoir votre cache de prédiction de branche à court d'emplacements, et le processeur suppose ce qui est par défaut. Connaître cette estimation par défaut peut sauver des cycles dans toute votre base de code.
Yakk - Adam Nevraumont
La réponse de @Yakk Jack est la seule correcte ici. N'effectuez pas d'optimisations qui réduisent la lisibilité si votre compilateur est capable de faire cette optimisation. Vous ne feriez pas de pliage constant, d'élimination de code mort, de déroulement de boucle ou toute autre optimisation si votre compilateur le fait pour vous, n'est-ce pas? Écrivez votre code, utilisez l'optimisation guidée par profil (qui est conçue pour résoudre ce problème car les codeurs sont nulles de deviner), puis voyez si votre compilateur l'optimise ou non. En fin de compte, vous ne voulez pas avoir de branche dans le code critique de performance de toute façon.
Christoph Diegelmann
@Christoph Je n'inclurais pas de code que je savais mort. Je n'utiliserais pas i++quand ++ile ferais, car je suis conscient que i++pour certains itérateurs, il est difficile d'optimiser ++iet la différence (pour moi) n'a pas d'importance. Il s'agit d'éviter la pessimisation; mettre le bloc le plus probable en premier comme habitude par défaut n'entraînera pas de réduction notable de la lisibilité (et pourrait réellement aider!), tout en aboutissant à un code compatible avec la prédiction de branche (et vous donnant ainsi une petite amélioration uniforme des performances qui ne peut pas être recapturée par micro optimisation ultérieure)
Yakk - Adam Nevraumont
3

Si vous connaissez déjà la probabilité relative de l'instruction if-else, alors à des fins de performance, il serait préférable d'utiliser la méthode triée, car elle ne vérifiera qu'une seule condition (la vraie).

D'une manière non triée, le compilateur vérifiera toutes les conditions inutilement et prendra du temps.

aditya rawat
la source