Warum kann (oder tut) der Compiler eine vorhersehbare Additionsschleife nicht in eine Multiplikation optimieren?

Lesezeit: 11 Minuten

Benutzeravatar von jhabbott
jhabbott

Diese Frage kam mir in den Sinn, als ich die brillante Antwort von Mystcial auf die Frage las: Warum ist es schneller, ein sortiertes Array zu verarbeiten als ein unsortiertes Array?

Kontext für die beteiligten Typen:

const unsigned arraySize = 32768;
int data[arraySize];
long long sum = 0;

In seiner Antwort erklärt er, dass der Intel Compiler (ICC) dies optimiert:

for (int i = 0; i < 100000; ++i)
    for (int c = 0; c < arraySize; ++c)
        if (data[c] >= 128)
            sum += data[c];

…in etwas Äquivalent zu diesem:

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        for (int i = 0; i < 100000; ++i)
            sum += data[c];

Der Optimierer erkennt, dass diese äquivalent sind und ist es daher Schleifen austauschen, wobei der Zweig aus der inneren Schleife heraus bewegt wird. Sehr schlau!

Aber warum tut es das nicht?

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        sum += 100000 * data[c];

Hoffentlich kann Mysticial (oder sonst jemand) eine ebenso brillante Antwort geben. Ich habe noch nie etwas über die in dieser anderen Frage besprochenen Optimierungen erfahren, daher bin ich dafür wirklich dankbar.

  • Das ist etwas, das wahrscheinlich nur Intel weiß. Ich weiß nicht, in welcher Reihenfolge seine Optimierungsdurchläufe ausgeführt werden. Und anscheinend führt es nach dem Schleifenaustausch keinen Loop-Collapsing-Pass aus.

    – Mystisch

    30. Juni 2012 um 18:02 Uhr


  • Diese Optimierung ist nur gültig, wenn die im Datenarray enthaltenen Werte unveränderlich sind. Zum Beispiel, wenn die sind Speicher abgebildet jedes Mal, wenn Sie Daten lesen, an ein Ein-/Ausgabegerät[0] ergibt einen anderen wert…

    – Thomas CG de Vilhena

    30. Juni 2012 um 18:02 Uhr

  • Welcher Datentyp ist das, Ganzzahl oder Fließkommazahl? Die wiederholte Addition in Gleitkommazahlen ergibt ganz andere Ergebnisse als die Multiplikation.

    – Ben Voigt

    30. Juni 2012 um 18:02 Uhr

  • @Thomas: Wären die Daten volatiledann wäre der Schleifenaustausch ebenfalls eine ungültige Optimierung.

    – Ben Voigt

    30. Juni 2012 um 18:26 Uhr

  • GNAT (Ada-Compiler mit GCC 4.6) schaltet die Schleifen bei O3 nicht um, aber wenn die Schleifen umgeschaltet werden, wandelt es sie in eine Multiplikation um.

    – prosfilae

    21. Mai 2013 um 20:06 Uhr

Benutzeravatar von Daniel Fischer
Daniel Fischer

Der Compiler kann im Allgemeinen nicht transformieren

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        for (int i = 0; i < 100000; ++i)
            sum += data[c];

hinein

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        sum += 100000 * data[c];

weil letzteres zu einem Überlauf von vorzeichenbehafteten Ganzzahlen führen könnte, wo ersteres nicht der Fall ist. Selbst bei garantiertem Wrap-Around-Verhalten für den Überlauf von vorzeichenbehafteten Zweierkomplement-Ganzzahlen würde sich das Ergebnis ändern (if data[c] 30000 ist, würde das Produkt werden -1294967296 für die typischen 32-Bit ints mit Wrap-around, während 100000 mal 30000 zu addieren sum würde, wenn das nicht überläuft, zunehmen sum um 3000000000). Beachten Sie, dass dasselbe für vorzeichenlose Mengen mit unterschiedlichen Zahlen gilt, Überlauf von 100000 * data[c] würde typischerweise eine Modulo-Reduktion einführen 2^32 das darf im Endergebnis nicht auftauchen.

Es könnte es verwandeln in

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        sum += 100000LL * data[c];  // resp. 100000ull

aber wenn, wie üblich, long long ausreichend größer ist als int.

Warum es das nicht tut, kann ich nicht sagen, ich denke, es ist das, was Mystcial gesagt hat: “Anscheinend führt es nach dem Loop-Austausch keinen Loop-Collapsing-Pass aus”.

Beachten Sie, dass der Schleifenaustausch selbst nicht allgemeingültig ist (für vorzeichenbehaftete Ganzzahlen), da

for (int c = 0; c < arraySize; ++c)
    if (condition(data[c]))
        for (int i = 0; i < 100000; ++i)
            sum += data[c];

wo zum Überlaufen führen kann

for (int i = 0; i < 100000; ++i)
    for (int c = 0; c < arraySize; ++c)
        if (condition(data[c]))
            sum += data[c];

würde nicht. Hier ist es koscher, da sorgt der Zustand für alles data[c] die hinzugefügt werden, haben das gleiche Vorzeichen, wenn also einer überläuft, tun es beide.

Ich wäre mir nicht sicher, ob der Compiler das berücksichtigt hat, aber (@Mystcial, könnten Sie es mit einer Bedingung wie versuchen data[c] & 0x80 oder kann das für positive und negative Werte gelten?). Ich hatte Compiler, die ungültige Optimierungen vornahmen (zum Beispiel hatte ich vor ein paar Jahren eine ICC (11.0, iirc) mit signierter 32-Bit-int-to-double-Konvertierung in 1.0/n wo n war ein unsigned int. War etwa doppelt so schnell wie die Ausgabe von gcc. Aber falsch, viele Werte waren größer als 2^31Hoppla.).

  • Ich erinnere mich an eine Version des MPW-Compilers, die eine Option hinzugefügt hat, um Stack-Frames zuzulassen, die größer als 32 KB sind [earlier versions were limited using @A7+int16 addressing for local variables]. Es hat alles richtig gemacht für Stack-Frames unter 32 KB oder über 64 KB, aber für einen 40-K-Stack-Frame würde es verwendet werden ADD.W A6,$A000, wobei zu vergessen ist, dass Wortoperationen mit Adressregistern das Wort vor der Addition auf 32 Bit erweitern. Die Fehlerbehebung hat eine Weile gedauert, da das einzige, was der Code dazwischen getan hat ADD und das nächste Mal, als es A6 vom Stack entfernte, war es, die Register des Anrufers wiederherzustellen, die es in diesem Frame gespeichert hat …

    – Superkatze

    3. April 2013 um 16:46 Uhr


  • … und das einzige Register, das den Anrufer interessierte, war das [load-time constant] Adresse eines statischen Arrays. Der Compiler wusste, dass die Adresse des Arrays in einem Register gespeichert wurde, damit er darauf basierend optimieren konnte, aber der Debugger kannte einfach die Adresse einer Konstante. Also vor einer Aussage MyArray[0] = 4; Ich könnte die Adresse von überprüfen MyArray, und sehen Sie sich diese Stelle vor und nach der Ausführung der Anweisung an; es würde sich nicht ändern. Code war so etwas wie move.B @A3,#4 und A3 sollte immer auf zeigen MyArray Jedes Mal, wenn diese Anweisung ausgeführt wurde, aber nicht. Spaß.

    – Superkatze

    3. April 2013 um 16:51 Uhr

  • Warum führt clang dann diese Art der Optimierung durch?

    – Jason S

    31. Dezember 2019 um 16:14 Uhr

  • Der Compiler könnte dieses Umschreiben in seinen internen Zwischendarstellungen durchführen, da er weniger undefiniertes Verhalten in seinen internen Zwischendarstellungen haben darf.

    – Benutzer253751

    6. Januar 2020 um 17:35 Uhr

Benutzeravatar von Ben Voigt
Ben Voigt

Diese Antwort trifft nicht auf den verlinkten konkreten Fall zu, wohl aber auf den Fragetitel und könnte für zukünftige Leser interessant sein:

Aufgrund der endlichen Genauigkeit ist eine wiederholte Gleitkommaaddition nicht gleichbedeutend mit einer Multiplikation. In Betracht ziehen:

float const step = 1e-15;
float const init = 1;
long int const count = 1000000000;

float result1 = init;
for( int i = 0; i < count; ++i ) result1 += step;

float result2 = init;
result2 += step * count;

cout << (result1 - result2);

Demo

  • Das ist keine Antwort auf die gestellte Frage. Trotz interessanter Informationen (und ein Muss für jeden C/C++-Programmierer), ist dies kein Forum und gehört nicht hierher.

    – orlp

    30. Juni 2012 um 18:11 Uhr


  • @nightcracker: Das erklärte Ziel von StackOverflow ist es, eine durchsuchbare Bibliothek mit Antworten aufzubauen, die für zukünftige Benutzer nützlich sind. Und dies ist eine Antwort auf die gestellte Frage … es kommt einfach vor, dass es einige unausgesprochene Informationen gibt, die dazu führen, dass diese Antwort nicht für das Originalplakat gilt. Es kann immer noch für andere mit der gleichen Frage gelten.

    – Ben Voigt

    30. Juni 2012 um 18:14 Uhr


  • Es ist könnte eine Antwort auf die Frage sein Titelaber nicht die Frage, nein.

    – orlp

    30. Juni 2012 um 18:15 Uhr


  • Wie gesagt, ist es interessant Information. Dennoch erscheint es mir falsch, dass nota bene the Top-Antwort der Frage beantwortet die Frage nicht so, wie sie jetzt steht. Das ist einfach nicht der Grund, warum der Intel-Compiler entschieden hat, nicht zu optimieren, basta.

    – orlp

    30. Juni 2012 um 18:21 Uhr


  • @nightcracker: Es scheint mir auch falsch zu sein, dass dies die beste Antwort ist. Ich hoffe, dass jemand eine wirklich gute Antwort für den Integer-Fall veröffentlicht, der diesen in der Punktzahl übertrifft. Leider glaube ich nicht, dass es für den Integer-Fall eine Antwort auf “kann nicht” gibt, da die Transformation legal wäre, also bleibt uns das “warum nicht”, was tatsächlich mit dem ” zu lokalisiert” enger Grund, weil es für eine bestimmte Compiler-Version typisch ist. Die Frage, die ich beantwortet habe, ist die wichtigere, IMO.

    – Ben Voigt

    30. Juni 2012 um 18:25 Uhr

Der Compiler enthält verschiedene Durchgänge, die die Optimierung durchführen. Normalerweise werden in jedem Durchlauf entweder eine Optimierung an Anweisungen oder Schleifenoptimierungen durchgeführt. Derzeit gibt es kein Modell, das eine Optimierung des Schleifenkörpers basierend auf den Schleifenköpfen durchführt. Dies ist schwer zu erkennen und seltener.

Die durchgeführte Optimierung war eine schleifeninvariante Codebewegung. Dies kann mit einer Reihe von Techniken erfolgen.

Benutzeravatar von Jason S
Jason S

Das tut es jetzt – Clang tut es zumindest:

long long add_100k_signed(int *data, int arraySize)
{
    long long sum = 0;

    for (int c = 0; c < arraySize; ++c)
        if (data[c] >= 128)
            for (int i = 0; i < 100000; ++i)
                sum += data[c];
    return sum;
}

kompiliert mit -O1 zu

add_100k_signed:                        # @add_100k_signed
        test    esi, esi
        jle     .LBB0_1
        mov     r9d, esi
        xor     r8d, r8d
        xor     esi, esi
        xor     eax, eax
.LBB0_4:                                # =>This Inner Loop Header: Depth=1
        movsxd  rdx, dword ptr [rdi + 4*rsi]
        imul    rcx, rdx, 100000
        cmp     rdx, 127
        cmovle  rcx, r8
        add     rax, rcx
        add     rsi, 1
        cmp     r9, rsi
        jne     .LBB0_4
        ret
.LBB0_1:
        xor     eax, eax
        ret

Ganzzahlüberlauf hat damit nichts zu tun; Wenn es einen Ganzzahlüberlauf gibt, der undefiniertes Verhalten verursacht, kann dies in beiden Fällen passieren. Hier ist die gleiche Art von Funktion mit int Anstatt von long:

int add_100k_signed(int *data, int arraySize)
{
    int sum = 0;

    for (int c = 0; c < arraySize; ++c)
        if (data[c] >= 128)
            for (int i = 0; i < 100000; ++i)
                sum += data[c];
    return sum;
}

kompiliert mit -O1 zu

add_100k_signed:                        # @add_100k_signed
        test    esi, esi
        jle     .LBB0_1
        mov     r9d, esi
        xor     r8d, r8d
        xor     esi, esi
        xor     eax, eax
.LBB0_4:                                # =>This Inner Loop Header: Depth=1
        mov     edx, dword ptr [rdi + 4*rsi]
        imul    ecx, edx, 100000
        cmp     edx, 127
        cmovle  ecx, r8d
        add     eax, ecx
        add     rsi, 1
        cmp     r9, rsi
        jne     .LBB0_4
        ret
.LBB0_1:
        xor     eax, eax
        ret

AnT steht mit Russlands Benutzer-Avatar
AnT steht zu Russland

Nun, ich würde vermuten, dass einige Compiler diese Art der Optimierung durchführen könnten, vorausgesetzt, wir sprechen über ganzzahlige Arithmetik.

Gleichzeitig könnten sich einige Compiler weigern, dies zu tun, da das Ersetzen der wiederholten Addition durch Multiplikation das Überlaufverhalten des Codes ändern könnte. Bei vorzeichenlosen Integer-Typen sollte dies keinen Unterschied machen, da ihr Überlaufverhalten vollständig von der Sprache festgelegt wird. Aber für signierte könnte es (wahrscheinlich nicht auf der 2er-Komplement-Plattform). Es ist wahr, dass ein signierter Überlauf tatsächlich zu undefiniertem Verhalten in C führt, was bedeutet, dass es völlig in Ordnung sein sollte, diese Überlaufsemantik vollständig zu ignorieren, aber nicht alle Compiler sind mutig genug, dies zu tun. Es zieht oft viel Kritik von der Menge der “C ist nur eine Assemblersprache auf höherer Ebene” auf sich. (Erinnern Sie sich, was passiert ist, als GCC Optimierungen basierend auf strikter Aliasing-Semantik eingeführt hat?)

In der Vergangenheit hat sich GCC als ein Compiler erwiesen, der das Zeug dazu hat, solch drastische Schritte zu unternehmen, aber andere Compiler ziehen es möglicherweise vor, an dem wahrgenommenen “benutzerbeabsichtigten” Verhalten festzuhalten, selbst wenn es nicht durch die Sprache definiert ist.

  • Ich würde es vorziehen zu wissen, ob ich versehentlich von undefiniertem Verhalten abhängig bin, aber ich denke, der Compiler hat keine Möglichkeit, dies zu wissen, da der Überlauf ein Laufzeitproblem wäre: /

    – jhabbott

    30. Juni 2012 um 18:14 Uhr

  • @jhabbott: iff der Überlauf auftritt, dann gibt es undefiniertes Verhalten. Ob das Verhalten definiert ist, ist bis zur Laufzeit unbekannt (vorausgesetzt, die Zahlen werden zur Laufzeit eingegeben) :P.

    – orlp

    30. Juni 2012 um 18:25 Uhr

Es gibt ein konzeptionelles Hindernis für diese Art der Optimierung. Compiler-Autoren geben sich viel Mühe Kraftreduzierung — zum Beispiel das Ersetzen von Multiplikationen durch Additionen und Verschiebungen. Sie gewöhnen sich daran zu denken, dass Multiplikationen schlecht sind. Ein Fall, in dem man den anderen Weg gehen sollte, ist also überraschend und kontraintuitiv. Also denkt niemand daran, es umzusetzen.

  • Ich würde es vorziehen zu wissen, ob ich versehentlich von undefiniertem Verhalten abhängig bin, aber ich denke, der Compiler hat keine Möglichkeit, dies zu wissen, da der Überlauf ein Laufzeitproblem wäre: /

    – jhabbott

    30. Juni 2012 um 18:14 Uhr

  • @jhabbott: iff der Überlauf auftritt, dann gibt es undefiniertes Verhalten. Ob das Verhalten definiert ist, ist bis zur Laufzeit unbekannt (vorausgesetzt, die Zahlen werden zur Laufzeit eingegeben) :P.

    – orlp

    30. Juni 2012 um 18:25 Uhr

Benutzeravatar von dfeuer
dfeuer

Die Leute, die Compiler entwickeln und warten, haben nur begrenzt Zeit und Energie für ihre Arbeit, daher möchten sie sich im Allgemeinen auf das konzentrieren, was ihren Benutzern am wichtigsten ist: gut geschriebenen Code in schnellen Code umzuwandeln. Sie wollen ihre Zeit nicht damit verschwenden, Wege zu finden, um dummen Code in schnellen Code umzuwandeln – dafür ist Code-Review da. In einer Hochsprache kann es „dummen“ Code geben, der eine wichtige Idee ausdrückt, sodass sich die Zeit der Entwickler lohnt, dies schnell zu machen – zum Beispiel ermöglichen Abkürzungs-Abholzung und Stream-Fusion Haskell-Programme, die um bestimmte Arten von Faulheit herum strukturiert sind erzeugte Datenstrukturen, die in enge Schleifen kompiliert werden, die keinen Speicher zuweisen. Aber diese Art von Anreiz gilt einfach nicht, um die Schleifenaddition in eine Multiplikation umzuwandeln. Wenn es schnell gehen soll, schreibe es einfach mit Multiplikation.

1423420cookie-checkWarum kann (oder tut) der Compiler eine vorhersehbare Additionsschleife nicht in eine Multiplikation optimieren?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy