Optimiere ein “while (1);” in C ++ 0x

Aktualisiert, siehe unten!

Ich habe gehört und gelesen, dass C ++ 0x einem Compiler ermöglicht, “Hallo” für das folgende Snippet zu drucken

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

Es hat offensichtlich etwas mit Threads und Optimierungsmöglichkeiten zu tun. Es sieht für mich aus, dass dies viele Menschen überraschen kann.

Hat jemand eine gute Erklärung, warum dies notwendig war? Als Referenz sagt der neueste C ++ 0x Entwurf um 6.5/5

Eine Schleife, die außerhalb der for-init-statement im Fall einer for-statement

  • ruft keine Bibliotheks-I / O-functionen auf und
  • nicht auf flüchtige Objekte zugreifen und diese ändern, und
  • führt keine Synchronisationsoperationen (1.10) oder atomaren Operationen durch (Klausel 29)

kann davon ausgegangen werden, dass die Implementierung beendet wird. [Hinweis: Dies soll Compilertransformationen ermöglichen, z. B. das Entfernen leerer Schleifen, selbst wenn die Beendigung nicht nachgewiesen werden kann. – Endnote]

Bearbeiten:

Dieser aufschlussreiche Artikel sagt über diesen Standardtext

Leider werden die Worte “undefined behaviour” nicht verwendet. Wenn jedoch der Standard sagt “der Compiler kann P annehmen”, wird vorausgesetzt, dass ein Programm, das die Eigenschaft not-P hat, eine undefinierte Semantik hat.

Ist das korrekt, und darf der Compiler “Bye” für das obige Programm drucken?


Es gibt einen noch aufschlussreicheren Thread hier , der von einer analogen Veränderung zu C handelt, die von dem Guy begonnen hat, den oben verlinkten Artikel. Neben anderen nützlichen Fakten stellen sie eine Lösung vor, die auch auf C ++ 0x zutreffen scheint ( Update : Das wird mit n3225 nicht mehr funktionieren – siehe unten!)

 endless: goto endless; 

Ein Compiler darf das anscheinend nicht optimieren, denn es ist keine Schleife, sondern ein Sprung. Ein anderer Typ 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 (führt I / O durch, greift auf flüchtige Objekte zu oder führt Synchronisation oder atomare Operationen durch) oder dass sie schließlich endet. Wenn ich diese Annahme verletze, indem ich eine Endlosschleife ohne Nebenwirkungen schreibe, lüge ich dem Compiler, und das Verhalten meines Programms ist nicht definiert. (Wenn ich Glück habe, könnte der Compiler mich davor warnen.) Die Sprache bietet keine Möglichkeit, eine Endlosschleife ohne sichtbares Verhalten auszudrücken.


Update am 3.1.2011 mit n3225: Komitee verlegt den Text auf 1.10 / 24 und sagt

Die Implementierung kann davon ausgehen, dass jeder Thread einen der folgenden Schritte ausführt:

  • beenden,
  • Rufen Sie eine Bibliotheks-E / A-function an,
  • auf ein flüchtiges Objekt zugreifen oder es ändern, oder
  • Führen Sie eine Synchronisationsoperation oder eine atomare Operation durch.

Der goto Trick wird nicht mehr funktionieren!

   

Hat jemand eine gute Erklärung, warum dies notwendig war?

Ja, dafür gibt Hans Böhm in N1528 eine Begründung : Warum undefiniertes Verhalten für Endlosschleifen? , obwohl dies WG14-Dokument ist, gilt die Begründung auch für C ++ und das Dokument bezieht sich sowohl auf WG14 als auch auf WG21:

Wie N1509 richtig hervorhebt, gibt der aktuelle Entwurf den unendlichen Schleifen in 6.8.5p6 im Wesentlichen undefiniertes Verhalten. Ein wichtiges Problem dabei ist, dass Code sich über eine potenziell nicht endende Schleife bewegen kann. Nehmen wir zum Beispiel an, dass wir die folgenden Schleifen haben, wobei count und count2 globale Variablen sind (oder dass ihre Adresse genommen wurde) und p eine lokale Variable ist, deren Adresse nicht vergeben wurde:

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

Könnten diese beiden Schleifen zusammengeführt und durch die folgende Schleife ersetzt werden?

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

Ohne die spezielle Dispensierung in 6.8.5p6 für Endlosschleifen wäre dies nicht erlaubt: Wenn die erste Schleife nicht beendet wird, weil q auf eine Kreisliste zeigt, schreibt das Original niemals in count2. Somit könnte es parallel zu einem anderen Thread ausgeführt werden, der count2 zugreift oder aktualisiert. Dies ist nicht mehr sicher mit der transformierten Version, die trotz Endlosschleife auf count2 zugreift. Somit führt die Transformation möglicherweise zu einem Datenrennen.

In solchen Fällen ist es sehr unwahrscheinlich, dass ein Compiler die Loop-Terminierung nachweisen kann. es müsste verstehen, dass q auf eine azyklische Liste verweist, die meiner Meinung nach die Fähigkeiten der meisten Mainstream-Compiler übersteigt und oft ohne vollständige Programminformationen unmöglich ist.

Die Beschränkungen, die durch nicht-endende Schleifen auferlegt werden, sind eine Beschränkung der Optimierung von Abschlußschleifen, für die der Compiler keine Beendigung nachweisen kann, sowie die Optimierung von tatsächlich nicht-endenden Schleifen. Erstere sind viel häufiger als letztere und oft interessanter zu optimieren.

Es gibt eindeutig auch for-Schleifen mit einer ganzzahligen Schleifenvariablen, in denen es für einen Compiler schwierig wäre, die Beendigung zu beweisen, und es wäre daher für den Compiler schwierig, Schleifen ohne 6.8.5p6 zu restrukturieren. Sogar so etwas wie

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

oder

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

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

Dieses Problem scheint für fast alle Schleifenumstrukturierungstransformationen zu gelten, einschließlich der Parallelisierung des Compilers und der Cache-Optimierungsumwandlungen, die beide an Bedeutung gewinnen und für den numerischen Code bereits oft wichtig sind. Dies wird wahrscheinlich zu einem erheblichen Kostenfaktor führen, da unendlich viele Schleifen auf die natürlichste Weise geschrieben werden können, zumal die meisten von uns selten absichtlich unendliche Schleifen schreiben.

Der eine Hauptunterschied zu C besteht darin, dass C11 eine Ausnahme für die Kontrolle von Ausdrücken bietet, die konstante Ausdrücke sind, die sich von C ++ unterscheiden und Ihr spezifisches Beispiel in C11 klar definiert.

Die relevante Rechtfertigung ist für mich:

Dies soll Compiler-Transformationen ermöglichen, z. B. das Entfernen von leeren Schleifen, auch wenn die Beendigung nicht nachgewiesen werden kann.

Vermutlich liegt dies daran, dass die mechanische Beendigung der Beendigung schwierig ist und die Unfähigkeit, die Beendigung zu beweisen, Compiler hemmt, die ansonsten nützliche Transformationen durchführen könnten, wie z. B. das Verschieben nichtabhängiger Operationen von vor der Schleife nach oder nach, während Post-Loop-Operationen in einem Thread ausgeführt werden Die Schleife wird in einem anderen ausgeführt und so weiter. Ohne diese Transformationen könnte eine Schleife alle anderen Threads blockieren, während sie darauf warten, dass der eine Thread die Schleife beendet. (Ich benutze “thread” lose, um jede Art von parallel processing zu verstehen, 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 für einen Thread, die complex_io_operation während der andere alle komplexen Berechnungen in der Schleife complex_io_operation . Aber ohne die Klausel, die Sie zitiert haben, muss der Compiler zwei Dinge beweisen, bevor er die Optimierung vornehmen kann: 1) dass complex_io_operation() nicht von den Ergebnissen der Schleife abhängt, und 2) dass die Schleife beendet wird . Der Nachweis 1) ist ziemlich einfach, was beweist, 2) ist das Anhalten-Problem. Mit der Klausel kann angenommen werden, dass die Schleife endet und einen Parallelisierungsgewinn erhält.

Ich stelle mir auch vor, dass die Designer der Ansicht waren, dass die Fälle, in denen Endlosschleifen im Produktionscode auftreten, sehr selten sind und normalerweise Dinge wie ereignisgesteuerte Schleifen sind, die auf I / O in irgendeiner Weise zugreifen. Als Ergebnis haben sie den seltenen Fall pessimisiert (Endlosschleifen), um den häufigeren Fall zu optimieren (nicht-infinite, aber mechanisch schwer zu bearbeitende nicht-endliche Schleifen).

Es bedeutet jedoch, dass Endlosschleifen, die in Lernbeispielen verwendet werden, darunter leiden werden, und werden Fehler im Anfängercode auslösen. Ich kann nicht sagen, dass das eine gute Sache ist.

EDIT: in Bezug auf den aufschlussreichen Artikel, den Sie jetzt verknüpfen, würde ich sagen, dass "der Compiler X über das Programm annehmen kann" ist logisch äquivalent zu "wenn das Programm X nicht erfüllt, ist das Verhalten nicht definiert". Wir können dies wie folgt zeigen: Angenommen, es existiert ein Programm, das die Eigenschaft X nicht erfüllt. Wo würde das Verhalten dieses Programms definiert? Der Standard definiert nur Verhalten, wenn Eigenschaft X wahr ist. Obwohl der Standard das Verhalten nicht explizit als undefiniert deklariert, hat er es durch Unterlassung als undefiniert deklariert.

Stellen Sie sich ein ähnliches Argument vor: "Der Compiler darf annehmen, dass eine Variable x höchstens einmal zwischen den Sequenzpunkten zugewiesen ist" entspricht "mehrmaliges Zuweisen von x zwischen Sequenzpunkten ist nicht definiert".

Ich denke, die richtige Interpretation ist diejenige aus Ihrer Bearbeitung: Leere Endlosschleifen sind undefiniertes Verhalten.

Ich würde nicht sagen, dass es ein besonders intuitives Verhalten ist, aber diese Interpretation macht mehr Sinn als die Alternative, dass der Compiler willkürlich Endlosschleifen ignorieren darf, ohne UB aufzurufen.

Wenn Endlosschleifen UB sind, bedeutet dies nur, dass nicht terminierende Programme nicht als sinnvoll erachtet werden: Laut C ++ 0x haben sie keine Semantik.

Das macht auch eine gewisse Menge Sinn. Sie sind ein Spezialfall, bei dem eine Reihe von Nebeneffekten einfach nicht mehr auftreten (z. B. wird nichts mehr von main ), und eine Reihe von Compileroptimierungen wird dadurch behindert, dass Endlosschleifen beibehalten werden müssen. Zum Beispiel ist das Verschieben von Berechnungen über die Schleife vollkommen gültig, wenn die Schleife keine Nebenwirkungen hat, weil schließlich die Berechnung in jedem Fall durchgeführt wird. Aber wenn die Schleife niemals endet, können wir den Code nicht sicher über sie hinweg anordnen, weil wir vielleicht nur ändern, welche Operationen tatsächlich ausgeführt werden, bevor das Programm aufhängt. Es sei denn, wir behandeln ein hängendes Programm als UB.

Ich denke, dies entspricht der Art dieser Frage , die auf einen anderen Thread verweist. Die Optimierung kann gelegentlich leere Schleifen entfernen.

Das relevante Problem ist, dass der Compiler Code neu ordnen darf, dessen Nebenwirkungen nicht in Konflikt stehen. Die überraschende Reihenfolge der Ausführung könnte auftreten, selbst wenn der Compiler nicht-terminierenden Maschinencode für die Endlosschleife erzeugt.

Ich glaube, das ist der richtige Ansatz. Die Sprachspezifikation definiert Möglichkeiten zum Erzwingen der Ausführungsreihenfolge. Wenn Sie eine Endlosschleife möchten, die nicht umsortiert werden kann, schreiben Sie Folgendes:

 volatile int dummy_side_effect; while (1) { dummy_side_effect = 0; } printf("Never prints.\n"); 

Ich denke, das Problem könnte vielleicht am besten wie folgt formuliert werden: “Wenn ein späteres Stück Code nicht von einem früheren Stück Code abhängt und das frühere Stück Code keine Nebeneffekte auf irgendeinen anderen Teil des Systems hat, wird der Compiler ausgegeben kann das spätere Stück Code vor, nach oder mit der Ausführung des ersteren ausführen, selbst wenn das erstere Schleifen enthält, ohne Rücksicht darauf, wann oder ob der vorherige Code tatsächlich vervollständigt werden würde . Zum Beispiel könnte der Compiler neu schreiben:

 void testfermat (int n)
 {
   int a = 1, b = 1, c = 1;
   while (pow (a, n) + pow (b, n)! = pow (c, n))
   {
     if (b> a) a ++;  sonst wenn (c> b) {a = 1;  b ++};  sonst {a = 1;  b = 1;  C ++};
   }
   printf ("Das Ergebnis ist");
   printf ("% d /% d /% d", a, b, c);
 }

wie

 void testfermat (int n)
 {
   if (fork_is_first_thread ())
   {
     int a = 1, b = 1, c = 1;
     while (pow (a, n) + pow (b, n)! = pow (c, n))
     {
       if (b> a) a ++;  sonst wenn (c> b) {a = 1;  b ++};  sonst {a = 1;  b = 1;  C ++};
     }
     signal_other_thread_and_die ();
   }
   else // Zweiter Thread
   {
     printf ("Das Ergebnis ist");
     wait_for_other_thread ();
   }
   printf ("% d /% d /% d", a, b, c);
 }

Im Allgemeinen nicht unvernünftig, obwohl ich mir Sorgen machen könnte, dass:

   int gesamt = 0;
   für (i = 0; num_reps> i; i ++)
   {
     update_progress_bar (i);
     total + = do_something_slow_with_no_side_effects (i);
   }
   show_result (gesamt);

würde werden

   int gesamt = 0;
   if (fork_is_first_thread ())
   {
     für (i = 0; num_reps> i; i ++)
       total + = do_something_slow_with_no_side_effects (i);
     signal_other_thread_and_die ();
   }
   sonst
   {
     für (i = 0; num_reps> i; i ++)
       update_progress_bar (i);
     wait_for_other_thread ();
   }
   show_result (gesamt);

Wenn eine CPU die Berechnungen übernimmt und ein anderer die Aktualisierung der Fortschrittsbalken übernimmt, würde das Neuschreiben die Effizienz verbessern. Leider würde dies dazu führen, dass die Fortschrittsbalken nicht mehr so ​​nützlich sind, wie sie sein sollten.

Es ist nicht entscheidbar für den Compiler für nicht-triviale Fälle, wenn es überhaupt eine Endlosschleife ist.

In verschiedenen Fällen kann es passieren, dass Ihr Optimierer eine bessere Komplexitätsklasse für Ihren Code erreicht (zB war er O (n ^ 2) und Sie erhalten nach der Optimierung O (n) oder O (1)).

Eine solche Regel einzuschließen, die das Entfernen einer Endlosschleife in den C ++ – Standard nicht erlaubt, würde viele Optimierungen unmöglich machen. Und die meisten Leute wollen das nicht. Ich denke, das beantwortet deine Frage ziemlich.


Eine andere Sache: Ich habe nie ein gültiges Beispiel gesehen, wo Sie eine Endlosschleife brauchen, die nichts tut.

Das eine Beispiel, von dem ich gehört habe, war ein hässlicher Hack, der eigentlich anders getriggers werden sollte: Es ging um eingebettete Systeme, bei denen die einzige Möglichkeit, einen Reset auszulösen, das Gerät einfrieren würde, so dass der Watchdog es automatisch neu startet.

Wenn Sie ein gültiges / gutes Beispiel kennen, wo Sie eine Endlosschleife brauchen, die nichts tut, sagen Sie es mir bitte.

Ich denke, es lohnt sich, darauf hinzuweisen, dass Schleifen, die unendlich sind, abgesehen von der Tatsache, dass sie mit anderen Threads über nichtflüchtige, nicht synchronisierte Variablen interagieren, jetzt ein falsches Verhalten mit einem neuen Compiler ergeben können.

Mit anderen Worten, machen Sie Ihre Globals flüchtig – ebenso wie Argumente in eine solche Schleife über pointers / Verweis weitergegeben werden.