Produzieren Compiler besseren Code für Do-While-Schleifen als für andere Arten von Schleifen?

In der zlib-Komprimierungsbibliothek (die unter anderem im Chromium-Projekt verwendet wird) gibt es einen Kommentar, der impliziert, dass eine Do-While-Schleife in C auf den meisten Compilern "besseren" Code generiert. Hier ist der Codeausschnitt, in dem er angezeigt wird.

do {
} while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
         *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
         *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
         *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
         scan < strend);
/* The funny "do {}" generates better code on most compilers */

https://code.google.com/p/chromium/codesearch#chromium/src/third_party/zlib/deflate.c&l=1225

Gibt es Hinweise darauf, dass die meisten (oder andere) Compiler besseren (z. B. effizienteren) Code generieren würden?

Update: Mark Adler , einer der ursprünglichen Autoren, gab in den Kommentaren ein wenig Kontext .

Zuerst:

Eine do-whileSchleife ist nicht dasselbe wie eine whileSchleife oder eine forSchleife.

• whileund forSchleifen führen den Schleifenkörper möglicherweise überhaupt nicht aus.
• Eine do-whileSchleife führt den Schleifenkörper immer mindestens einmal aus - sie überspringt die Anfangszustandsprüfung.

Das ist also der logische Unterschied. Das heißt, nicht jeder hält sich strikt daran. Es ist durchaus üblich, dass whileoder forSchleifen verwendet werden, auch wenn garantiert ist, dass sie immer mindestens einmal wiederholt werden. (Besonders in Sprachen mit foreach- Schleifen.)

Um einen Vergleich von Äpfeln und Orangen zu vermeiden, gehe ich davon aus, dass die Schleife immer mindestens einmal ausgeführt wird. Außerdem werde ich forLoops nicht noch einmal erwähnen , da es sich im Wesentlichen um whileLoops mit etwas Syntaxzucker für einen Loop-Zähler handelt.

Also werde ich die Frage beantworten:

Wenn whilegarantiert wird, dass eine Schleife mindestens einmal wiederholt wird, gibt es einen Leistungsgewinn durch die Verwendung einer do-whileSchleife.

A do-whileüberspringt die erste Zustandsprüfung. Es gibt also einen Zweig weniger und eine Bedingung weniger zu bewerten.

Wenn die Überprüfung der Bedingung teuer ist und Sie wissen, dass Sie garantiert mindestens einmal eine do-whileSchleife ausführen, kann eine Schleife schneller sein.

Und obwohl dies bestenfalls als Mikrooptimierung angesehen wird, kann der Compiler dies nicht immer tun: Insbesondere, wenn der Compiler nicht nachweisen kann, dass die Schleife immer mindestens einmal eintritt.

Mit anderen Worten, eine while-Schleife:

while (condition){
    body
}

Ist effektiv das gleiche wie das:

if (condition){
    do{
        body
    }while (condition);
}

Wenn Sie wissen, dass Sie immer mindestens einmal eine Schleife ausführen, ist diese if-Anweisung irrelevant.

Auf Assembly-Ebene werden die verschiedenen Schleifen auf folgende Weise kompiliert:

do-while-Schleife:

start:
    body
    test
    conditional jump to start

while-Schleife:

    test
    conditional jump to end
start:
    body
    test
    conditional jump to start
end:

Beachten Sie, dass die Bedingung dupliziert wurde. Ein alternativer Ansatz ist:

    unconditional jump to end
start:
    body
end:
    test
    conditional jump to start

... der den doppelten Code gegen einen zusätzlichen Sprung eintauscht.

In jedem Fall ist es immer noch schlimmer als eine normale do-whileSchleife.

Compiler können jedoch tun, was sie wollen. Und wenn sie beweisen können, dass die Schleife immer einmal eintritt, hat sie die Arbeit für Sie erledigt.

Aber für das jeweilige Beispiel in der Frage sind die Dinge etwas seltsam, weil es einen leeren Schleifenkörper hat. Da es keinen Körper gibt, gibt es keinen logischen Unterschied zwischen whileund do-while.

FWIW, ich habe dies in Visual Studio 2012 getestet:

• Mit dem leeren Körper wird tatsächlich der gleiche Code für whileund generiert do-while. Dieser Teil ist wahrscheinlich ein Überbleibsel der alten Zeiten, als Compiler nicht so großartig waren.

• Mit einem nicht leeren Körper schafft es VS2012 jedoch, eine Verdoppelung des Bedingungscodes zu vermeiden, erzeugt aber dennoch einen zusätzlichen bedingten Sprung.

Es ist also ironisch, dass das Beispiel in der Frage zwar zeigt, warum eine do-whileSchleife im allgemeinen Fall schneller sein könnte, das Beispiel selbst jedoch für einen modernen Compiler keinen Nutzen zu bringen scheint.

Wenn man bedenkt, wie alt der Kommentar war, können wir nur raten, warum er wichtig ist. Es ist sehr wahrscheinlich, dass die Compiler zu diesem Zeitpunkt nicht erkennen konnten, dass der Körper leer war. (Oder wenn doch, haben sie die Informationen nicht verwendet.)

Gibt es Hinweise darauf, dass die meisten (oder andere) Compiler besseren (z. B. effizienteren) Code generieren würden?

Nicht viel, es sei denn, Sie betrachten die tatsächlich generierte Assembly eines tatsächlichen, bestimmten Compilers auf einer bestimmten Plattform mit bestimmten Optimierungseinstellungen.

Dies war wahrscheinlich vor Jahrzehnten besorgniserregend (als ZLib geschrieben wurde), aber heutzutage sicherlich nicht, es sei denn, Sie haben durch echte Profilerstellung festgestellt , dass dies einen Engpass in Ihrem Code beseitigt.

Kurz gesagt (tl; dr):

Ich interpretiere den Kommentar im Code von OPs etwas anders. Ich denke, der "bessere Code", den sie angeblich beobachtet haben, war darauf zurückzuführen, dass die eigentliche Arbeit in die "Bedingung" der Schleife verschoben wurde. Ich stimme jedoch voll und ganz zu, dass es sehr compilerspezifisch ist und dass der Vergleich, den sie angestellt haben, obwohl sie einen etwas anderen Code erzeugen können, größtenteils sinnlos und wahrscheinlich veraltet ist, wie ich unten zeige.

Einzelheiten:

Es ist schwer zu sagen, was der ursprüngliche Autor mit seinem Kommentar zu diesem do {} whilebesseren Code gemeint hat , aber ich möchte in eine andere Richtung spekulieren als hier - wir glauben, dass der Unterschied zwischen do {} whileund while {}Schleifen ziemlich gering ist (ein Zweig weniger als Mystical sagte), aber es gibt etwas noch "lustigeres" in diesem Code und das bringt die ganze Arbeit in diesen verrückten Zustand und hält den internen Teil leer ( do {}).

Ich habe den folgenden Code auf gcc 4.8.1 (-O3) ausprobiert und es gibt einen interessanten Unterschied -

#include "stdio.h" 
int main (){
    char buf[10];
    char *str = "hello";
    char *src = str, *dst = buf;

    char res;
    do {                            // loop 1
        res = (*dst++ = *src++);
    } while (res);
    printf ("%s\n", buf);

    src = str;
    dst = buf;
    do {                            // loop 2
    } while (*dst++ = *src++);
    printf ("%s\n", buf);

    return 0; 
}

Nach dem Kompilieren -

00000000004003f0 <main>:
  ... 
; loop 1  
  400400:       48 89 ce                mov    %rcx,%rsi
  400403:       48 83 c0 01             add    $0x1,%rax
  400407:       0f b6 50 ff             movzbl 0xffffffffffffffff(%rax),%edx
  40040b:       48 8d 4e 01             lea    0x1(%rsi),%rcx
  40040f:       84 d2                   test   %dl,%dl
  400411:       88 16                   mov    %dl,(%rsi)
  400413:       75 eb                   jne    400400 <main+0x10>
  ...
;loop 2
  400430:       48 83 c0 01             add    $0x1,%rax
  400434:       0f b6 48 ff             movzbl 0xffffffffffffffff(%rax),%ecx
  400438:       48 83 c2 01             add    $0x1,%rdx
  40043c:       84 c9                   test   %cl,%cl
  40043e:       88 4a ff                mov    %cl,0xffffffffffffffff(%rdx)
  400441:       75 ed                   jne    400430 <main+0x40>
  ...

Die erste Schleife führt also 7 Anweisungen aus, während die zweite 6 Anweisungen ausführt, obwohl sie die gleiche Arbeit ausführen sollen. Jetzt kann ich nicht wirklich sagen, ob dahinter eine gewisse Compiler-Intelligenz steckt, wahrscheinlich nicht, und es ist nur ein Zufall, aber ich habe nicht überprüft, wie es mit anderen Compiler-Optionen interagiert, die dieses Projekt möglicherweise verwendet.

Bei Clang 3.3 (-O3) hingegen generieren beide Loops diesen 5-Anweisungscode:

  400520:       8a 88 a0 06 40 00       mov    0x4006a0(%rax),%cl
  400526:       88 4c 04 10             mov    %cl,0x10(%rsp,%rax,1)
  40052a:       48 ff c0                inc    %rax
  40052d:       48 83 f8 05             cmp    $0x5,%rax
  400531:       75 ed                   jne    400520 <main+0x20>

Das zeigt nur, dass Compiler ganz anders sind und viel schneller vorankommen, als manche Programmierer vor einigen Jahren erwartet hatten. Es bedeutet auch, dass dieser Kommentar ziemlich bedeutungslos ist und wahrscheinlich da ist, weil noch nie jemand überprüft hat, ob er noch Sinn macht.

Fazit: Wenn Sie den bestmöglichen Code optimieren möchten (und wissen, wie er aussehen soll), tun Sie dies direkt in der Assembly und schneiden Sie den "Middle-Man" (Compiler) aus der Gleichung aus, berücksichtigen Sie jedoch den neueren Compiler und neuere HW könnten diese Optimierung überflüssig machen. In den meisten Fällen ist es weitaus besser, den Compiler diese Arbeit für Sie erledigen zu lassen und sich auf die Optimierung der großen Dinge zu konzentrieren.

Ein weiterer Punkt, der angesprochen werden sollte - die Anzahl der Anweisungen (vorausgesetzt, dies ist der Code des ursprünglichen OPs), ist keineswegs ein gutes Maß für die Codeeffizienz. Nicht alle Anweisungen wurden gleich erstellt, und einige von ihnen (z. B. einfache Reg-to-Reg-Bewegungen) sind sehr billig, da sie von der CPU optimiert werden. Andere Optimierungen können tatsächlich die internen Optimierungen der CPU beeinträchtigen, sodass letztendlich nur das richtige Benchmarking zählt.

Eine whileSchleife wird häufig als do-whileSchleife mit einer anfänglichen Verzweigung zur Bedingung kompiliert , d. H.

    bra $1    ; unconditional branch to the condition
$2:
    ; loop body
$1:
    tst <condition> ; the condition
    brt $2    ; branch if condition true

wohingegen die Kompilierung einer do-whileSchleife ohne den anfänglichen Zweig dieselbe ist. Daraus können Sie ersehen, dass while()die Kosten der ersten Filiale, die jedoch nur einmal bezahlt wird, von Natur aus weniger effizient sind. [Vergleichen Sie mit der naiven Art der Implementierung, while,die sowohl einen bedingten als auch einen bedingungslosen Zweig pro Iteration erfordert.]

Trotzdem sind sie keine wirklich vergleichbaren Alternativen. Es ist schmerzhaft, eine whileSchleife in eine do-whileSchleife umzuwandeln und umgekehrt. Sie machen verschiedene Dinge. Und in diesem Fall die verschiedenen Methodenaufrufe würde völlig dominieren , was der Compiler tat mit whilegegendo-while.

Bei der Bemerkung geht es nicht um die Wahl der Steueranweisung (do vs. while), sondern um das Abrollen der Schleife !!!

Wie Sie sehen können, handelt es sich um eine Zeichenfolgenvergleichsfunktion (Zeichenfolgenelemente sind wahrscheinlich 2 Byte lang), die mit einem einzigen Vergleich anstelle von vier in einer Verknüpfung und einem Ausdruck geschrieben werden könnte.

Diese letztere Implementierung ist mit Sicherheit schneller, da nach jeweils vier Elementvergleichen eine einzige Überprüfung der Bedingung für das Ende der Zeichenfolge durchgeführt wird, während die Standardcodierung eine Überprüfung pro Vergleich beinhalten würde. Anders gesagt, 5 Tests pro 4 Elemente gegenüber 8 Tests pro 4 Elemente.

Auf jeden Fall funktioniert es nur, wenn die Zeichenfolgenlänge ein Vielfaches von vier ist oder ein Sentinel-Element enthält (sodass sich die beiden Zeichenfolgen garantiert über den strendRand hinaus unterscheiden). Ziemlich riskant!

Diese Diskussion über die Effizienz von while vs. do ist in diesem Fall völlig sinnlos, da es keinen Körper gibt.

while (Condition)
{
}

und

do
{
}
while (Condition);

sind absolut gleichwertig.