Welches ist schneller: while(1) oder while(2)?

Question

Dies war eine Interviewfrage eines leitenden Managers.

Was ist schneller?

while(1) {
    // Einige Code
}

oder

while(2) {
    // Einige Code
}

Ich sagte, dass beide die gleiche Ausführungsgeschwindigkeit haben, da der Ausdruck innerhalb des while-Statements schließlich zu true oder false ausgewertet werden sollte. In diesem Fall evaluieren beide zu true und es gibt keine zusätzlichen bedingten Anweisungen innerhalb der while-Bedingung. Daher werden beide mit der gleichen Ausführungsgeschwindigkeit ausgeführt, und ich bevorzuge while (1).

Aber der Interviewer sagte zuversichtlich: "Überprüfe deine Grundlagen. while(1) ist schneller als while(2)." (Er testete nicht meine Zuversicht)

Ist das wahr?

Siehe auch: Ist "for(;;)" schneller als "while (TRUE)"? Wenn nicht, warum verwenden Menschen es?

Answer 1

Beide Schleifen sind unendlich, aber wir können sehen, welche mehr Anweisungen/Ressourcen pro Iteration benötigt.

Unter Verwendung von gcc habe ich die beiden folgenden Programme in Assembly mit unterschiedlichen Optimierungsebenen kompiliert:

int main(void) {
    while(1) {}
    return 0;
}

int main(void) {
    while(2) {}
    return 0;
}

Selbst ohne Optimierungen (-O0) war das generierte Assembly für beide Programme identisch. Daher gibt es keinen Geschwindigkeitsunterschied zwischen den beiden Schleifen.

Zur Referenz, hier ist das generierte Assembly (mit gcc main.c -S -masm=intel mit einer Optimierungsoption):

Mit -O0:

    .file   "main.c"
    .intel_syntax noprefix
    .def    __main; .scl    2;  .type   32; .endef
    .text
    .globl  main
    .def    main;   .scl    2;  .type   32; .endef
    .seh_proc   main
main:
    push    rbp
    .seh_pushreg    rbp
    mov rbp, rsp
    .seh_setframe   rbp, 0
    sub rsp, 32
    .seh_stackalloc 32
    .seh_endprologue
    call    __main
.L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Mit -O1:

    .file   "main.c"
    .intel_syntax noprefix
    .def    __main; .scl    2;  .type   32; .endef
    .text
    .globl  main
    .def    main;   .scl    2;  .type   32; .endef
    .seh_proc   main
main:
    sub rsp, 40
    .seh_stackalloc 40
    .seh_endprologue
    call    __main
.L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Mit -O2 und -O3 (gleiche Ausgabe):

    .file   "main.c"
    .intel_syntax noprefix
    .def    __main; .scl    2;  .type   32; .endef
    .section    .text.startup,"x"
    .p2align 4,,15
    .globl  main
    .def    main;   .scl    2;  .type   32; .endef
    .seh_proc   main
main:
    sub rsp, 40
    .seh_stackalloc 40
    .seh_endprologue
    call    __main
.L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Tatsächlich ist das für die Schleife generierte Assembly für jede Optimierungsebene identisch:

 .L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Die wichtigen Teile sind:

.L2:
    jmp .L2

Ich kann Assembly nicht sehr gut lesen, aber das ist offensichtlich eine bedingungslose Schleife. Die Anweisung jmp setzt das Programm bedingungslos zurück zum Label .L2, ohne einen Wert gegen wahr zu vergleichen, und tut dies sofort wieder, bis das Programm auf irgendeine Weise beendet wird. Das entspricht direkt dem C/C++ Code:

L2:
    goto L2;

Bearbeitet:

Interessanterweise wurde sogar bei keinen Optimierungen die folgenden Schleifen alle als identische Ausgabe (bedingungsloses jmp) im Assembly erzeugt:

while(42) {}

while(1==1) {}

while(2==2) {}

while(4<7) {}

while(3==3 && 4==4) {}

while(8-9 < 0) {}

while(4.3 * 3e4 >= 2 << 6) {}

while(-0.1 + 02) {}

Und sogar zu meiner Verwunderung:

#include

while(sqrt(7)) {}

while(hypot(3,4)) {}

Mit benutzerdefinierten Funktionen wird es etwas interessanter:

int x(void) {
    return 1;
}

while(x()) {}

#include

double x(void) {
    return sqrt(7);
}

while(x()) {}

Bei -O0 rufen diese beiden Beispiele tatsächlich x auf und führen für jede Iteration einen Vergleich durch.

Erstes Beispiel (Rückgabe 1):

.L4:
    call    x
    testl   %eax, %eax
    jne .L4
    movl    $0, %eax
    addq    $32, %rsp
    popq    %rbp
    ret
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Zweites Beispiel (Rückgabe sqrt(7)):

.L4:
    call    x
    xorpd   %xmm1, %xmm1
    ucomisd %xmm1, %xmm0
    jp  .L4
    xorpd   %xmm1, %xmm1
    ucomisd %xmm1, %xmm0
    jne .L4
    movl    $0, %eax
    addq    $32, %rsp
    popq    %rbp
    ret
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Bei -O1 und höher erzeugen sie jedoch beide dasselbe Assembly wie die vorherigen Beispiele (ein bedingungsloses jmp zurück zum vorherigen Label).

Zusammenfassung

Unter GCC werden verschiedene Schleifen in identisches Assembly übersetzt. Der Compiler evaluieret die Konstantenwerte und führt keinen tatsächlichen Vergleich durch.

Die Moral von der Geschichte ist:

• Es gibt eine Übersetzungsebene zwischen dem C-Quellcode und den CPU-Anweisungen, und diese Ebene hat wichtige Auswirkungen auf die Leistung.
• Daher kann die Leistung nicht nur durch Betrachten des Quellcodes bewertet werden.
• Der Compiler sollte schlau genug sein, um solche trivialen Fälle zu optimieren. Programmierer sollten in der überwiegenden Mehrheit der Fälle keine Zeit darauf verschwenden, darüber nachzudenken.

Answer 2

Ja, while(1) ist viel schneller als while(2), für einen Menschen zu lesen! Wenn ich while(1) in einem unbekannten Codebase sehe, weiß ich sofort, was der Autor beabsichtigt hat, und meine Augen können zur nächsten Zeile übergehen.

Wenn ich while(2) sehe, werde ich wahrscheinlich innehalten und versuchen herauszufinden, warum der Autor nicht while(1) geschrieben hat. Ist dem Autor beim Tippen ein Fehler unterlaufen? Verwenden die Maintainer dieses Codebase while(n) als obskuren Kommentierungsmechanismus, um Schleifen anders aussehen zu lassen? Ist es eine grobe Lösung für eine nicht vorhandene Warnung in einem defekten statischen Analysetool? Oder ist es ein Hinweis darauf, dass ich generierten Code lese? Handelt es sich um einen Fehler, der aus einem unüberlegten Find-and-Replace-all oder einem schlechten Merge oder einem kosmischen Strahl resultiert? Vielleicht sollte diese Codezeile etwas dramatisch Anderes tun. Vielleicht sollte es while(w) oder while(x2) heißen. Ich sollte besser den Autor in der Dateihistorie finden und ihnen eine "WTF"-E-Mail schicken... und jetzt habe ich meinen mentalen Kontext verloren. Das while(2) könnte mehrere Minuten meiner Zeit in Anspruch nehmen, während while(1) nur einen Bruchteil einer Sekunde benötigt hätte!

Ich übertreibe nur ein wenig. Die Lesbarkeit des Codes ist wirklich wichtig. Und das ist es wert, in einem Interview erwähnt zu werden!

Answer 3

Die vorhandenen Antworten, die den vom Compiler für ein bestimmtes Ziel, eine bestimmte Liste von Optionen generierten Code zeigen, beantworten die Frage nicht vollständig - es sei denn, die Frage wurde in diesem spezifischen Kontext gestellt ("Welches ist schneller mit gcc 4.7.2 für x86_64 mit Standardoptionen?", zum Beispiel).

Soweit die Sprachdefinition betrifft, bewertet im abstrakten Maschine while (1) die ganzzahlige Konstante 1, und while (2) bewertet die ganzzahlige Konstante 2; in beiden Fällen wird das Ergebnis mit Null verglichen. Der Sprachstandard sagt absolut nichts über die relative Leistung der beiden Konstrukte aus.

Ich kann mir vorstellen, dass ein extrem naiver Compiler möglicherweise unterschiedlichen Maschinencode für die beiden Formen generiert, zumindest wenn er ohne Optimierung kompiliert wird.

Andererseits müssen C-Compiler definitiv einige Konstantenausdrücke zur Kompilierzeit bewerten, wenn sie in Kontexten erscheinen, die einen Konstantenausdruck erfordern. Zum Beispiel, das:

int n = 4;
switch (n) {
    case 2+2: break;
    case 4:   break;
}

erfordert eine Diagnose; ein träger Compiler hat nicht die Möglichkeit, die Auswertung von 2+2 bis zur Ausführungszeit aufzuschieben. Da ein Compiler in der Lage sein muss, Konstantenausdrücke zur Kompilierzeit zu bewerten, gibt es keinen guten Grund, warum er diese Fähigkeit nicht nutzen sollte, selbst wenn es nicht erforderlich ist.

Der C-Standard (N1570 6.8.5p4) besagt, dass

Ein Iterationsausdruck führt ein als Schleifenkörper bezeichnetes Statement so lange wiederholt aus, bis der kontrollierende Ausdruck gleich 0 ist.

Die relevanten Konstantenausdrücke sind also 1 == 0 und 2 == 0, beide werten zur int Wert 0. (Diese Vergleiche sind implizit in der Semantik der while Schleife; sie existieren nicht als tatsächliche C-Ausdrücke.)

Ein pervers naiver Compiler könnte unterschiedlichen Code für die beiden Konstrukte generieren. Zum Beispiel könnte er für den ersten eine bedingungslose Endlosschleife generieren (indem er 1 als Sonderfall behandelt) und für den zweiten könnte er einen expliziten Laufzeitvergleich erzeugen, der äquivalent zu 2 != 0 ist. Aber ich bin noch nie auf einen C-Compiler gestoßen, der sich tatsächlich so verhalten würde, und ich bezweifle ernsthaft, dass ein solcher Compiler existiert.

Die meisten Compiler (ich versuche zu sagen, alle produktionsqualität Compiler) haben Optionen, um zusätzliche Optimierungen anzufordern. Unter einer solchen Option ist es noch unwahrscheinlicher, dass ein Compiler unterschiedlichen Code für die beiden Formen generieren würde.

Wenn Ihr Compiler unterschiedlichen Code für die beiden Konstrukte generiert, überprüfen Sie zunächst, ob die sich unterscheidenden Code-Sequenzen tatsächlich unterschiedliche Leistungen haben. Wenn sie dies tun, versuchen Sie es erneut mit einer Optimierungsoption (falls verfügbar). Wenn sie sich immer noch unterscheiden, reichen Sie einen Fehlerbericht beim Compiler-Hersteller ein. Es ist kein Fehler im Sinne eines Nichterfüllens des C-Standards, aber es ist fast sicher ein Problem, das korrigiert werden sollte.

Letztendlich: while (1) und while(2) haben fast sicher die gleiche Leistung. Sie haben genau die gleiche Semantik, und es gibt keinen guten Grund, warum irgendein Compiler keinen identischen Code generieren sollte.

Und obwohl es rechtens ist, dass ein Compiler für while(1) schnelleren Code generieren, als für while(2), ist es genauso rechtens, dass ein Compiler schnelleren Code für while(1) erstellen kann, als für eine weitere Auftreten von while(1) im selben Programm.

(In Ihrer Frage steckt eine weitere Frage: Wie gehen Sie mit einem Interviewer um, der auf einem inkorrekten technischen Punkt besteht. Das wäre wahrscheinlich eine gute Frage für die Workplace-Website).

Answer 4

Warte mal. Hat der Interviewer so ausgesehen?

Es ist schon schlimm genug, dass der Interviewer selbst dieses Interview nicht bestanden hat, was ist, wenn andere Programmierer bei diesem Unternehmen diesen Test "bestanden" haben?

Nein. Die Auswertung der Aussagen 1 == 0 und 2 == 0 sollte gleichermaßen schnell sein. Man könnte sich vorstellen, dass es schlechte Compilerimplementierungen gibt, bei denen eine schneller sein könnte als die andere. Aber es gibt keinen guten Grund, warum eine schneller sein sollte als die andere.

Auch wenn es irgendwelche obskuren Umstände gibt, unter denen die Behauptung wahr wäre, sollten Programmierer nicht anhand von Wissen über obskure (und in diesem Fall gruselige) Trivia bewertet werden. Mach dir keine Sorgen über dieses Interview, der beste Schritt hier ist, wegzugehen.

Haftungsausschluss: Dies ist KEIN Original-Dilbert-Comic. Dies ist lediglich eine Mashup.

Answer 5

Ihre Erklärung ist korrekt. Dies scheint eine Frage zu sein, die Ihr Selbstvertrauen zusätzlich zu Ihrem Fachwissen testet.

Übrigens, wenn Sie geantwortet hätten

Beide Codeabschnitte sind gleich schnell, weil beide unendlich lange dauern, bis sie fertig sind

würde der Interviewer sagen

Aber while (1) kann mehr Iterationen pro Sekunde durchlaufen; können Sie erklären warum? (das ist Unsinn; er testet wieder Ihr Vertrauen)

Also haben Sie durch Ihre Antwort Zeit gespart, die Sie sonst damit verschwendet hätten, über diese schlechte Frage zu diskutieren.

---

Hier ist ein Codebeispiel, das vom Compiler auf meinem System (MS Visual Studio 2012) generiert wurde, mit deaktivierten Optimierungen:

yyy:
    xor eax, eax
    cmp eax, 1     (oder 2, je nach Ihrem Code)
    je xxx
    jmp yyy
xxx:
    ...

Mit aktivierten Optimierungen:

xxx:
    jmp xxx

Also ist der generierte Code genau gleich, zumindest mit einem optimierenden Compiler.