Was bewirkt die Bestellung, wenn… sonst Aussagen nach Wahrscheinlichkeit?

187

Insbesondere, wenn ich eine Reihe von if... else ifAnweisungen habe und die relative Wahrscheinlichkeit, mit der jede Anweisung bewertet wird, im Voraus irgendwie weiß true, wie groß ist der Unterschied in der Ausführungszeit, wenn sie nach Wahrscheinlichkeit sortiert werden? Soll ich das zum Beispiel bevorzugen:

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

dazu?:

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

Es scheint offensichtlich, dass die sortierte Version schneller wäre, aber aus Gründen der Lesbarkeit oder des Vorhandenseins von Nebenwirkungen möchten wir sie möglicherweise nicht optimal bestellen. Es ist auch schwer zu sagen, wie gut die CPU mit der Verzweigungsvorhersage umgehen kann, bis Sie den Code tatsächlich ausführen.

Während ich damit experimentierte, beantwortete ich meine eigene Frage für einen bestimmten Fall, aber ich würde auch gerne andere Meinungen / Erkenntnisse hören.

Wichtig: Bei dieser Frage wird davon ausgegangen, dass die ifAnweisungen beliebig neu angeordnet werden können, ohne dass sich dies auf das Verhalten des Programms auswirkt. In meiner Antwort schließen sich die drei bedingten Tests gegenseitig aus und verursachen keine Nebenwirkungen. Wenn die Aussagen in einer bestimmten Reihenfolge ausgewertet werden müssen, um ein gewünschtes Verhalten zu erzielen, ist das Thema Effizienz sicherlich umstritten.

Carlton
quelle
35
Vielleicht möchten Sie einen Hinweis hinzufügen, dass sich die Bedingungen gegenseitig ausschließen, andernfalls sind die beiden Versionen nicht gleichwertig
idclev 463035818
28
Es ist ziemlich interessant, wie eine selbst beantwortete Frage in einer Stunde mehr als 20 positive Stimmen mit einer eher schlechten Antwort erhielt. Nicht auf OP anrufen, aber Aufsteiger sollten sich davor hüten, auf einen Bandwagen zu springen. Die Frage mag interessant sein, aber die Ergebnisse sind zweifelhaft.
luk32
3
Ich glaube, dies kann als eine Form der Kurzschlussbewertung beschrieben werden, da das Schlagen eines Vergleichs das Schlagen eines anderen Vergleichs verweigert. Ich persönlich bevorzuge eine Implementierung wie diese, wenn ein schneller Vergleich, sagen wir boolesch, mich daran hindern kann, einen anderen Vergleich durchzuführen, der eine ressourcenintensive Manipulation von Zeichenfolgen, Regex oder Datenbankinteraktion beinhalten könnte.
MonkeyZeus
11
Einige Compiler bieten die Möglichkeit, Statistiken über genommene Zweige zu sammeln und diese an den Compiler zurückzusenden, damit dieser bessere Optimierungen vornehmen kann.
11
Wenn Ihnen eine solche Leistung wichtig ist, sollten Sie wahrscheinlich Profile Guided Optimization ausprobieren und Ihr manuelles Ergebnis mit dem Ergebnis des Compilers vergleichen
Justin

Antworten:

96

In der Regel gehen die meisten, wenn nicht alle Intel-CPUs davon aus, dass Vorwärtszweige nicht beim ersten Mal verwendet werden. Siehe Godbolts Arbeit .

Danach wird die Verzweigung in einen Verzweigungsvorhersage-Cache verschoben, und das vergangene Verhalten wird verwendet, um die zukünftige Verzweigungsvorhersage zu informieren.

In einer engen Schleife wird der Effekt einer Fehlordnung also relativ gering sein. Der Zweigprädiktor wird lernen, welche Gruppe von Zweigen am wahrscheinlichsten ist, und wenn Sie nicht triviale Menge an Arbeit in der Schleife haben, summieren sich die kleinen Unterschiede nicht viel.

Im Allgemeinen bestellen die meisten Compiler standardmäßig (ohne einen anderen Grund) den erzeugten Maschinencode ungefähr so, wie Sie ihn in Ihrem Code bestellt haben. Wenn also Anweisungen Forward-Zweige sind, wenn sie fehlschlagen.

Sie sollten Ihre Zweige daher in der Reihenfolge abnehmender Wahrscheinlichkeit ordnen, um die beste Verzweigungsvorhersage aus einer "ersten Begegnung" zu erhalten.

Ein Mikrobenchmark, das viele Male eine enge Schleife über eine Reihe von Bedingungen durchläuft und triviale Arbeit leistet, wird von winzigen Effekten der Befehlsanzahl und dergleichen dominiert und wenig von relativen Verzweigungsvorhersageproblemen. In diesem Fall müssen Sie also ein Profil erstellen , da Faustregeln nicht zuverlässig sind.

Darüber hinaus gelten die Vektorisierung und viele andere Optimierungen für winzige enge Schleifen.

Fügen Sie also im Allgemeinen Code den wahrscheinlichsten Code in den ifBlock ein, und dies führt zu den wenigsten nicht zwischengespeicherten Verzweigungsvorhersagefehlern. Befolgen Sie in engen Schleifen die allgemeine Regel, um zu beginnen, und wenn Sie mehr wissen müssen, haben Sie keine andere Wahl, als ein Profil zu erstellen.

Natürlich geht das alles aus dem Fenster, wenn einige Tests weitaus billiger sind als andere.

Yakk - Adam Nevraumont
quelle
19
Es lohnt sich auch zu überlegen, wie teuer die Tests selbst sind: Wenn ein Test nur geringfügig wahrscheinlicher, aber viel teurer ist, kann es sich lohnen, den anderen Test an die erste Stelle zu setzen, da die Einsparungen durch die Nichtdurchführung des teuren Tests wahrscheinlich den überwiegen Einsparungen durch Verzweigungsvorhersage usw.
psmears
Der von Ihnen angegebene Link unterstützt Ihre Schlussfolgerung nicht. In der Regel gehen die meisten, wenn nicht alle Intel-CPUs davon aus, dass Vorwärtszweige nicht beim ersten Mal verwendet werden, wenn sie sie sehen . Tatsächlich gilt dies nur für die relativ dunkle Arrendale-CPU, deren Ergebnisse zuerst angezeigt werden. Die Mainstream-Ergebnisse von Ivy Bridge und Haswell unterstützen dies überhaupt nicht. Haswell sieht sehr nahe daran, für unsichtbare Zweige immer einen Durchfall vorherzusagen, und Ivy Bridge ist überhaupt nicht klar.
BeeOnRope
Es ist allgemein bekannt, dass CPUs nicht wie in der Vergangenheit statische Vorhersagen verwenden. In der Tat verwendet der moderne Intel wahrscheinlich so etwas wie einen probabilistischen TAGE-Prädiktor. Sie hashen nur den Verlauf der Verzweigung in verschiedene Verlaufstabellen und nehmen eine, die mit der längsten Geschichte übereinstimmt. Es wird ein "Tag" verwendet, um Aliasing zu vermeiden, aber das Tag enthält nur wenige Bits. Wenn Sie bei allen Verlaufslängen fehlen, wird wahrscheinlich eine Standardvorhersage gemacht, die nicht unbedingt von der Verzweigungsrichtung abhängt (bei Haswell können wir sagen, dass dies eindeutig nicht der Fall ist).
BeeOnRope
44

Ich habe den folgenden Test durchgeführt, um die Ausführung von zwei verschiedenen if... else ifBlöcken zu planen, von denen einer nach Wahrscheinlichkeit sortiert und der andere in umgekehrter Reihenfolge sortiert ist:

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

Bei Verwendung von MSVC2017 mit / O2 zeigen die Ergebnisse, dass die sortierte Version durchweg etwa 28% schneller ist als die unsortierte Version. Gemäß dem Kommentar von luk32 habe ich auch die Reihenfolge der beiden Tests geändert, was einen spürbaren Unterschied macht (22% gegenüber 28%). Der Code wurde unter Windows 7 auf einem Intel Xeon E5-2697 v2 ausgeführt. Dies ist natürlich sehr problemspezifisch und sollte nicht als schlüssige Antwort interpretiert werden.

Carlton
quelle
9
OP sollte jedoch vorsichtig sein, da das Ändern einer if... else ifAnweisung einen erheblichen Einfluss darauf haben kann, wie Logik durch den Code fließt. Die unlikelyÜberprüfung wird möglicherweise nicht häufig durchgeführt, es kann jedoch erforderlich sein, dass das Unternehmen unlikelyzuerst den Zustand überprüft, bevor es nach anderen überprüft.
Luke T Brooks
21
30% schneller? Sie meinen, es war schneller um ungefähr den Prozentsatz der zusätzlichen Anweisungen, die nicht ausgeführt werden mussten? Scheint ein ziemlich vernünftiges Ergebnis zu sein.
UKMonkey
5
Wie haben Sie es bewertet? Welcher Compiler, welche CPU usw.? Ich bin mir ziemlich sicher, dass dieses Ergebnis nicht portabel ist.
luk32
12
Ein Problem mit diesem Mikrobenchmark besteht darin, dass die CPU herausfindet, welcher der Zweige am wahrscheinlichsten ist, und ihn zwischenspeichert, wenn Sie ihn wiederholt durchlaufen. Wenn die Zweige nicht in einer kleinen engen Schleife untersucht wurden, enthält der Zweigvorhersage-Cache sie möglicherweise nicht, und die Kosten könnten viel höher sein, wenn die CPU mit der Führung des Null-Zweigvorhersage-Cache falsch vermutet.
Yakk - Adam Nevraumont
6
Dieser Benchmark ist nicht zu zuverlässig. Kompilieren mit gcc 6.3.0 : g++ -O2 -march=native -std=c++14gibt den sortierten bedingten Anweisungen eine leichte Kante, aber die meiste Zeit betrug der prozentuale Unterschied zwischen den beiden Läufen ~ 5%. Mehrmals war es tatsächlich langsamer (aufgrund von Abweichungen). Ich bin mir ziemlich sicher, dass ifes sich nicht lohnt, sich darüber Sorgen zu machen. PGO wird wahrscheinlich solche Fälle vollständig behandeln
Justin
30

Nein, sollten Sie nicht, es sei denn, Sie sind wirklich sicher, dass das Zielsystem betroffen ist. Standardmäßig ist die Lesbarkeit aktiviert.

Ich bezweifle Ihre Ergebnisse sehr. Ich habe Ihr Beispiel ein wenig geändert, damit das Umkehren der Ausführung einfacher ist. Ideone zeigt ziemlich konsequent, dass die umgekehrte Reihenfolge schneller ist, wenn auch nicht viel. Bei bestimmten Läufen drehte sich sogar dies gelegentlich um. Ich würde sagen, die Ergebnisse sind nicht schlüssig. coliru meldet auch keinen wirklichen Unterschied. Ich kann später die Exynos5422-CPU auf meinem Odroid xu4 überprüfen.

Die Sache ist, dass moderne CPUs Verzweigungsprädiktoren haben. Es gibt viel Logik, die sowohl dem Vorabrufen von Daten als auch von Anweisungen gewidmet ist, und moderne x86-CPUs sind in dieser Hinsicht ziemlich intelligent. Einige schlankere Architekturen wie ARMs oder GPUs sind möglicherweise dafür anfällig. Aber es hängt sehr stark vom Compiler und vom Zielsystem ab.

Ich würde sagen, dass die Optimierung der Filialreihenfolge ziemlich fragil und kurzlebig ist. Tun Sie dies nur als einen wirklich feinen Abstimmungsschritt.

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
quelle
Ich erhalte den gleichen Leistungsunterschied von ~ 30%, wenn ich die Reihenfolge der sortierten und umgekehrt sortierten if-Blöcke ändere, wie dies in Ihrem Code geschehen ist. Ich bin mir nicht sicher, warum Ideone und Coliru keinen Unterschied zeigen.
Carlton
Sicher interessant. Ich werde versuchen, einige Daten für andere Systeme zu erhalten, aber es kann bis zu einem Tag dauern, bis ich damit herumspielen muss. Die Frage ist interessant, insbesondere angesichts Ihrer Ergebnisse, aber sie sind so spektakulär, dass ich sie überprüfen musste.
luk32
Wenn die Frage ist, was ist der Effekt? Die Antwort kann nicht Nein sein !
PJTraill
Jep. Ich erhalte jedoch keine Benachrichtigungen für Aktualisierungen der ursprünglichen Frage. Sie machten die Antwortformulierung überflüssig. Es tut uns leid. Ich werde den Inhalt später bearbeiten, um darauf hinzuweisen, dass die ursprüngliche Frage beantwortet und einige Ergebnisse gezeigt wurden, die den ursprünglichen Punkt bewiesen haben.
luk32
Dies sollte wiederholt werden: "Standardmäßig wird die Lesbarkeit überprüft." Wenn Sie lesbaren Code schreiben, erzielen Sie häufig bessere Ergebnisse als wenn Sie versuchen, einen winzigen Leistungsschub (in absoluten Zahlen) zu erzielen, indem Sie das Parsen Ihres Codes für Menschen erschweren.
Andrew Brēza
26

Nur meine 5 Cent. Es scheint die Auswirkung der Bestellung zu sein, wenn Aussagen abhängen sollten von:

  1. Wahrscheinlichkeit jeder if-Anweisung.

  2. Anzahl der Iterationen, damit der Verzweigungsprädiktor einschalten kann.

  3. Wahrscheinliche / unwahrscheinliche Compiler-Hinweise, dh Code-Layout.

Um diese Faktoren zu untersuchen, habe ich die folgenden Funktionen verglichen:

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

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

Daten

Das Datenarray enthält Zufallszahlen zwischen 0 und 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;
}

Die Ergebnisse

Die folgenden Ergebnisse gelten für Intel i5 bei 3,2 GHz und G ++ 6.3.0. Das erste Argument ist der Prüfpunkt (dh die Wahrscheinlichkeit in %% für die höchstwahrscheinliche if-Anweisung), das zweite Argument ist data_sz (dh die Anzahl der Iterationen).

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

Analyse

1. Die Bestellung ist wichtig

Bei 4K-Iterationen und einer (fast) 100% igen Wahrscheinlichkeit einer sehr beliebten Aussage beträgt der Unterschied 223%:

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

Bei 4K-Iterationen und einer Wahrscheinlichkeit von 50% für eine sehr beliebte Aussage beträgt der Unterschied etwa 14%:

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

2. Die Anzahl der Iterationen spielt eine Rolle

Der Unterschied zwischen 4K- und 8K-Iterationen für eine (fast) 100% ige Wahrscheinlichkeit einer sehr beliebten Aussage beträgt ungefähr das Zweifache (wie erwartet):

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

Der Unterschied zwischen 4K- und 8K-Iterationen für eine 50% ige Wahrscheinlichkeit einer sehr beliebten Aussage beträgt jedoch das 5,5-fache:

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

Warum ist das so? Wegen Branch Predictor Misses. Hier sind die Verzweigungsfehler für jeden oben genannten Fall:

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

Auf meinem i5 schlägt der Zweigprädiktor für nicht so wahrscheinliche Zweige und große Datenmengen spektakulär fehl.

3. Hinweise helfen ein bisschen

Bei 4K-Iterationen sind die Ergebnisse bei einer Wahrscheinlichkeit von 50% etwas schlechter und bei einer Wahrscheinlichkeit von nahezu 100% etwas besser:

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

Bei 8K-Iterationen sind die Ergebnisse jedoch immer etwas besser:

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

Die Hinweise helfen also auch, aber nur ein kleines bisschen.

Die allgemeine Schlussfolgerung lautet: Benchmarking des Codes immer, da die Ergebnisse überraschen können.

Hoffentlich hilft das.

Andriy Berestovskyy
quelle
1
i5 Nehalem? i5 Skylake? Nur "i5" zu sagen ist nicht sehr spezifisch. Ich nehme auch an, Sie haben g++ -O2oder verwendet -O3 -fno-tree-vectorize, aber Sie sollten es sagen.
Peter Cordes
Interessant, dass with_hints für geordnete und umgekehrte immer noch unterschiedlich ist. Es wäre gut, wenn Sie irgendwo mit der Quelle verlinken würden. (zB ein Godbolt-Link, vorzugsweise ein Volllink, damit die Linkverkürzung nicht verrotten kann.)
Peter Cordes
1
Die Tatsache, dass der Verzweigungsprädiktor selbst bei einer Größe von 4K-Eingabedaten gut vorhersagen kann, dh den Benchmark "durchbrechen" kann, indem er die Verzweigungsergebnisse über eine Schleife mit einem Zeitraum von Tausenden speichert, ist ein Beweis für die Leistungsfähigkeit der Moderne Zweigprädiktoren. Denken Sie daran, dass Prädiktoren in einigen Fällen sehr empfindlich auf Dinge wie Ausrichtung reagieren, sodass es schwierig ist, eindeutige Schlussfolgerungen über einige Änderungen zu ziehen. Sie haben beispielsweise in verschiedenen Fällen ein entgegengesetztes Verhalten für den Hinweis festgestellt, dies könnte jedoch durch den Hinweis erklärt werden, der das Codelayout zufällig ändert und den Prädiktor beeinflusst.
BeeOnRope
1
@PeterCordes Mein Hauptpunkt ist, dass wir zwar versuchen können, die Ergebnisse einer Änderung vorherzusagen, aber dennoch die Leistung vor und nach der Änderung besser messen können ... Und Sie haben Recht, ich hätte erwähnen sollen, dass sie mit -O3 und dem Prozessor optimiert wurde ist i5-4460 @ 3,20 GHz
Andriy Berestovskyy
19

Basierend auf einigen der anderen Antworten hier sieht es so aus, als ob die einzige wirkliche Antwort lautet: Es kommt darauf an . Es hängt mindestens von Folgendem ab (wenn auch nicht unbedingt in dieser Reihenfolge der Wichtigkeit):

  • Relative Wahrscheinlichkeit jedes Zweigs. Dies ist die ursprüngliche Frage, die gestellt wurde. Basierend auf den vorhandenen Antworten scheint es einige Bedingungen zu geben, unter denen die Reihenfolge nach Wahrscheinlichkeit hilft, aber dies scheint nicht immer der Fall zu sein. Wenn die relativen Wahrscheinlichkeiten nicht sehr unterschiedlich sind, ist es unwahrscheinlich, dass es einen Unterschied macht, in welcher Reihenfolge sie sich befinden. Wenn jedoch die erste Bedingung in 99,999% der Fälle auftritt und die nächste ein Bruchteil dessen ist, was noch übrig ist, würde ich dies tun Nehmen wir an, dass es zeitlich vorteilhaft wäre, die wahrscheinlichste zuerst zu setzen.
  • Kosten für die Berechnung der Richtig / Falsch-Bedingung für jeden Zweig. Wenn die Zeitkosten für das Testen der Bedingungen für einen Zweig im Vergleich zu einem anderen wirklich hoch sind, hat dies wahrscheinlich einen erheblichen Einfluss auf das Timing und die Effizienz. Betrachten Sie beispielsweise eine Bedingung, für deren Berechnung 1 Zeiteinheit erforderlich ist (z. B. Überprüfen des Status einer Booleschen Variablen), gegenüber einer anderen Bedingung, für deren Berechnung Zehn-, Hundert-, Tausend- oder sogar Millionen von Zeiteinheiten erforderlich sind (z. B. Überprüfen des Inhalts von eine Datei auf der Festplatte oder eine komplexe SQL-Abfrage für eine große Datenbank durchführen). Angenommen, der Code überprüft die Bedingungen jedes Mal in der richtigen Reihenfolge, sollten die schnelleren Bedingungen wahrscheinlich an erster Stelle stehen (es sei denn, sie hängen davon ab, dass andere Bedingungen zuerst fehlschlagen).
  • Compiler / Interpreter Einige Compiler (oder Interpreter) enthalten möglicherweise Optimierungen einer anderen Art, die die Leistung beeinträchtigen können (und einige davon sind nur vorhanden, wenn bestimmte Optionen während der Kompilierung und / oder Ausführung ausgewählt werden). Wenn Sie also nicht zwei Kompilierungen und Ausführungen von ansonsten identischem Code auf demselben System mit genau demselben Compiler vergleichen, wobei der einzige Unterschied in der Reihenfolge der betreffenden Zweige besteht, müssen Sie Spielraum für Compilervariationen geben.
  • Betriebssystem / Hardware Wie von luk32 und Yakk erwähnt, haben verschiedene CPUs ihre eigenen Optimierungen (wie auch Betriebssysteme). Benchmarks können hier also wieder variieren.
  • Häufigkeit der Ausführung von Codeblöcken Wenn selten auf den Block zugegriffen wird, der die Zweige enthält (z. B. nur einmal während des Startvorgangs), spielt es wahrscheinlich keine Rolle, in welcher Reihenfolge Sie die Zweige platzieren. Wenn Ihr Code jedoch während eines kritischen Teils Ihres Codes auf diesen Codeblock einhämmert, kann die Bestellung von großer Bedeutung sein (abhängig von den Benchmarks).

Die einzige Möglichkeit, dies mit Sicherheit zu wissen, besteht darin, Ihren speziellen Fall zu bewerten, vorzugsweise auf einem System, das mit dem beabsichtigten System identisch (oder diesem sehr ähnlich) ist, auf dem der Code schließlich ausgeführt wird. Wenn es auf einer Reihe unterschiedlicher Systeme mit unterschiedlicher Hardware, unterschiedlichem Betriebssystem usw. ausgeführt werden soll, empfiehlt es sich, mehrere Varianten zu vergleichen, um festzustellen, welche am besten geeignet sind. Es kann sogar eine gute Idee sein, den Code mit einer Bestellung auf einem Systemtyp und einer anderen Bestellung auf einem anderen Systemtyp kompilieren zu lassen.

Meine persönliche Faustregel (in den meisten Fällen ohne Benchmark) lautet: Bestellen auf der Grundlage von:

  1. Bedingungen, die auf dem Ergebnis früherer Bedingungen beruhen,
  2. Kosten für die Berechnung der Bedingung also
  3. Relative Wahrscheinlichkeit jedes Zweigs.
Ampersat
quelle
13

Die Art und Weise, wie ich dies normalerweise für Hochleistungscode gelöst sehe, besteht darin, die Reihenfolge beizubehalten, die am besten lesbar ist, aber dem Compiler Hinweise zu geben. Hier ist ein Beispiel aus dem Linux-Kernel :

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

Hier wird davon ausgegangen, dass die Zugriffsprüfung bestanden wird und kein Fehler zurückgegeben wird res. Der Versuch, eine dieser if-Klauseln neu zu ordnen, würde den Code nur verwirren, aber das likely()undunlikely() Makros verbessern tatsächlich die Lesbarkeit, indem sie darauf hinweisen, was der Normalfall und was die Ausnahme ist.

Die Linux-Implementierung dieser Makros verwendet GCC-spezifische Funktionen . Es scheint, dass Clang und Intel C Compiler dieselbe Syntax unterstützen, aber MSVC verfügt nicht über eine solche Funktion .

jpa
quelle
4
Dies wäre hilfreicher, wenn Sie erklären könnten, wie die Makros likely()und unlikely()definiert sind, und einige Informationen zur entsprechenden Compilerfunktion enthalten könnten .
Nate Eldredge
1
AFAIK, diese Hinweise ändern "nur" das Speicherlayout der Codeblöcke und ob ein Ja oder Nein zu einem Sprung führt. Dies kann Leistungsvorteile haben, z. B. weil Speicherseiten gelesen werden müssen (oder fehlen). Dies ändert jedoch nicht die Reihenfolge, in der die Bedingungen innerhalb einer langen Liste von else-ifs bewertet werden
Hagen von Eitzen,
@HagenvonEitzen Hmm ja, das ist ein guter Punkt, es kann die Reihenfolge nicht beeinflussen, else ifwenn der Compiler nicht klug genug ist, um zu wissen, dass sich die Bedingungen gegenseitig ausschließen.
jpa
7

Hängt auch von Ihrem Compiler und der Plattform ab, für die Sie kompilieren.

Theoretisch sollte die wahrscheinlichste Bedingung dazu führen, dass die Steuerung so wenig wie möglich springt.

Normalerweise sollte die wahrscheinlichste Bedingung die erste sein:

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

Die beliebtesten asm der auf bedingte Verzweigungen basiert , die springen , wenn die Bedingung ist wahr . Dieser C-Code wird wahrscheinlich in einen solchen Pseudoasmus übersetzt:

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

Dies liegt daran, dass die CPU durch Sprünge die Ausführungspipeline abbricht und blockiert, weil sich der Programmzähler geändert hat (für Architekturen, die wirklich häufige Pipelines unterstützen). Dann geht es um den Compiler, der einige ausgefeilte Optimierungen anwenden kann oder nicht, um die statistisch wahrscheinlichste Bedingung zu haben, dass die Steuerung weniger Sprünge macht.

NoImaginationGuy
quelle
2
Sie haben angegeben, dass der bedingte Zweig auftritt, wenn die Bedingung erfüllt ist, aber das Beispiel "Pseudo-Asm" zeigt das Gegenteil. Es kann auch nicht gesagt werden, dass bedingte Sprünge (geschweige denn alle Sprünge) die Pipeline blockieren, da moderne CPUs typischerweise eine Verzweigungsvorhersage haben. In der Tat wird die Pipeline blockiert , wenn vorhergesagt wird, dass der Zweig genommen wird, aber dann nicht genommen wird. Ich würde immer noch versuchen, die Bedingungen in absteigender Reihenfolge der Wahrscheinlichkeit zu sortieren, aber was der Compiler und die CPU daraus machen, hängt stark von der Implementierung ab.
Arne Vogel
1
Ich setze "nicht (höchstwahrscheinlich)". Wenn also "höchstwahrscheinlich" wahr ist, wird die Steuerung ohne Springen fortgesetzt.
NoImaginationGuy
1
"Die beliebtesten Asms basieren auf bedingten Zweigen, die springen, wenn die Bedingung erfüllt ist." .. Welche ISAs wären das? Dies gilt sicherlich weder für x86 noch für ARM. Hölle für grundlegenden ARM - CPUs (und sehr alte x86 diejenigen, auch für komplexe bps sie in der Regel nach wie vor mit dieser Annahme beginnen und dann anpassen) die Verzweigungsprädiktor geht davon aus, dass ein Vorwärtszweig wird nicht genommen und nach hinten Zweigen immer sind, so das Gegenteil von dem Anspruch ist wahr.
Voo
1
Die Compiler, die ich ausprobiert habe, verwendeten meistens alle den oben erwähnten Ansatz für einen einfachen Test. Beachten Sie, dass clangfür test2und test3: aufgrund von Heuristiken, die darauf hinweisen, dass ein < 0oder ein == 0Test wahrscheinlich falsch ist , tatsächlich ein anderer Ansatz gewählt wurde , wurde beschlossen, den Rest der Funktion auf beiden Pfaden zu klonen, damit condition == falseder Fall durch den Pfad erfolgen kann. Dies ist nur möglich, weil der Rest der Funktion kurz ist: test4Ich habe eine weitere Operation hinzugefügt und es geht zurück zu dem oben beschriebenen Ansatz.
BeeOnRope
1
@ArneVogel - korrekt vorhergesagte genommene Verzweigungen blockieren die Pipeline auf modernen CPUs nicht vollständig, aber sie sind oftmals erheblich schlechter als nicht genommen: (1) Sie bedeuten, dass der Kontrollfluss nicht zusammenhängend ist, so dass der Rest der Anweisungen nach dem jmpnicht vorhanden ist Nützlich, damit die Abruf- / Dekodierungsbandbreite verschwendet wird (2), selbst wenn vorausgesagt wird, dass moderne große Kerne nur einen Abruf pro Zyklus ausführen, sodass eine feste Grenze von 1 genommenem Zweig / Zyklus festgelegt ist (OTOH Modern Intel kann 2 nicht genommene / Zyklen ausführen) (3) ) Es ist schwieriger für die
Zweigvorhersage,
6

Ich habe beschlossen, den Test auf meinem eigenen Computer mit Lik32-Code erneut auszuführen. Ich musste es ändern, weil mein Windows- oder Compiler dachte, dass eine hohe Auflösung 1 ms beträgt

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

vector<int> rand_vec(10000000);

GCC hat für beide Originalcodes dieselbe Transformation durchgeführt.

Beachten Sie, dass nur die beiden ersten Bedingungen getestet werden, da die dritte immer wahr sein muss. GCC ist hier eine Art Sherlock.

Umkehren

.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

Das sagt uns also nicht viel, außer dass der letzte Fall keine Verzweigungsvorhersage benötigt.

Jetzt habe ich alle 6 Kombinationen der Ifs ausprobiert, die Top 2 sind die Originalumkehrung und sortiert. hoch ist> = 95, niedrig ist <20, mittel ist 20-94 mit jeweils 10000000 Iterationen.

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.

Warum ist die Reihenfolge hoch, niedrig, med dann schneller (geringfügig)?

Weil das Unvorhersehbarste das Letzte ist und daher niemals durch einen Verzweigungsprädiktor geführt wird.

          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.

So werden die Zweige vorhergesagt genommen, genommen und der Rest mit

6% + (0,94 *) 20% falsche Vorhersagen.

"Sortiert"

          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

Die Zweige werden mit nicht genommen, nicht genommen und Sherlock vorhergesagt.

25% + (0,75 *) 24% falsche Vorhersagen

Geben Sie eine Differenz von 18-23% an (gemessene Differenz von ~ 9%), aber wir müssen Zyklen berechnen, anstatt% falsch vorherzusagen.

Nehmen wir an, dass auf meiner Nehalem-CPU eine Strafe von 17 Zyklen falsch vorhergesagt wird und dass jede Überprüfung 1 Zyklus dauert (4-5 Anweisungen) und die Schleife auch einen Zyklus dauert. Die Datenabhängigkeiten sind die Zähler und die Schleifenvariablen, aber sobald die falschen Vorhersagen aus dem Weg sind, sollte dies das Timing nicht beeinflussen.

Für "Umkehren" erhalten wir also die Timings (dies sollte die in der Computerarchitektur verwendete Formel sein: Ein quantitativer Ansatz 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

und das gleiche für "sortiert"

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% gegenüber ~ 9% gemessen (nahe am gemessenen!?!).

Das Offensichtliche des OP ist also nicht offensichtlich.

Bei diesen Tests sind andere Tests mit komplizierterem Code oder mehr Datenabhängigkeiten sicherlich anders. Messen Sie also Ihren Fall.

Durch Ändern der Testreihenfolge wurden die Ergebnisse geändert. Dies kann jedoch an unterschiedlichen Ausrichtungen des Schleifenstarts liegen, die idealerweise 16 Byte betragen sollten, die auf allen neueren Intel-CPUs ausgerichtet sind, in diesem Fall jedoch nicht.

Surt
quelle
4

Ordnen Sie sie in einer beliebigen logischen Reihenfolge an. Sicher, die Verzweigung ist möglicherweise langsamer, aber die Verzweigung sollte nicht den größten Teil der Arbeit Ihres Computers ausmachen.

Wenn Sie an einem leistungskritischen Teil des Codes arbeiten, verwenden Sie sicherlich logische Reihenfolge, profilgesteuerte Optimierung und andere Techniken, aber für allgemeinen Code denke ich, dass dies eher eine stilistische Wahl ist.

Jack
quelle
6
Fehler bei der Verzweigungsvorhersage sind teuer. In Microbenchmarks, sie sind unter kalkulierten , weil x86s eine große Tabelle von Verzweigungsvorhersager haben. Eine enge Schleife unter denselben Bedingungen führt dazu, dass die CPU besser als Sie weiß, welche am wahrscheinlichsten ist. Wenn Sie jedoch Verzweigungen im gesamten Code haben, können Sie dafür sorgen, dass der Cache für die Verzweigungsvorhersage keine Slots mehr hat und die CPU die Standardeinstellungen übernimmt. Wenn Sie wissen, was diese Standardschätzung ist, können Sie Zyklen in Ihrer gesamten Codebasis speichern.
Yakk - Adam Nevraumont
@ Yakk Jacks Antwort ist die einzig richtige hier. Nehmen Sie keine Optimierungen vor, die die Lesbarkeit beeinträchtigen, wenn Ihr Compiler diese Optimierung durchführen kann. Sie würden nicht ständig falten, toten Code eliminieren, Schleifen abrollen oder andere Optimierungen vornehmen, wenn Ihr Compiler dies für Sie erledigt, oder? Schreiben Sie Ihren Code, verwenden Sie die profilgesteuerte Optimierung (mit der dieses Problem behoben werden soll, weil Codierer nicht raten können) und prüfen Sie dann, ob Ihr Compiler ihn optimiert oder nicht. Am Ende möchten Sie ohnehin keine Verzweigung in leistungskritischem Code haben.
Christoph Diegelmann
@Christoph Ich würde keinen Code einschließen, von dem ich wusste, dass er tot ist. Ich würde nicht verwenden, i++wann ++idies der Fall wäre, da mir bewusst ist, dass es i++für einige Iteratoren schwierig ist, bis zu optimieren, ++iund der Unterschied (für mich) keine Rolle spielt. Hier geht es darum, Pessimisierung zu vermeiden. Wenn Sie den wahrscheinlichsten Block als Standardgewohnheit an die erste Stelle setzen, wird dies nicht zu einer spürbaren Verringerung der Lesbarkeit führen (und möglicherweise sogar helfen!). Dies führt zu Code, der für die Verzweigungsvorhersage geeignet ist (und Ihnen somit einen einheitlichen kleinen Leistungsschub bietet, der nicht wieder erfasst werden kann) durch spätere
Mikrooptimierung
3

Wenn Sie die relative Wahrscheinlichkeit einer if-else-Anweisung bereits kennen, ist es für Leistungszwecke besser, die sortierte Methode zu verwenden, da nur eine Bedingung (die wahre) überprüft wird.

Auf unsortierte Weise überprüft der Compiler alle Bedingungen unnötig und nimmt sich Zeit.

Aditya Rawat
quelle