Programm verhält sich auf Online-IDEs seltsam

82

Ich bin auf das folgende C ++ - Programm ( Quelle ) gestoßen :

#include <iostream>
int main()
{
    for (int i = 0; i < 300; i++)
        std::cout << i << " " << i * 12345678 << std::endl;
}

Es sieht aus wie ein einfaches Programm und gibt die richtige Ausgabe auf meinem lokalen Computer aus, dh so etwas wie:

0 0
1 12345678
2 24691356
...
297 -628300930
298 -615955252
299 -603609574

Bei Online-IDEs wie codechef wird jedoch die folgende Ausgabe ausgegeben:

0 0
1 12345678
2 24691356
...
4167 -95167326
4168 -82821648
4169 -7047597

Warum endet die forSchleife nicht bei 300? Auch dieses Programm endet immer am 4169. Warum 4169und nicht irgendein anderer Wert?

Arpanmangal
quelle
45
Wahrscheinlich, weil der vorzeichenbehaftete Ganzzahlüberlauf ein undefiniertes Verhalten aufweist.
Eerorika
17
Ich weiß, signierter Überlauf ist UB, aber dies ist ein spektakulärer Fehler ...
Galik
45
Eine gute Lektion, wenn man nicht davon ausgeht, dass UB eingeschränkt ist
MM
12
Ich bin gespannt, warum Sie denken, dass die erste Ausgabe "die richtige Ausgabe" ist.
Leichtigkeitsrennen im Orbit
5
@LightnessRacesinOrbit - nun, diese Erinnerung ist wertvoll!
Davidbak

Antworten:

108

Ich gehe davon aus, dass die Online-Compiler GCC oder einen kompatiblen Compiler verwenden. Natürlich darf auch jeder andere Compiler die gleiche Optimierung durchführen, aber die GCC-Dokumentation erklärt gut, was er tut:

-faggressive-loop-optimizations

Diese Option weist den Schleifenoptimierer an, Sprachbeschränkungen zu verwenden, um Grenzen für die Anzahl der Iterationen einer Schleife abzuleiten. Dies setzt voraus, dass der Schleifencode kein undefiniertes Verhalten aufruft, indem er beispielsweise vorzeichenbehaftete Ganzzahlüberläufe oder nicht gebundene Array-Zugriffe verursacht. Die Grenzen für die Anzahl der Iterationen einer Schleife werden verwendet, um das Abrollen und Schälen der Schleife sowie die Optimierung des Schleifenausgangstests zu steuern. Diese Option ist standardmäßig aktiviert.

Diese Option ermöglicht lediglich Annahmen, die auf Fällen basieren, in denen UB nachgewiesen ist. Um diese Annahmen nutzen zu können, müssen möglicherweise andere Optimierungen aktiviert werden, z. B. die konstante Faltung.


Der vorzeichenbehaftete Ganzzahlüberlauf hat ein undefiniertes Verhalten. Der Optimierer konnte beweisen, dass ein Wert von imehr als 173 UB verursachen würde, und da er annehmen kann, dass es keine UB gibt, kann er auch annehmen, dass er iniemals größer als 173 ist. Er kann dann weiter beweisen, dass dies i < 300immer wahr ist, und so kann der Schleifenzustand weg optimiert werden.

Warum 4169 und kein anderer Wert?

Diese Sites begrenzen wahrscheinlich die Anzahl der Ausgabezeilen (oder Zeichen oder Bytes), die sie anzeigen, und teilen zufällig dieselbe Grenze.

Eerorika
quelle
3
Wenn der Compiler nachweisen kann, dass es UB für einen Wert von imehr als 173 gibt, warum gibt er dann keine Warnung aus, anstatt eine sinnlose Optimierung durchzuführen?
Jabberwocky
7
@ MichaelWalz Es gibt einen aus.
HolyBlackCat
3
@MichaelWalz: Das Entfernen redundanter boolescher Tests ist keine sinnlose Optimierung. es ist sehr nützlich. Was würde sein (meist) sinnlos ist das Hinzufügen von zusätzlichem Code zu sperren / rückgängig macht die Optimierung in Gegenwart von gebrochenem Quellcodes.
25
@MichaelWalz: Der Compiler kann UB nicht zuverlässig erkennen, wie Sie vorschlagen (obwohl er manchmal vor einem wahrscheinlichen Auftreten warnen kann, wie es hier tatsächlich der Fall ist). Stattdessen kann mit besten Absichten davon ausgegangen werden, dass es keine UB geben wird . Das sind zwei vielleicht subtile, aber tatsächlich wesentlich unterschiedliche Dinge. Es ist nicht so, dass der Compiler "aha! UB! Jetzt kann ich so und so eine Optimierung einschalten " - die Optimierung war immer da. Es macht die ganze Zeit solche Sachen . Solange Ihr Programm jedoch korrekt geschrieben ist, werden keine Änderungen an der potenziellen Semantik festgestellt.
Leichtigkeitsrennen im Orbit
20
Als Analogie könnte der Hersteller der Haustür Ihres Hauses entschieden haben, dass sie robuster wäre, wenn ein Stück Metall taktisch irgendwo in der Mitte platziert würde. Sie werden es nie bemerken, es sei denn, Sie schlagen Löcher in Ihre Tür und verwenden Türen falsch .
Leichtigkeitsrennen im Orbit
40

"Undefiniertes Verhalten ist undefiniert." (c)

Ein auf codechef verwendeter Compiler scheint folgende Logik zu verwenden:

  1. Undefiniertes Verhalten kann nicht passieren.
  2. i * 12345678läuft über und führt zu UB if i > 173(unter der Annahme von 32 Bit ints).
  3. Somit ikann nie überschreiten 173.
  4. Somit i < 300ist überflüssig und kann durch ersetzt werden true.

Die Schleife selbst scheint unendlich zu sein. Anscheinend stoppt codechef das Programm nur nach einer bestimmten Zeit oder schneidet die Ausgabe ab.

HolyBlackCat
quelle
11
@ArpanMangal Ich habe gerade die Zeichen in der Ausgabe gezählt, und es scheint zu sein 2^16. Anscheinend ist das ein Zufall, dass beide die Ausgabe auf 2^16Zeichen kürzen .
HolyBlackCat
3
@ArpanMangal: Nasendämonen wie 4169, und feiern derzeit bei ideone und codechef. UB ist undefiniert, es kann alles sein, einschließlich Nasendämonen. In aller Ernsthaftigkeit ist der Versuch, UB zu analysieren, Zeitverschwendung. Nutzen Sie diese Zeit, um herauszufinden, wie Sie dies verhindern können.
jmoreno
6
@jmoreno es ist keine Zeitverschwendung, wenn Sie am Compiler-Design interessiert sind
user253751
2
@jmoreno Diesmal war es jedoch möglich, es zu analysieren. Zu verstehen, wie genau UB Dinge kaputt macht, kann hilfreich sein, um zu schließen, in welchen Fällen UB akzeptabel ist, wenn überhaupt.
HolyBlackCat
4
@jmoreno Alles, was das Universum tut, ist (per Definition) korrekt. Was bringt es also, Astronomie zu studieren?
user253751
11

Sie rufen undefiniertes Verhalten wahrscheinlich bei der 174. Iteration in Ihrer forSchleife auf, da der intMaximalwert wahrscheinlich 2147483647noch 174 * 123456789Ausdruck ist, für 2148147972den ein undefiniertes Verhalten vorliegt, da kein vorzeichenbehafteter Ganzzahlüberlauf vorliegt. Sie beobachten also die Auswirkungen von UB, insbesondere beim GCC-Compiler mit in Ihrem Fall gesetzten Optimierungsflags. Es ist wahrscheinlich, dass der Compiler Sie mit der folgenden Warnung davor gewarnt hätte:

warning: iteration 174 invokes undefined behavior [-Waggressive-loop-optimizations]

Entfernen Sie die ( -O2) Optimierungsflags, um unterschiedliche Ergebnisse zu beobachten.

Ron
quelle
4
Es ist erwähnenswert, dass undefiniertes Verhalten rückwirkende Auswirkungen haben kann - da UB bei Iteration 174 auftreten würde, verlangt der Standard nicht einmal, dass die ersten 173 Iterationen der Schleife wie erwartet ablaufen!
@ Hurkyl In der Tat. Es ist etwas paradox, dass UB bewirkt, dass das gesamte Programm, einschließlich der vorherigen Aussagen, UB aufweist.
Ron
12
@ Ron: Es ist nicht paradox. Entweder hat das Programm eine genau definierte Semantik oder nicht. Zeitraum. Denken Sie daran, dass C ++ - Code keine Folge von auszuführenden Anweisungen ist. Es ist eine Beschreibung eines Programms .
Leichtigkeitsrennen im Orbit
@LightnessRacesinOrbit: Es ist möglich, dass ein Programm eine Semantik hat, die teilweise nicht spezifiziert, aber nicht vollständig undefiniert ist. Der C-Standard versucht, dieses Konzept auf das anzuwenden, was er "Bounded UB" nennt, obwohl die verwendete Sprache etwas vage ist. Wenn Compilern eine breite, aber nicht unbegrenzte Freiheit beim Umgang mit Dingen wie dem Überlauf von Ganzzahlen eingeräumt wird, würde dies viele ansonsten nützliche Optimierungen nicht beeinträchtigen, aber die Sprache für die Verarbeitung von Daten aus nicht vertrauenswürdigen Quellen viel besser geeignet machen.
Supercat
@supercat: In der Tat ist nicht spezifiziertes Verhalten nicht dasselbe wie undefiniertes Verhalten. Wir diskutieren das letztere
Leichtigkeitsrennen im Orbit
7

Der Compiler kann davon ausgehen, dass kein undefiniertes Verhalten auftritt, und da der signierte Überlauf UB ist, kann er davon ausgehen, dass niemals i * 12345678 > INT_MAX, also auch i <= INT_MAX / 12345678 < 300und daher die Prüfung entfernt wird i < 300.

Yassin
quelle