Optimieren ohne "while(1);" in C++0x

Question

Aktualisiert, siehe unten!

Ich habe gehört und gelesen, dass C++0x einem Compiler erlaubt, "Hello" für den folgenden Ausschnitt zu drucken

#include <iostream>

int main() {
  while(1) 
    ;
  std::cout << "Hello" << std::endl;
}

Es hat offenbar etwas mit Threads und Optimierungsmöglichkeiten zu tun. Es sieht so aus, als ob dies viele Leute überraschen kann.

Hat jemand eine gute Erklärung dafür, warum dies notwendig war, um dies zu erlauben? Zum Vergleich: Der jüngste C++0x-Entwurf sagt unter 6.5/5

Eine Schleife, die im Falle einer for-Anweisung außerhalb der for-init-Anweisung liegt,

• ruft keine Bibliotheks-E/A-Funktionen auf, und
• nicht auf flüchtige Objekte zugreift oder sie verändert, und
• keine Synchronisationsoperationen (1.10) oder atomare Operationen (Klausel 29) durchführt

kann von der Implementierung als beendet angenommen werden. [Hinweis: Dies soll Compiler-Transformationen ermöglichen. mationen, wie z.B. das Entfernen von Leerschleifen, zu ermöglichen, auch wenn die Terminierung nicht nachgewiesen werden kann. - end note ]

Edita:

Dieser aufschlussreiche Artikel sagt über diesen Standardtext

Leider werden die Worte "undefiniertes Verhalten" nicht verwendet. Immer wenn es in der Norm heißt: "Der Compiler kann P annehmen", wird damit impliziert, dass ein Programm, das die Eigenschaft not-P hat, eine undefinierte Semantik aufweist.

Ist das korrekt, und darf der Compiler "Bye" für das obige Programm ausgeben?

---

Es gibt eine noch aufschlussreichere Thread hier , in dem es um eine analoge Änderung zu C geht, die von dem Kerl aus dem oben verlinkten Artikel angestoßen wurde. Neben anderen nützlichen Fakten stellen sie eine Lösung vor, die auch für C++0x zu gelten scheint ( Update : Dies wird mit n3225 nicht mehr funktionieren - siehe unten!)

endless:
  goto endless;

Ein Compiler darf das nicht wegoptimieren, weil es sich nicht um eine Schleife, sondern um einen Sprung handelt. Ein anderer Mann fasst die vorgeschlagene Änderung in C++0x und C201X zusammen

Indem der Programmierer eine Schleife schreibt, behauptet er entweder dass die Schleife etwas mit sichtbarem Verhalten tut (E/A durchführt, auf flüchtige Objekte oder führt Synchronisierungs- oder atomare Operationen durch), oder dass sie schließlich beendet wird. Wenn ich diese Annahme verletze indem ich eine Endlosschleife ohne Seiteneffekte schreibe, belüge ich den Compiler an, und das Verhalten meines Programms ist undefiniert. (Wenn ich Glück habe, warnt mich der Compiler vielleicht davor.) Die Sprache bietet keine (nicht mehr?) eine Möglichkeit, eine Endlosschleife ohne sichtbares Verhalten auszudrücken.

---

Aktualisierung am 3.1.2011 mit n3225: Der Ausschuss hat den Text nach 1.10/24 verschoben und sagt

Bei der Implementierung kann davon ausgegangen werden, dass jeder Thread irgendwann eine der folgenden Aktionen ausführt:

• terminieren,
• einen Aufruf an eine Bibliotheks-E/A-Funktion machen,
• auf ein flüchtiges Objekt zuzugreifen oder es zu verändern, oder
• eine Synchronisationsoperation oder eine atomare Operation durchführen.

En goto Trick wird no nicht mehr funktionieren!

Answer 1

Für mich ist die relevante Rechtfertigung:

Dies soll Compilertransformationen ermöglichen, wie z.B. das Entfernen von Leerschleifen, auch wenn die Terminierung nicht nachgewiesen werden kann.

Vermutlich liegt dies daran, dass der Nachweis der Beendigung auf mechanischem Wege schwierig und die Unfähigkeit, die Terminierung zu beweisen, behindert Compiler, die ansonsten nützliche Transformationen vornehmen könnten, wie z. B. das Verschieben von nicht abhängigen Operationen von vor der Schleife auf nach der Schleife oder umgekehrt, das Ausführen von Operationen nach der Schleife in einem Thread, während die Schleife in einem anderen ausgeführt wird, und so weiter. Ohne diese Umwandlungen könnte eine Schleife alle anderen Threads blockieren, während sie darauf warten, dass der eine Thread die Schleife beendet. (Ich verwende den Begriff "Thread" frei und bezeichne damit jede Form der Parallelverarbeitung, einschließlich separater VLIW-Befehlsströme.)

EDIT: Dummes Beispiel:

while (complicated_condition()) {
    x = complicated_but_externally_invisible_operation(x);
}
complex_io_operation();
cout << "Results:" << endl;
cout << x << endl;

Hier wäre es schneller, wenn ein Thread die complex_io_operation während der andere alle komplexen Berechnungen in der Schleife durchführt. Aber ohne die von Ihnen zitierte Klausel muss der Compiler zwei Dinge beweisen, bevor er die Optimierung durchführen kann: 1) dass complex_io_operation() nicht von den Ergebnissen der Schleife abhängt, und 2) dass die Schleife beendet wird . Der Beweis von 1) ist ziemlich einfach, der Beweis von 2) ist das Problem des Haltens. Mit der Klausel kann man davon ausgehen, dass die Schleife endet und einen Parallelisierungsgewinn erzielen.

Ich kann mir auch vorstellen, dass die Entwickler bedacht haben, dass die Fälle, in denen Endlosschleifen im Produktionscode auftreten, sehr selten sind und es sich in der Regel um Dinge wie ereignisgesteuerte Schleifen handelt, die in irgendeiner Weise auf E/A zugreifen. Infolgedessen haben sie den seltenen Fall (Endlosschleifen) zugunsten der Optimierung des häufigeren Falls (nicht unendliche, aber mechanisch schwer zu beweisende Schleifen) pessimiert.

Dies bedeutet jedoch, dass Endlosschleifen, die in Lernbeispielen verwendet werden, darunter leiden und bei Anfängern zu Problemen führen werden. Ich kann nicht sagen, dass dies eine durchweg gute Sache ist.

EDIT: In Bezug auf den aufschlussreichen Artikel, den Sie jetzt verlinken, würde ich sagen, dass "der Compiler kann X über das Programm annehmen" logisch äquivalent zu "wenn das Programm X nicht erfüllt, ist das Verhalten undefiniert" ist. Wir können dies wie folgt zeigen: Nehmen wir an, es gibt ein Programm, das die Eigenschaft X nicht erfüllt. Wo würde das Verhalten dieses Programms definiert werden? Die Norm definiert das Verhalten nur unter der Annahme, dass die Eigenschaft X wahr ist. Obwohl die Norm das Verhalten nicht ausdrücklich für undefiniert erklärt, hat sie es durch Auslassung für undefiniert erklärt.

Betrachten Sie ein ähnliches Argument: "Der Compiler kann davon ausgehen, dass eine Variable x zwischen den Sequenzpunkten höchstens einmal zugewiesen wird" ist gleichbedeutend mit "Die Zuweisung von x mehr als einmal zwischen den Sequenzpunkten ist undefiniert".

Answer 2

Hat jemand eine gute Erklärung dafür, warum dies notwendig war, um dies zu erlauben?

Ja, Hans Boehm liefert eine Begründung dafür in N1528: Warum undefiniertes Verhalten bei Endlosschleifen? Obwohl es sich um ein Dokument der WG14 handelt, gelten die Überlegungen auch für C++, und das Dokument bezieht sich sowohl auf die WG14 als auch auf die WG21:

Wie N1509 richtig feststellt, gibt der aktuelle Entwurf im Wesentlichen undefiniertes Verhalten für Endlosschleifen in 6.8.5p6. Ein Hauptproblem für ist, dass es dem Code erlaubt, sich über eine potenziell nicht-abschließenden Schleife. Nehmen wir zum Beispiel die folgenden Schleifen an, wobei count und count2 globale Variablen sind (oder ihre Adresse genommen wurden) und p eine lokale Variable ist, deren Adresse noch nicht genommen wurde:

for (p = q; p != 0; p = p -> next) {
    ++count;
}
for (p = q; p != 0; p = p -> next) {
    ++count2;
}

Können diese beiden Schleifen zusammengelegt und durch die folgende Schleife ersetzt werden?

for (p = q; p != 0; p = p -> next) {
        ++count;
        ++count2;
}

Ohne die Sonderregelung in 6.8.5p6 für Endlosschleifen wäre dies wäre dies nicht erlaubt: Wenn die erste Schleife nicht abbricht, weil q auf eine zirkuläre Liste zeigt, schreibt das Original niemals in count2. Daher könnte sie parallel zu einem anderen Thread laufen, der auf die Liste zugreift oder count2 aktualisiert. Dies ist mit der transformierten Version nicht mehr sicher die trotz der Endlosschleife auf count2 zugreift. Daher ist die Transformation potentiell ein Datenrennen ein.

In Fällen wie diesem ist es sehr unwahrscheinlich, dass ein Compiler in der Lage ist Schleifenabbruch zu beweisen; er müsste verstehen, dass q auf eine auf eine azyklische Liste zeigt, was meines Erachtens jenseits der Fähigkeiten der meisten Mainstream-Compilern übersteigt und oft unmöglich ist, ohne das ganze Programm Informationen.

Die Beschränkungen, die durch nicht abschließende Schleifen entstehen, sind eine Beschränkung von die Optimierung von terminierenden Schleifen, für die der Compiler keine nicht beweisen kann, als auch die Optimierung von tatsächlich nicht terminierenden Schleifen. [ ] letztere und sind oft interessanter zu optimieren.

Natürlich gibt es auch for-Schleifen mit einer ganzen Zahl bei denen es für einen Compiler schwierig wäre, die Beendigung zu beweisen, und es für den Compiler also schwierig wäre, Schleifen umzustrukturieren ohne 6.8.5p6. Auch so etwas wie

for (i = 1; i != 15; i += 2)

o

for (i = 1; i <= 10; i += j)

scheint nicht trivial zu sein. (Im ersten Fall ist eine Grundzahl Zahlentheorie erforderlich, um die Beendigung zu beweisen, im letzteren Fall müssen wir müssen wir etwas über die möglichen Werte von j wissen, um dies zu tun. Umfassender für ganze Zahlen ohne Vorzeichen kann einige dieser Überlegungen weiter erschweren.)

Dieses Problem scheint zuzutreffen auf Umstrukturierungen, einschließlich Compiler-Parallelisierung und [ ] an Bedeutung gewinnen werden und für numerischen Code bereits häufig wichtig sind. Dies wird wahrscheinlich zu erheblichen Kosten für den Vorteil führen, dass der Möglichkeit, Endlosschleifen auf möglichst natürliche Weise zu schreiben, zumal die meisten von uns selten absichtlich Endlosschleifen schreiben.

Der einzige große Unterschied zu C besteht darin, dass C11 bietet eine Ausnahme für die Kontrolle von Ausdrücken, die konstante Ausdrücke sind was sich von C++ unterscheidet und Ihr spezifisches Beispiel in C11 wohldefiniert macht.

Answer 3

Ich denke, die korrekte Interpretation ist die aus Ihrer Bearbeitung: leere Endlosschleifen sind undefiniertes Verhalten.

Ich würde nicht sagen, dass es sich um ein besonders intuitives Verhalten handelt, aber diese Interpretation macht mehr Sinn als die Alternative, dass der Compiler willkürlich die Möglichkeit hat ignorieren. Endlosschleifen, ohne UB aufzurufen.

Wenn Endlosschleifen UB sind, bedeutet das nur, dass Programme, die nicht enden, nicht als sinnvoll angesehen werden: Nach C++0x sind sie haben keine Semantik.

Das ergibt auch einen gewissen Sinn. Sie sind ein Sonderfall, bei dem eine Reihe von Nebeneffekten einfach nicht mehr auftreten (zum Beispiel wird nie etwas von main ), und eine Reihe von Compiler-Optimierungen werden dadurch behindert, dass Endlosschleifen erhalten bleiben müssen. So ist beispielsweise die Verlagerung von Berechnungen über die Schleife hinweg durchaus zulässig, wenn die Schleife keine Seiteneffekte hat, denn schließlich wird die Berechnung in jedem Fall durchgeführt. Wenn die Schleife jedoch nie endet, können wir den Code nicht gefahrlos über die Schleife verschieben, weil wir かもしれない nur ändern, welche Operationen tatsächlich ausgeführt werden, bevor sich das Programm aufhängt. Es sei denn, wir behandeln ein hängendes Programm als UB, das heißt.

Answer 4

Der springende Punkt ist, dass der Compiler Code umordnen darf, dessen Seiteneffekte nicht in Konflikt stehen. Die überraschende Ausführungsreihenfolge könnte auch dann auftreten, wenn der Compiler für die Endlosschleife nicht-terminierenden Maschinencode erzeugt.

Ich glaube, das ist der richtige Ansatz. Die Sprachspezifikation definiert Wege, die Reihenfolge der Ausführung zu erzwingen. Wenn Sie eine Endlosschleife wollen, die nicht neu geordnet werden kann, schreiben Sie dies:

volatile int dummy_side_effect;

while (1) {
    dummy_side_effect = 0;
}

printf("Never prints.\n");

Answer 5

Ich denke, dass dies in die Richtung der folgenden Art von Frage die auf eine andere Gewinde . Durch die Optimierung können gelegentlich leere Schleifen entfernt werden.