webentwicklung-frage-antwort-db.com.de

Wenn vs. Geschwindigkeit wechseln

Wechselanweisungen sind normalerweise schneller als äquivalente if-else-if-Anweisungen (wie in diesem article beschrieben) aufgrund von Compiler-Optimierungen.

Wie funktioniert diese Optimierung eigentlich? Hat jemand eine gute Erklärung?

106
Dirk Vollmar

Der Compiler kann gegebenenfalls Sprungtabellen erstellen. Wenn Sie zum Beispiel den erzeugten Code mit dem Reflektor betrachten, werden Sie feststellen, dass der Compiler bei großen Zeichenfolgen für Strings tatsächlich Code generiert, der eine Hashtabelle verwendet, um diese zu verteilen. Die Hashtabelle verwendet die Zeichenfolgen als Schlüssel und delegiert die case-Codes als Werte.

Dies hat eine asymptotische bessere Laufzeit als viele verkettete if-Tests und ist sogar für relativ wenige Zeichenfolgen tatsächlich schneller.

174
Konrad Rudolph

Konrad ist richtig. Wenn zusammenhängende Bereiche von Ganzzahlen eingeschaltet werden (z. B. Fall 0, Fall 1, Fall 2 .. Fall n), kann der Compiler noch etwas tun, da er nicht einmal eine Hash-Tabelle erstellen muss. Es speichert einfach ein Array von Funktionszeigern und kann so sein Sprungziel in konstanter Zeit laden.

29
Crashworks

Dies ist eine leichte Vereinfachung, da normalerweise jeder moderne Compiler auf eine if..else if ..-Sequenz stößt, die von einer Person trivial in eine switch-Anweisung umgewandelt werden könnte, auch der Compiler. Um jedoch zusätzlichen Spaß zu haben, ist der Compiler nicht durch die Syntax eingeschränkt. Er kann also interne Anweisungen wie "switch" generieren, die eine Mischung aus Bereichen, einzelnen Zielen usw. haben. .else-Anweisungen.

Wie auch immer, eine Erweiterung der Antwort von Konrad ist, dass der Compiler eine Sprungtabelle generieren kann, aber das ist nicht unbedingt garantiert (oder wünschenswert). Aus verschiedenen Gründen tun Sprungtabellen für die Verzweigungsprädiktoren auf modernen Prozessoren schlechte Dinge, und die Tabellen selbst tun schlechte Dinge, um das Verhalten zwischenzuspeichern, z.

switch(a) { case 0: ...; break; case 1: ...; break; }

Wenn ein Compiler dafür tatsächlich eine Sprungtabelle generiert, wäre es wahrscheinlich langsamer als der alternative if..else if..-Stilcode, da die Sprungtabelle die Verzweigungsvorhersage missachtet.

13
olliej

Switch/Case-Anweisungen sind in der Regel schneller 1-stufig. Wenn Sie jedoch mit 2 oder mehr beginnen, benötigen Switch/Case-Anweisungen 2-3 Mal so lange wie verschachtelte if/else-Anweisungen.

Dieser Artikel enthält einige Geschwindigkeitsvergleiche Hervorhebung der Geschwindigkeitsunterschiede beim Verschachteln solcher Anweisungen.

Beispielcode entsprechend ihrer Tests Beispielcode wie folgt:

if (x % 3 == 0)
            if (y % 3 == 0)
                total += 3;
            else if (y % 3 == 1)
                total += 2;
            else if (y % 3 == 2)
                total += 1;
            else
                total += 0;
        else if (x % 3 == 1)
            if (y % 3 == 0)
                total += 3;
            else if (y % 3 == 1)
                total += 2;
            else if (y % 3 == 2)
                total += 1;
            else
                total += 0;
        else if (x % 3 == 2)
            if (y % 3 == 0)
                total += 3;
            else if (y % 3 == 1)
                total += 2;
            else if (y % 3 == 2)
                total += 1;
            else
                total += 0;
        else
            if (y % 3 == 0)
                total += 3;
            else if (y % 3 == 1)
                total += 2;
            else if (y % 3 == 2)
                total += 1;
            else
                total += 0;

in half die Zeit beendet, die die entsprechende switch/case-Anweisung zur Ausführung benötigte:

switch (x % 3)
    {
        case 0:
            switch (y % 3)
            {
                case 0: total += 3;
                    break;
                case 1: total += 2;
                    break;
                case 2: total += 1;
                    break;
                default: total += 0;
                    break;
            }
            break;
        case 1:
            switch (y % 3)
            {
                case 0: total += 3;
                    break;
                case 1: total += 2;
                    break;
                case 2: total += 1;
                    break;
                default: total += 0;
                    break;
            }
            break;
    case 2:
            switch (y % 3)
            {
                case 0: total += 3;
                    break;
                case 1: total += 2;
                    break;
                case 2: total += 1;
                    break;
                default: total += 0;
                    break;
            }
            break;
    default:
        switch (y % 3)
        {
            case 0: total += 3;
                break;
            case 1: total += 2;
                break;
            case 2: total += 1;
                break;
            default: total += 0;
                break;
        }
        break;
    }

Ja, es ist ein rudimentäres Beispiel, aber es veranschaulicht den Punkt. 

Eine Schlussfolgerung könnte also die Verwendung von switch/case für einfache Typen sein, die nur eine Ebene tief sind. Für komplexere Vergleiche und mehrere verschachtelte Ebenen verwenden Sie jedoch die klassischen if/else-Konstrukte.

5
Thrawn Wannabe

Wie Konrad sagte, kann der Compiler eine Jump-Tabelle erstellen. 

In C++ kann dies auf die Einschränkung von Switches zurückzuführen sein. 

5
J.J.

Die Nicht-Übereinstimmungsstatistiken sind möglicherweise nicht gut.

Wenn Sie tatsächlich die Quelle herunterladen, sind die Werte für die Nichtübereinstimmung im Fall von if und switch mit 21 bekannt. Ein Compiler sollte in der Lage sein zu abstrahieren, wobei er weiß, welche Anweisung zu jeder Zeit ausgeführt werden sollte, und eine CPU sollte in der Lage sein, die Verzweigungsvoraussage richtig auszuführen.

Der interessantere Fall ist, wenn meiner Meinung nach nicht jeder Fall bricht, aber dies war möglicherweise nicht der Umfang des Experiments. 

4
Calyth

Der einzige Vorteil des if-over-Falls besteht darin, dass die Häufigkeit des Auftretens des ersten Falls merklich ansteigt. 

Ich weiß nicht genau, wo sich der Schwellenwert befindet, aber ich verwende die Groß-/Kleinschreibung, es sei denn, der erste Test wird "fast immer" bestanden. 

0
Ralph

Das ist der Code für den PIC18-Mikrocontroller in C-Sprache:

void main() {
int s1='0';
int d0;
int d1;
//if (s1 == '0') {d1 = '0'; d0 = '0';}
//else if (s1 == '1') {d1 = '0';d0 = '1';}
//else if (s1 == '2') {d1 = '1';d0 = '0';}
//else if (s1 == '3') {d1 = '1';d0 = '1';}
switch (s1) {
      case  '0': {d1 = '0';d0 = '0';} break;
      case  '1': {d1 = '0';d0 = '1';} break;
      case  '2': {d1 = '1';d0 = '0';} break;
      case  '3': {d1 = '1';d0 = '1';} break;
    }
}

Mit ifs

s1='0' - 14 cycles
s1='1' - 21 cycles
s1='2' - 28 cycles
s1='3' - 33 cycles
s1='4' - 34 cycles

Mit Fällen

s1='0' - 17 cycles
s2='1' - 23 cycles
s3='2' - 29 cycles
s4='3' - 35 cycles
s5='4' - 32 cycles

Ich kann also davon ausgehen, dass ifs auf sehr niedrigem Niveau schneller ist. Der Code in ROM ist auch kürzer.

0
Denys Titarenko