c++ aléatoire - Quel est l'effet de la commande si ... sinon si les déclarations par probabilité?




5 Answers

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

Après cela, la branche passe dans un cache de prédiction de branchement, 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 va être relativement faible. Le prédicteur de branche va apprendre quel est l'ensemble de branches le plus probable, et si vous avez une quantité de travail non triviale dans la boucle, les petites différences ne seront pas très importantes.

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

Vous devriez donc ordonner vos branches dans l'ordre décroissant de probabilité d'obtenir la meilleure prédiction de branche à partir d'une «première rencontre».

Un microbalignement qui boucle de nombreuses fois sur un ensemble de conditions et fait un travail trivial va être dominé par de minuscules effets du nombre d'instructions et similaires, 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 à de minuscules boucles serrées.

Donc, dans le code général, placez le code le plus probable dans le bloc if , et cela se traduira par le plus petit manque de prédiction de branchement 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 sort par la fenêtre si certains tests sont beaucoup moins chers que d'autres.

répartition densité

Plus précisément, si j'ai une série de if ... else if déclarations, et je sais d'une manière ou d'une autre la probabilité relative que chaque déclaration va évaluer à true , combien de temps d'exécution 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 ordonner de façon non optimale. Il est également difficile de dire à quel point le CPU va faire avec la prédiction de branche jusqu'à ce que vous exécutiez le code.

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

Important: cette question suppose que les instructions if peuvent être arbitrairement réorganisées 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 atteindre un comportement souhaité, alors la question de l'efficacité est discutable.




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

Je doute fortement de vos résultats. J'ai modifié un peu votre exemple, donc l'exécution inverse est plus facile. Ideone montre plutôt que l'ordre inverse est plus rapide, mais pas beaucoup. Sur certaines pistes, même parfois retourné. 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 xu4 odroid 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 des données et des instructions, et les processeurs x86 modernes sont plutôt intelligents, quand il s'agit de cela. Certaines architectures plus minces comme les ARM ou les GPU peuvent être vulnérables à cela. Mais il est vraiment très dépendant à la fois du compilateur et du système cible.

Je dirais que l'optimisation des commandes de branches est plutôt fragile et éphémère. Faites-le seulement comme une étape très précise.

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



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

  • Probabilité relative de chaque branche. C'est la question originale 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, il est peu probable qu'il y ait une différence dans l'ordre dans lequel elles se trouvent. Cependant, si la première condition arrive 99,999% du temps et la suivante est une fraction de ce qui reste, alors je Supposons que le plus probable en premier sera 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 de tester les conditions est vraiment élevé pour une branche par rapport à une autre, alors cela aura probablement un impact significatif sur le calendrier et l'efficacité. Par exemple, considérons une condition qui nécessite 1 unité de temps pour calculer (par exemple, vérifier l'état d'une variable booléenne) par rapport à une autre condition qui nécessite des dizaines, des centaines, des milliers ou même des millions d'unités de temps (p. un fichier sur disque ou exécuter 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 échouant en premier).
  • Compilateur / Interprète Certains compilateurs (ou interprètes) peuvent inclure des optimisations d'un type de l'autre qui peuvent affecter les performances (et certaines d'entre elles ne sont présentes que si certaines options sont sélectionnées lors de la compilation et / ou de l'exécution). Donc, sauf si vous comparez 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 l'ordre des branches en question, vous devrez donner une certaine marge pour les variations du compilateur.
  • Système d'exploitation / matériel Comme mentionné par luk32 et Yakk, diverses CPU ont leurs propres optimisations (tout comme les systèmes d'exploitation). Les benchmarks sont donc encore sensibles à la variation ici.
  • Fréquence de l'exécution du bloc de code Si le bloc qui inclut les branches est rarement accédé (par exemple, une seule fois au démarrage), il est probable que l'ordre dans lequel vous placez les branches importe peu. D'un autre côté, si votre code tape sur ce bloc de code pendant une partie critique de votre code, alors la commande peut être très importante (en fonction des benchmarks).

La seule façon 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 sur lequel le code sera finalement exécuté. S'il est destiné à fonctionner sur un ensemble de systèmes différents avec un matériel, un système d'exploitation, etc. différent, alors il est judicieux de comparer plusieurs variations pour voir lequel est le meilleur. Il peut même être une bonne idée 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 personnelle (pour la plupart des cas, en l'absence d'un benchmark) est de commander en fonction de:

  1. Conditions qui s'appuient sur le résultat de conditions préalables,
  2. Coût de calcul de la condition, puis
  3. Probabilité relative de chaque branche.



Dépend aussi de votre compilateur et de la plate-forme que vous compilez.

En théorie, la condition la plus probable devrait faire sauter le contrôle le moins possible.

Généralement, 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 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 CPU annule le pipeline d'exécution et stalle parce que le compteur du programme a changé (pour les architectures qui supportent les pipelines qui sont vraiment communs). 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.




Put them in whatever logical order you like. Sure, the branch may be slower, but branching should not be the majority of work your computer is doing.

If you are working on a performance critical portion of code, then certainly use logical order, profile guided optimization and other techniques, but for general code, I think its really more of a stylistic choice.




Related

c++ performance if-statement optimization branch-prediction