Signierter Überlauf in C ++ und undefiniertes Verhalten (UB)

Ich frage mich über die Verwendung von Code wie folgt

int result = 0;
int factor = 1;
for (...) {
    result = ...
    factor *= 10;
}
return result;

Wenn die Schleife über nZeiten iteriert wird, factorwird sie mit 10genau nZeiten multipliziert . Wird factorjedoch immer erst verwendet, nachdem es 10insgesamt multipliziert n-1wurde. Wenn wir davon ausgehen, dass es factornur bei der letzten Iteration der Schleife überläuft, aber bei der letzten Iteration der Schleife möglicherweise überläuft, sollte ein solcher Code dann akzeptabel sein? In diesem Fall factorwürde der Wert von nach dem Überlauf nachweislich nie verwendet.

Ich habe eine Debatte darüber, ob Code wie dieser akzeptiert werden sollte. Es wäre möglich, die Multiplikation in eine if-Anweisung einzufügen und die Multiplikation bei der letzten Iteration der Schleife nicht durchzuführen, wenn sie überlaufen kann. Der Nachteil ist, dass der Code unübersichtlich wird und ein unnötiger Zweig hinzugefügt wird, nach dem bei allen vorherigen Schleifeniterationen gesucht werden muss. Ich könnte auch ein Mal weniger über die Schleife iterieren und den Schleifenkörper einmal nach der Schleife replizieren, was wiederum den Code kompliziert.

Der eigentliche fragliche Code wird in einer engen inneren Schleife verwendet, die einen großen Teil der gesamten CPU-Zeit in einer Echtzeit-Grafikanwendung verbraucht.

Compiler gehen davon aus, dass ein gültiges C ++ - Programm kein UB enthält. Betrachten Sie zum Beispiel:

if (x == nullptr) {
    *x = 3;
} else {
    *x = 5;
}

Wenn x == nullptrdann die Dereferenzierung und Zuweisung eines Wertes UB ist. Daher kann dies nur dann zu einem gültigen Programm führen, wenn x == nullptres niemals true ergibt und der Compiler unter der Regel als ob annehmen kann, dass das oben Gesagte äquivalent ist zu:

*x = 5;

Jetzt in deinem Code

int result = 0;
int factor = 1;
for (...) {      // Loop until factor overflows but not more
   result = ...
   factor *= 10;
}
return result;

Die letzte Multiplikation von factorkann in einem gültigen Programm nicht erfolgen (signierter Überlauf ist undefiniert). Daher kann auch die Zuordnung resultnicht erfolgen. Da es keine Möglichkeit gibt, vor der letzten Iteration zu verzweigen, kann auch die vorherige Iteration nicht stattfinden. Schließlich ist der Teil des Codes, der korrekt ist (dh es passiert nie ein undefiniertes Verhalten):

// nothing :(

Das Verhalten des intÜberlaufs ist undefiniert.

Es spielt keine Rolle, ob Sie factoraußerhalb des Schleifenkörpers lesen . Wenn es bis dahin übergelaufen ist, ist das Verhalten Ihres Codes auf, nach und etwas paradoxerweise vor dem Überlauf undefiniert.

Ein Problem, das bei der Beibehaltung dieses Codes auftreten kann, ist, dass Compiler bei der Optimierung immer aggressiver werden. Insbesondere entwickeln sie eine Gewohnheit, bei der sie davon ausgehen, dass undefiniertes Verhalten niemals auftritt. In diesem Fall können sie die forSchleife vollständig entfernen .

Können Sie keinen unsignedTyp verwenden, factorobwohl Sie sich dann Gedanken über die unerwünschte Konvertierung von intin unsignedin Ausdrücken machen müssen, die beide enthalten?

Es könnte aufschlussreich sein, echte Optimierer in Betracht zu ziehen. Das Abrollen der Schleife ist eine bekannte Technik. Die Grundidee beim Abrollen der Schleife ist die folgende

for (int i = 0; i != 3; ++i)
    foo()

könnte hinter den Kulissen besser umgesetzt werden als

 foo()
 foo()
 foo()

Dies ist der einfache Fall mit einer festen Grenze. Moderne Compiler können dies aber auch für variable Grenzen tun:

for (int i = 0; i != N; ++i)
   foo();

wird

__RELATIVE_JUMP(3-N)
foo();
foo();
foo();

Dies funktioniert natürlich nur, wenn der Compiler weiß, dass N <= 3 ist. Und hier kommen wir zurück zur ursprünglichen Frage. Da der Compiler weiß, dass kein signierter Überlauf auftritt , weiß er, dass die Schleife auf 32-Bit-Architekturen maximal 9 Mal ausgeführt werden kann. 10^10 > 2^32. Es kann daher eine 9-Iterationsschleife abrollen. Aber das beabsichtigte Maximum war 10 Iterationen! .

Was passieren kann, ist, dass Sie einen relativen Sprung zu einer Assemblierungsanweisung (9-N) mit N = 10 erhalten, also einen Versatz von -1, was die Sprunganweisung selbst ist. Hoppla. Dies ist eine absolut gültige Schleifenoptimierung für genau definiertes C ++, aber das angegebene Beispiel wird zu einer engen Endlosschleife.

Jeder vorzeichenbehaftete Ganzzahlüberlauf führt zu einem undefinierten Verhalten, unabhängig davon, ob der übergelaufene Wert gelesen wird oder gelesen werden könnte.

Vielleicht können Sie in Ihrem Anwendungsfall die erste Iteration aus der Schleife heben und diese drehen

int result = 0;
int factor = 1;
for (int n = 0; n < 10; ++n) {
    result += n + factor;
    factor *= 10;
}
// factor "is" 10^10 > INT_MAX, UB

das sehr gut finden

int factor = 1;
int result = 0 + factor; // first iteration
for (int n = 1; n < 10; ++n) {
    factor *= 10;
    result += n + factor;
}
// factor is 10^9 < INT_MAX

Wenn die Optimierung aktiviert ist, rollt der Compiler möglicherweise die zweite Schleife oben in einen bedingten Sprung.

Das ist UB; In ISO C ++ ist das gesamte Verhalten des gesamten Programms für eine Ausführung, die schließlich UB trifft, völlig unbestimmt . Das klassische Beispiel ist, was den C ++ - Standard betrifft, dass Dämonen aus der Nase fliegen können. (Ich empfehle, keine Implementierung zu verwenden, bei der Nasendämonen eine echte Möglichkeit sind). Weitere Antworten finden Sie in anderen Antworten.

Compiler können zur Kompilierungszeit "Probleme verursachen", wenn Ausführungspfade angezeigt werden, die zu einer zur Kompilierungszeit sichtbaren UB führen. Nehmen wir beispielsweise an, dass diese Basisblöcke niemals erreicht werden.

Siehe auch Was jeder C-Programmierer über undefiniertes Verhalten wissen sollte (LLVM-Blog). Wie dort erläutert, können Compiler mit UB mit signiertem Überlauf beweisen, dass for(... i <= n ...)Schleifen auch für Unbekannte keine Endlosschleifen sind n. Außerdem können sie int-Schleifenzähler auf Zeigerbreite "heraufstufen", anstatt die Vorzeichenerweiterung zu wiederholen. (Die Konsequenz von UB in diesem Fall könnte also der Zugriff außerhalb der Low-64k- oder 4G-Elemente eines Arrays sein, wenn Sie eine vorzeichenbehaftete Umhüllung iin seinen Wertebereich erwarten .)

In einigen Fällen geben Compiler eine unzulässige Anweisung wie x86 ud2für einen Block aus, der nachweislich UB verursacht, wenn er jemals ausgeführt wird. (Beachten Sie, dass eine Funktion möglicherweise nicht immer aufgerufen werden, so Compiler kann im Allgemeinen nicht Amok und andere Funktionen brechen oder sogar mögliche Pfade durch eine Funktion , die UB nicht betroffen. Dh der Maschinencode kompiliert es muss noch viel Arbeit für alle Eingänge, die nicht zu UB führen.)

Die wahrscheinlich effizienteste Lösung besteht darin, die letzte Iteration manuell zu schälen, damit unnötige Iterationen factor*=10vermieden werden können.

int result = 0;
int factor = 1;
for (... i < n-1) {   // stop 1 iteration early
    result = ...
    factor *= 10;
}
 result = ...      // another copy of the loop body, using the last factor
 //   factor *= 10;    // and optimize away this dead operation.
return result;

Wenn der Schleifenkörper groß ist, sollten Sie einfach einen vorzeichenlosen Typ für verwenden factor. Dann können Sie den vorzeichenlosen Multiplikationsüberlauf zulassen, und es wird nur ein genau definierter Umbruch mit einer Potenz von 2 (der Anzahl der Wertbits im vorzeichenlosen Typ) durchgeführt.

Dies ist auch dann in Ordnung, wenn Sie es mit signierten Typen verwenden, insbesondere wenn Ihre nicht signierte> signierte Konvertierung nie überläuft.

Die Konvertierung zwischen vorzeichenlosem und vorzeichenbehaftetem 2er-Komplement ist kostenlos (gleiches Bitmuster für alle Werte). Das im C ++ - Standard angegebene Modulo-Wrapping für int -> unsigned vereinfacht die Verwendung des gleichen Bitmusters, anders als für das eigene Komplement oder Vorzeichen / die eigene Größe.

Und unsigned-> signiert ist ähnlich trivial, obwohl es für Werte größer als implementiert ist INT_MAX. Wenn Sie nicht mit dem riesigen unsigned Ergebnis der letzten Iteration, haben Sie nichts zu befürchten. Wenn ja, lesen Sie Ist die Konvertierung von nicht signiert zu signiert undefiniert? . Der Fall "Wert passt nicht" ist implementierungsdefiniert. Dies bedeutet, dass eine Implementierung ein bestimmtes Verhalten auswählen muss . Vernünftige schneiden das vorzeichenlose Bitmuster einfach ab (falls erforderlich) und verwenden es als vorzeichenbehaftet, da dies für Werte im Bereich auf die gleiche Weise ohne zusätzliche Arbeit funktioniert. Und es ist definitiv nicht UB. So können große Werte ohne Vorzeichen zu Ganzzahlen mit negativen Vorzeichen werden. zB nach int x = u; gcc und clang nicht weg optimierenx>=0wie immer wahr, auch ohne -fwrapv, weil sie das Verhalten definiert haben.

Wenn Sie ein paar zusätzliche Montageanweisungen in der Schleife tolerieren können, anstatt

int factor = 1;
for (int j = 0; j < n; ++j) {
    ...
    factor *= 10;
}

Du kannst schreiben:

int factor = 0;
for (...) {
    factor = 10 * factor + !factor;
    ...
}

um die letzte Multiplikation zu vermeiden. !factorwird keinen Zweig einführen:

    xor     ebx, ebx
L1:                       
    xor     eax, eax              
    test    ebx, ebx              
    lea     edx, [rbx+rbx*4]      
    sete    al    
    add     ebp, 1                
    lea     ebx, [rax+rdx*2]      
    mov     edi, ebx              
    call    consume(int)          
    cmp     r12d, ebp             
    jne     .L1                   

Dieser Code

int factor = 0;
for (...) {
    factor = factor ? 10 * factor : 1;
    ...
}

führt auch zu einer verzweigungslosen Montage nach der Optimierung:

    mov     ebx, 1
    jmp     .L1                   
.L2:                               
    lea     ebx, [rbx+rbx*4]       
    add     ebx, ebx
.L1:
    mov     edi, ebx
    add     ebp, 1
    call    consume(int)
    cmp     r12d, ebp
    jne     .L2

(Kompiliert mit GCC 8.3.0 -O3)

Sie haben nicht gezeigt, was in den Klammern der forAussage steht, aber ich gehe davon aus, dass es ungefähr so ​​ist:

for (int n = 0; n < 10; ++n) {
    result = ...
    factor *= 10;
}

Sie können das Zählerinkrement und die Schleifenbeendigungsprüfung einfach in den Body verschieben:

for (int n = 0; ; ) {
    result = ...
    if (++n >= 10) break;
    factor *= 10;
}

Die Anzahl der Montageanweisungen in der Schleife bleibt gleich.

Inspiriert von Andrei Alexandrescus Präsentation "Geschwindigkeit liegt in den Köpfen der Menschen".

Betrachten Sie die Funktion:

unsigned mul_mod_65536(unsigned short a, unsigned short b)
{
  return (a*b) & 0xFFFFu;
}

Gemäß der veröffentlichten Begründung hätten die Autoren des Standards erwartet, dass, wenn diese Funktion auf (z. B.) einem gewöhnlichen 32-Bit-Computer mit Argumenten von 0xC000 und 0xC000 aufgerufen würde, die Förderung der Operanden von *to signed intdazu führen würde, dass die Berechnung -0x10000000 ergibt , die, wenn sie konvertiert unsignedwürden, ergeben 0x90000000uwürden - die gleiche Antwort, als ob sie unsigned shortWerbung gemacht hätten unsigned. Trotzdem optimiert gcc diese Funktion manchmal auf eine Weise, die sich bei einem Überlauf unsinnig verhält. Jeder Code, bei dem eine Kombination von Eingaben einen Überlauf verursachen könnte, muss mit -fwrapvOption verarbeitet werden, es sei denn, es wäre akzeptabel, Erstellern von absichtlich fehlerhaften Eingaben zu erlauben, beliebigen Code ihrer Wahl auszuführen.

Warum nicht das:

int result = 0;
int factor = 10;
for (...) {
    factor *= 10;
    result = ...
}
return result;

Es gibt viele verschiedene Gesichter von undefiniertem Verhalten, und was akzeptabel ist, hängt von der Verwendung ab.

Enge innere Schleife, die einen großen Teil der gesamten CPU-Zeit in einer Echtzeit-Grafikanwendung verbraucht

Das ist an sich schon etwas ungewöhnlich, aber wie auch immer ... wenn dies tatsächlich der Fall ist, dann befindet sich die UB höchstwahrscheinlich im Bereich "zulässig, akzeptabel". . Grafikprogrammierung ist berüchtigt für Hacks und hässliche Sachen. Solange es "funktioniert" und es nicht länger als 16,6 ms dauert, um einen Rahmen zu produzieren, kümmert es normalerweise niemanden. Beachten Sie jedoch, was es bedeutet, UB aufzurufen.

Erstens gibt es den Standard. Unter diesem Gesichtspunkt gibt es nichts zu besprechen und keine Möglichkeit zu rechtfertigen, Ihr Code ist einfach ungültig. Es gibt kein Wenn und Wann, es ist einfach kein gültiger Code. Sie können genauso gut sagen, dass dies aus Ihrer Sicht ein Mittelfinger ist, und in 95-99% der Fälle können Sie trotzdem loslegen.

Als nächstes gibt es die Hardware-Seite. Es gibt einige ungewöhnliche, seltsame Architekturen, bei denen dies ein Problem darstellt. Ich sage "ungewöhnlich, seltsam", weil auf der einen Architektur, die 80% aller Computer ausmacht (oder auf den beiden Architekturen, die zusammen 95% aller Computer ausmachen), ein Überlauf ein "Ja, was auch immer, egal" ist. Sache auf der Hardware-Ebene. Sie erhalten zwar ein Müllergebnis (obwohl immer noch vorhersehbar), aber es passieren keine bösen Dinge.
Das ist nichtIn jedem Fall kann es durchaus vorkommen, dass der Überlauf in eine Falle gerät (obwohl Sie sehen, wie Sie von einer Grafikanwendung sprechen, sind die Chancen, auf einer so seltsamen Architektur zu arbeiten, eher gering). Ist Portabilität ein Problem? Wenn ja, möchten Sie sich vielleicht enthalten.

Zuletzt gibt es die Compiler / Optimierer-Seite. Ein Grund, warum Überlauf undefiniert ist, ist, dass es am einfachsten war, ihn einmal zu belassen, wenn man ihn einfach so belassen hat. Aber ein anderer Grund ist , dass zum Beispiel x+1ist garantiert immer größer als x, und der Compiler / Optimierer kann dieses Wissen nutzen. Für den zuvor erwähnten Fall ist bekannt, dass Compiler tatsächlich so handeln und einfach komplette Blöcke entfernen (es gab vor einigen Jahren einen Linux-Exploit, der darauf beruhte, dass der Compiler aus genau diesem Grund einen Validierungscode entfernt hat).
Für Ihren Fall würde ich ernsthaft bezweifeln, dass der Compiler einige spezielle, merkwürdige Optimierungen vornimmt. Was weißt du, was weiß ich? Probieren Sie es im Zweifelsfall aus. Wenn es funktioniert, können Sie loslegen.

(Und schließlich gibt es natürlich eine Code-Prüfung. Wenn Sie Pech haben, müssen Sie möglicherweise Ihre Zeit damit verschwenden, dies mit einem Prüfer zu besprechen.)