Quel est l'effet de la commande si ... sinon si les déclarations par probabilité?

Question

Plus précisément, si j'ai une série de if...else if des déclarations, et j'ai un peu savoir à l'avance la probabilité relative que chaque énoncé évaluer à l' true, comment beaucoup de différence dans le temps d'exécution est-il pour les trier par ordre de probabilité? Par exemple, je préfère ceci:

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

à ceci?:

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, cependant pour des raisons de lisibilité ou de l'existence d'effets secondaires, on peut vouloir ordonnance de non-optimale. Il est également difficile de dire combien le CPU fait avec la direction de la prévision jusqu'à ce que vous exécutez le code.

Ainsi, dans le cours de l'essai de ce type, j'ai fini par répondre à ma propre question pour un cas spécifique, cependant j'aimerais entendre d'autres opinions/idées ainsi.

Important: cette question suppose que l' if déclarations peuvent être réorganisées de manière arbitraire, sans avoir d'autres effets sur le comportement du programme. Dans ma réponse, les trois tests conditionnels sont mutuellement exclusives et ne produisent pas d'effets secondaires. Certainement, si la déclaration doit être évaluée dans un certain ordre pour atteindre certains comportement désiré, puis la question de l'efficacité est discutable.

Answer 1

En règle générale, la plupart, si pas tous les Processeurs Intel assumer en avant des branches ne sont pas prises, la première fois qu'ils les voient. Voir Godbolt du travail.

Après cela, la direction générale va dans une direction de la prévision cache, et le comportement passé est utilisé pour informer les futures direction de la prévision.

Donc dans une boucle serrée, l'effet de misordering va être relativement faible. La direction de la prédicteur est pour apprendre l'ensemble des branches est le plus probable, et si vous avez le montant non négligeable de travail dans la boucle les petites différences ne sera pas ajouter beaucoup plus haut.

En général, le code, la plupart des compilateurs par défaut (manque une autre raison) sera de l'ordre de la machine produite code à peu près la façon dont vous l'avez commandé dans votre code. Ainsi, si des instructions sont en avant des branches quand ils échouent.

Donc, vous devez commander vos branches dans l'ordre décroissant de probabilité pour obtenir le meilleur, direction de la prévision à partir d'une "première rencontre".

Un microbenchmark que les boucles étroitement à de nombreuses reprises sur un ensemble de conditions et de ne trivial travail dominé par de petits effets de l'instruction, le comte, et le peu de relative de la direction de la prévision questions. Dans ce cas, vous devez profil, en tant que règles de base ne seront pas fiables.

En plus de cela, la vectorisation et de nombreuses autres optimisations s'appliquer à de petites boucles serrées.

Donc, en général, de code, de mettre le plus de chances de code au sein de l' if bloc, et qui va entraîner le moins de non mise en cache de la branche de prédiction de la rate. En boucles serrées, suivez la règle générale pour commencer, et si vous avez besoin d'en savoir plus vous avez peu de choix mais de profil.

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

Answer 2

J'ai fait le test suivant pour moment de l'exécution de deux if...else if blocs, l'un triées par ordre de probabilité, l'autre triés 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;
}

À l'aide de MSVC2017 avec /O2, les résultats montrent que la version triée est de façon constante d'environ 28% plus rapide que la version non triés. Par luk32 commentaire, j'ai aussi 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 processeur Intel Xeon E5-2697 v2. C'est, bien sûr, très spécifique, et ne doit pas être interprété comme une réponse concluante.

Answer 3

Non, vous ne devrait pas, sauf si vous êtes vraiment sûr que le système cible est touchée. Par défaut, passez par la lisibilité.

Je doute fortement de vos résultats. J'ai modifié votre exemple un peu, donc l'inversion de l'exécution est plus facile. Ideone plutôt montrent que les inversions d'ordre est plus rapide, mais pas beaucoup. Sur certaines pistes, même cela peut parfois inversés. Je dirais que les résultats ne sont pas concluants. coliru n'y a pas de réelle différence en tant que bien. Je peux vérifier Exynos5422 CPU sur mon odroid xu4 plus tard.

Le truc, c'est que les Processeurs modernes ont succursale de prédicteurs. Il y a beaucoup-beaucoup de logique dédiée à la pré-extraction à la fois des données et des instructions, et le moderne, les Processeurs x86 sont plutôt intelligent, quand il s'agit de cela. Certains plus mince architectures comme les Bras ou les Gpu peuvent être vulnérables à ce. Mais il est vraiment fortement dépendant à la fois du compilateur et du système cible.

Je dirais que la direction de la commande d'optimisation est assez fragile et éphémère. Faire cela seulement dans certains vraiment réglage fin de l'étape.

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;
    }
}

Answer 4

Juste mon 5 cents. Il semble que l'effet de la commande si les états devraient dépendre de:

1. La probabilité de chaque instruction if.

2. Nombre d'itérations, de sorte que la direction de la prédicteur pourrait survenir.

3. Probable/peu probable compilateur conseils, c'est à dire la disposition du code.

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

ordered_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;
}

reversed_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;
}

ordered_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;
}

reversed_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;
}

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 Résultats

Les résultats suivants sont pour Intel i5@3,2 GHz et G++ 6.3.0. Le premier argument est le check_point (c'est à dire la probabilité en %% pour les hautement probable si l'énoncé), le deuxième argument est data_sz (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

L'analyse

1. La Commande De N'Importe

Pour la 4K itérations et (presque) 100% de probabilité très aimé déclaration de la différence est énorme 223%:

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

Pour la 4K itérations et 50% de probabilité très aimé déclaration de 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. Nombre d'Itérations N'Importe

La différence entre 4K et 8K itérations pour (presque) 100% de probabilité très aimé déclaration 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 4K et 8K itérations pour 50% de probabilité très aimé déclaration est 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 est-il si? En raison de la direction de la prédicteur de justesse. Ici est la branche de justesse pour chaque cas mentionnés 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

Donc sur mon i5 la branche facteur prédictif d'échec spectaculaire pour la pas-si-sont susceptibles de branches et de grands ensembles de données.

3. Conseils Aider un Peu

Pour la 4K, les itérations, les résultats sont un peu moins bonne pour une probabilité de 50% et un peu mieux à près de 100% de probabilité:

---------------------------------------------------------------------
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 8K itérations, les résultats sont toujours un peu mieux:

---------------------------------------------------------------------
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

Ainsi, les conseils également de l'aide, mais juste un petit peu.

Conclusion générale est: toujours de référence le code, car les résultats peuvent surprendre.

Espérons que cela aide.

Answer 5

Basé sur certains des autres réponses ici, il semble que la seule vraie réponse est: ça dépend. Il dépend au moins de la suite (mais pas nécessairement dans cet ordre d'importance):

• La probabilité Relative de chaque branche. C'est la question qui a été posée. Sur la base des réponses, il semble y avoir certaines conditions de la commande par la probabilité aide, mais il ne semble pas toujours être le cas. Si les probabilités relatives ne sont pas très différents, il est peu probable de faire une différence ce que l'ordre dans lequel ils sont. Cependant, si la première condition se produit à 99,999% du temps, et la prochaine est une fraction de ce qui est à gauche, alors je suppose que le fait de mettre le plus de chances un premier serait bénéfique en termes de calendrier.
• Le coût de calcul de la vrai/faux de l'état de chaque branche. Si le coût du temps d'essai les conditions est vraiment élevé pour une branche par rapport à une autre, cela est susceptible d'avoir un impact significatif sur la rapidité et l'efficacité. Considérons, par exemple, une condition qui prend 1 unité de temps de calcul (par exemple, la vérification de l'état d'une variable Booléenne) par rapport à une autre condition qui prend des dizaines, des centaines, des milliers, voire des millions d'unités de temps de calcul (par exemple, la vérification du contenu d'un fichier sur le disque ou l'exécution d'un complexe requête SQL sur une grande base de données). En supposant que le code vérifie les conditions dans l'ordre chaque fois, le plus rapide des conditions devrait probablement être le premier (à moins qu'ils dépendent d'autres conditions à défaut de la première).
• Compilateur/Interpréteur de Certains compilateurs (ou interprètes) peuvent inclure des optimisations d'un autre qui peut affecter les performances (et certains de ces ne sont présents que si certaines options sont sélectionnées lors de la compilation et/ou de l'exécution). Donc, sauf si vous êtes l'analyse comparative de deux compilations et des exécutions de code identique sur le même système en utilisant exactement le même compilateur où la seule différence est de l'ordre de branches en question, vous allez avoir à donner une certaine marge de manœuvre pour le compilateur variations.
• Système d'exploitation/Matériel tel Que mentionné par luk32 et Yakk, différents Processeurs ont leurs propres optimisations (comme le font les systèmes d'exploitation). Si les repères sont encore sensibles à la variation de la ici.
• La fréquence de bloc de code d'exécution Si le bloc qui comprend les branches est rarement accessible (par exemple, une seule fois pendant le démarrage), puis il a probablement des questions très peu de quel ordre que vous mettez les branches. D'autre part, si votre code est à marteler ce bloc de code au cours d'une partie critique de votre code, puis la commande peut avoir son importance (selon les points de référence).

La seule façon de savoir est de tester votre cas spécifique, de préférence sur un système identique (ou très similaire à) le système sur lequel le code sera finalement exécuté. S'il est destiné à s'exécuter sur un ensemble de systèmes divers avec différents matériel, système d'exploitation, etc., alors c'est une bonne idée pour indice de référence à travers de multiples variations pour voir qui est le meilleur. Il peut même être une bonne idée d'avoir le code soit compilé avec une commande sur un seul type de système et une autre commande sur un autre type de système.

Ma règle personnelle de pouce (pour la plupart des cas, en l'absence d'un indice de référence) est de l'ordre basé sur:

1. Les Conditions qui s'appuient sur le résultat de conditions préalables,
2. Le coût de calcul de la condition, puis
3. La probabilité Relative de chaque branche.