Ist "wechseln" schneller als "wenn"?

Zu Ihrer Frage:

1.Wie würde eine grundlegende Sprungtabelle in x86 oder x64 aussehen?

Die Sprungtabelle ist eine Speicheradresse, die einen Zeiger auf die Beschriftungen in einer Art Array-Struktur enthält. Das folgende Beispiel hilft Ihnen zu verstehen, wie Sprungtabellen angeordnet sind

00B14538  D8 09 AB 00 D8 09 AB 00 D8 09 AB 00 D8 09 AB 00  Ø.«.Ø.«.Ø.«.Ø.«.
00B14548  D8 09 AB 00 D8 09 AB 00 D8 09 AB 00 00 00 00 00  Ø.«.Ø.«.Ø.«.....
00B14558  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
00B14568  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................

Wobei 00B14538 der Zeiger auf die Sprungtabelle ist und ein Wert wie D8 09 AB 00 den Beschriftungszeiger darstellt.

2.Verwendet dieser Code eine Sprungtabelle? Nein in diesem Fall.

3.Warum gibt es in diesem Beispiel keinen Leistungsunterschied?

Es gibt keinen Leistungsunterschied, da die Anweisung für beide Fälle gleich aussieht, keine Sprungtabelle.

4. Gibt es eine Situation, in der es einen signifikanten Leistungsunterschied gibt?

Wenn Sie eine sehr lange Folge von if Prüfungen haben, verbessert die Verwendung einer Sprungtabelle in diesem Fall die Leistung (Verzweigungs-/JMP-Anweisungen sind teuer, wenn sie nicht vorhersagen fast perfekt), geht aber mit den Speicherkosten einher.

Der Code für alle Vergleichsbefehle hat ebenfalls eine gewisse Größe. Insbesondere bei 32-Bit-Zeigern oder Offsets kostet eine einzelne Sprungtabellensuche möglicherweise nicht viel mehr Größe in einer ausführbaren Datei.

Fazit: Compiler ist schlau genug, solche Fälle zu behandeln und entsprechende Anweisungen zu generieren :)

Dem Compiler steht es frei, die switch-Anweisung als Code zu kompilieren, der der if-Anweisung entspricht, oder eine Sprungtabelle zu erstellen. Es wird sich wahrscheinlich nach dem entscheiden, was am schnellsten ausgeführt wird, oder den kleinsten Code generieren, je nachdem, was Sie in Ihren Compiler-Optionen angegeben haben - im schlimmsten Fall ist es also genauso schnell wie if-Anweisungen

Ich würde darauf vertrauen, dass der Compiler die beste Wahl trifft und sich darauf konzentriert, was den Code am besten lesbar macht.

Wenn die Anzahl der Fälle sehr groß wird, ist eine Sprungtabelle viel schneller als eine Reihe von if. Wenn die Schritte zwischen den Werten jedoch sehr groß sind, kann die Sprungtabelle groß werden, und der Compiler wählt möglicherweise aus, keine zu generieren.

Woher wissen Sie, dass Ihr Computer während der Switch-Testschleife keine mit dem Test unabhängige Aufgabe ausgeführt hat und während der If-Testschleife weniger Aufgaben ausgeführt hat? Ihre Testergebnisse zeigen nichts als:

1. der Unterschied ist sehr gering
2. es gibt nur ein Ergebnis, keine Reihe von Ergebnissen
3. es gibt zu wenige Fälle

Meine Ergebnisse:

Ich fügte hinzu:

printf("counter: %u\n", counter);

bis zum Ende, damit die Schleife nicht wegoptimiert wird, da in Ihrem Beispiel nie ein Zähler verwendet wurde. Warum sollte der Compiler die Schleife ausführen? Sogar mit einem solchen Micro-Benchmark hat der Switch sofort immer gewonnen.

Das andere Problem mit Ihrem Code ist:

switch (counter % 4 + 1)

in Ihrer Switch-Schleife im Vergleich zu

const size_t c = counter % 4 + 1; 

in deiner if-Schleife. Sehr großer Unterschied, wenn Sie das beheben. Ich glaube, dass das Einfügen der Anweisung in die switch-Anweisung den Compiler dazu veranlasst, den Wert direkt in die CPU-Register zu senden, anstatt ihn zuerst auf den Stack zu setzen. Dies spricht daher für die switch-Anweisung und nicht für einen symmetrischen Test.

Oh und ich denke du solltest auch den Zähler zwischen den Tests zurücksetzen. In der Tat sollten Sie wahrscheinlich eine Art Zufallszahl anstelle von +1, +2, +3 usw. verwenden, da dies dort wahrscheinlich etwas optimiert. Mit Zufallszahl meine ich beispielsweise eine auf der aktuellen Zeit basierende Zahl. Andernfalls könnte der Compiler Ihre beiden Funktionen in eine einzige lange Rechenoperation umwandeln und sich nicht einmal um Schleifen kümmern.

Ich habe Ryans Code gerade genug modifiziert, um sicherzustellen, dass der Compiler die Dinge nicht herausfinden konnte, bevor der Code ausgeführt wurde:

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define MAX_COUNT (1 << 26)
size_t counter = 0;

long long testSwitch()
{
    clock_t start = clock();
    size_t i;
    for (i = 0; i < MAX_COUNT; i++)
    {
        const size_t c = Rand() % 20 + 1;

        switch (c)
        {
                case 1: counter += 20; break;
                case 2: counter += 33; break;
                case 3: counter += 62; break;
                case 4: counter += 15; break;
                case 5: counter += 416; break;
                case 6: counter += 3545; break;
                case 7: counter += 23; break;
                case 8: counter += 81; break;
                case 9: counter += 256; break;
                case 10: counter += 15865; break;
                case 11: counter += 3234; break;
                case 12: counter += 22345; break;
                case 13: counter += 1242; break;
                case 14: counter += 12341; break;
                case 15: counter += 41; break;
                case 16: counter += 34321; break;
                case 17: counter += 232; break;
                case 18: counter += 144231; break;
                case 19: counter += 32; break;
                case 20: counter += 1231; break;
        }
    }
    return 1000 * (long long)(clock() - start) / CLOCKS_PER_SEC;
}

long long testIf()
{
    clock_t start = clock();
    size_t i;
    for (i = 0; i < MAX_COUNT; i++)
    {
        const size_t c = Rand() % 20 + 1;
        if (c == 1) { counter += 20; }
        else if (c == 2) { counter += 33; }
        else if (c == 3) { counter += 62; }
        else if (c == 4) { counter += 15; }
        else if (c == 5) { counter += 416; }
        else if (c == 6) { counter += 3545; }
        else if (c == 7) { counter += 23; }
        else if (c == 8) { counter += 81; }
        else if (c == 9) { counter += 256; }
        else if (c == 10) { counter += 15865; }
        else if (c == 11) { counter += 3234; }
        else if (c == 12) { counter += 22345; }
        else if (c == 13) { counter += 1242; }
        else if (c == 14) { counter += 12341; }
        else if (c == 15) { counter += 41; }
        else if (c == 16) { counter += 34321; }
        else if (c == 17) { counter += 232; }
        else if (c == 18) { counter += 144231; }
        else if (c == 19) { counter += 32; }
        else if (c == 20) { counter += 1231; }
    }
    return 1000 * (long long)(clock() - start) / CLOCKS_PER_SEC;
}

int main()
{
    srand(time(NULL));
    printf("Starting...\n");
    printf("Switch statement: %lld ms\n", testSwitch()); fflush(stdout);
    printf("counter: %d\n", counter);
    counter = 0;
    srand(time(NULL));
    printf("If     statement: %lld ms\n", testIf()); fflush(stdout);
    printf("counter: %d\n", counter);
} 

schalter: 3740
wenn: 3980

(ähnliche Ergebnisse bei mehreren Versuchen)

Ich habe auch die Anzahl der Fälle/Ifs auf 5 reduziert und die Switch-Funktion trotzdem gewonnen.

Ein guter optimierender Compiler wie MSVC kann Folgendes generieren:

1. eine einfache Sprungtabelle, wenn die Fälle in einem Nizza langen Bereich geordnet werden
2. eine spärliche (zweistufige) Sprungtabelle, wenn es viele Lücken gibt
3. eine Reihe von ifs, wenn die Anzahl der Fälle gering ist oder die Werte nicht nahe beieinander liegen
4. eine Kombination der oben genannten Fälle, wenn die Fälle mehrere Gruppen eng beieinander liegender Bereiche darstellen.

Kurz gesagt, wenn der Schalter langsamer als eine Reihe von ifs zu sein scheint, konvertiert der Compiler ihn möglicherweise einfach in eins. Und es ist wahrscheinlich nicht nur eine Folge von Vergleichen für jeden Fall, sondern ein binärer Suchbaum. Siehe hier für ein Beispiel.

Ich werde 2) beantworten und einige allgemeine Kommentare abgeben. 2) Nein, der von Ihnen veröffentlichte Assembly-Code enthält keine Sprungtabelle. Eine Sprungtabelle ist eine Tabelle mit Sprungzielen und ein oder zwei Anweisungen, um direkt von der Tabelle zu einer indizierten Position zu springen. Eine Sprungtabelle wäre sinnvoller, wenn es viele mögliche Vermittlungsziele gibt. Vielleicht weiß der Optimierer, dass einfache, wenn sonst die Logik schneller ist, es sei denn, die Anzahl der Ziele überschreitet einen bestimmten Schwellenwert. Versuchen Sie Ihr Beispiel noch einmal mit sagen wir 20 Möglichkeiten anstelle von 4.

Ich war fasziniert und habe mir angesehen, was ich an Ihrem Beispiel ändern könnte, damit die switch-Anweisung schneller ausgeführt wird.

Wenn Sie zu 40 if-Anweisungen gelangen und einen 0-Fall hinzufügen, wird der if-Block langsamer ausgeführt als die entsprechende switch-Anweisung. Ich habe die Ergebnisse hier: https://www.ideone.com/KZeCz .

Der Effekt des Entfernens des 0-Falls ist hier zu sehen: https://www.ideone.com/LFnrX .

Hier sind einige Ergebnisse aus dem alten (jetzt schwer zu findenden) Bench ++ Benchmark:

Test Name:   F000003                         Class Name:  Style
CPU Time:       0.781  nanoseconds           plus or minus     0.0715
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 2-way if/else if statement
 compare this test with F000004

Test Name:   F000004                         Class Name:  Style
CPU Time:        1.53  nanoseconds           plus or minus     0.0767
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 2-way switch statement
 compare this test with F000003

Test Name:   F000005                         Class Name:  Style
CPU Time:        7.70  nanoseconds           plus or minus      0.385
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 10-way if/else if statement
 compare this test with F000006

Test Name:   F000006                         Class Name:  Style
CPU Time:        2.00  nanoseconds           plus or minus     0.0999
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 10-way switch statement
 compare this test with F000005

Test Name:   F000007                         Class Name:  Style
CPU Time:        3.41  nanoseconds           plus or minus      0.171
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 10-way sparse switch statement
 compare this test with F000005 and F000006

Daraus können wir ersehen, dass (auf diesem Computer mit diesem Compiler - VC++ 9.0 x64) jeder if -Test etwa 0,7 Nanosekunden dauert. Mit steigender Anzahl von Tests skaliert die Zeit nahezu perfekt linear.

Mit der switch-Anweisung gibt es fast keinen Geschwindigkeitsunterschied zwischen einem 2-Wege-Test und einem 10-Wege-Test, solange die Werte dicht sind. Der 10-Wege-Test mit Sparse-Werten dauert ungefähr 1,6-mal so lange wie der 10-Wege-Test mit Density-Werten - aber selbst mit Sparse-Werten ist er immer noch besser als die doppelte Geschwindigkeit eines 10-Wege-Tests if/else if.

Fazit: Nur ein 4-Wege-Test zeigt Ihnen nicht wirklich viel über die Leistung von switch vs if/else. Wenn Sie sich die Zahlen aus diesem Code ansehen, ist es ziemlich einfach, die Tatsache zu interpolieren, dass für einen 4-Wege-Test erwartet wird, dass die beiden hübsch ähnliche Ergebnisse liefern (~ 2,8 Nanosekunden für eine if/else, ~ 2.0 für switch).

Beachten Sie, dass Sie sehr oft schreiben können, wenn ein Switch NICHT zu einer Sprungtabelle kompiliert wird, wenn er effizienter ist als der Switch ...

(1) Wenn die Fälle eine Reihenfolge haben und nicht der schlechteste Test für alle N, können Sie Ihre Ifs aufschreiben, um zu testen, ob in der oberen oder unteren Hälfte, dann in jeder Hälfte dieses binären Suchstils ... resultiert der schlimmste Fall ist logN anstatt N(2) Wenn bestimmte Fälle/Gruppen weitaus häufiger auftreten als andere, können Sie die durchschnittliche Durchlaufzeit beschleunigen, indem Sie festlegen, ob diese Fälle zuerst isoliert werden sollen

Ich bin mir nicht sicher, warum einer schneller und einer langsamer ist.

Das ist eigentlich nicht zu schwer zu erklären ... Wenn Sie sich erinnern, dass falsch vorhergesagte Zweige zehn- bis hundertmal teurer sind als richtig vorhergesagte Zweige.

In dem % 20 Version, der erste Fall/wenn ist immer derjenige, der trifft. Moderne CPUs "lernen", welche Zweige normalerweise belegt sind und welche nicht, so dass sie leicht vorhersagen können, wie sich dieser Zweig bei fast jeder Iteration der Schleife verhält. Das erklärt, warum die "wenn" -Version fliegt; Es muss niemals etwas nach dem ersten Test ausführen, und es sagt das Ergebnis dieses Tests für die meisten Iterationen (korrekt) voraus. Offensichtlich ist der "Schalter" etwas anders implementiert - vielleicht sogar eine Sprungtabelle, die dank des berechneten Zweigs langsam sein kann.

In dem % 21 Version sind die Zweige im Wesentlichen zufällig. Viele von ihnen führen also nicht nur jede Iteration aus, die CPU kann auch nicht erraten, in welche Richtung sie gehen werden. Dies ist der Fall, wenn eine Sprungtabelle (oder eine andere "Schalter" -Optimierung) wahrscheinlich hilfreich ist.

Es ist sehr schwer vorherzusagen, wie ein Teil des Codes mit einem modernen Compiler und einer modernen CPU abschneiden wird, und es wird mit jeder Generation schwieriger. Der beste Rat ist "nicht einmal die Mühe machen, immer Profil". Dieser Rat wird von Jahr zu Jahr besser - und die Anzahl der Leute, die ihn erfolgreich ignorieren können, wird kleiner.

Alles in allem ist meine obige Erklärung eine Vermutung. :-)

Nein, das sind, wenn dann, springen Sie, wenn dann, springen Sie. Eine Sprungtabelle hätte eine Adresstabelle oder würde einen Hash oder ähnliches verwenden.

Schneller oder langsamer ist subjektiv. Sie könnten zum Beispiel Fall 1 als Letztes anstatt als Erstes verwenden, und wenn Ihr Testprogramm oder Real-World-Programm Fall 1 die meiste Zeit verwendete, wäre der Code bei dieser Implementierung langsamer. Es kann also schon einen großen Unterschied machen, die Fallliste je nach Implementierung neu zu ordnen.

Wenn Sie die Fälle 0-3 anstelle von 1-4 verwendet haben, könnte der Compiler eine Sprungtabelle verwendet haben, der Compiler hätte es trotzdem herausfinden müssen, Ihre +1 zu entfernen. Vielleicht lag es an der geringen Stückzahl. Wenn Sie es auf 0 - 15 oder 0 - 31 gesetzt haben, hat es es möglicherweise mit einer Tabelle implementiert oder eine andere Verknüpfung verwendet. Der Compiler kann frei wählen, wie er die Dinge implementiert, solange es die Funktionalität des Quellcodes erfüllt. Dies führt zu Compilerunterschieden, Versionsunterschieden und Optimierungsunterschieden. Wenn Sie eine Sprungtabelle wollen, machen Sie eine Sprungtabelle, wenn Sie einen Wenn-Dann-Sonst-Baum wollen, machen Sie einen Wenn-Dann-Sonst-Baum. Wenn Sie möchten, dass der Compiler entscheidet, verwenden Sie eine switch/case-Anweisung.

Keiner. In den meisten Fällen, in denen Sie in den Assembler gehen und echte Leistungsmessungen durchführen, ist Ihre Frage einfach falsch. Für das gegebene Beispiel ist Ihr Denken definitiv zu kurz

counter += (4 - counter % 4);

scheint mir der richtige inkrementelle Ausdruck zu sein, den Sie verwenden sollten.