Beim Schreiben einer optimierten ftol
Funktion habe ich ein sehr merkwürdiges Verhalten festgestellt GCC 4.6.1
. Lassen Sie mich Ihnen zuerst den Code zeigen (aus Gründen der Klarheit habe ich die Unterschiede markiert):
fast_trunc_one, C:
int fast_trunc_one(int i) {
int mantissa, exponent, sign, r;
mantissa = (i & 0x07fffff) | 0x800000;
exponent = 150 - ((i >> 23) & 0xff);
sign = i & 0x80000000;
if (exponent < 0) {
r = mantissa << -exponent; /* diff */
} else {
r = mantissa >> exponent; /* diff */
}
return (r ^ -sign) + sign; /* diff */
}
fast_trunc_two, C:
int fast_trunc_two(int i) {
int mantissa, exponent, sign, r;
mantissa = (i & 0x07fffff) | 0x800000;
exponent = 150 - ((i >> 23) & 0xff);
sign = i & 0x80000000;
if (exponent < 0) {
r = (mantissa << -exponent) ^ -sign; /* diff */
} else {
r = (mantissa >> exponent) ^ -sign; /* diff */
}
return r + sign; /* diff */
}
Scheint das gleiche richtig? Nun, GCC ist anderer Meinung. Nach dem Kompilieren ist gcc -O3 -S -Wall -o test.s test.c
dies die Assembly-Ausgabe:
fast_trunc_one, generiert:
_fast_trunc_one:
LFB0:
.cfi_startproc
movl 4(%esp), %eax
movl $150, %ecx
movl %eax, %edx
andl $8388607, %edx
sarl $23, %eax
orl $8388608, %edx
andl $255, %eax
subl %eax, %ecx
movl %edx, %eax
sarl %cl, %eax
testl %ecx, %ecx
js L5
rep
ret
.p2align 4,,7
L5:
negl %ecx
movl %edx, %eax
sall %cl, %eax
ret
.cfi_endproc
fast_trunc_two, generiert:
_fast_trunc_two:
LFB1:
.cfi_startproc
pushl %ebx
.cfi_def_cfa_offset 8
.cfi_offset 3, -8
movl 8(%esp), %eax
movl $150, %ecx
movl %eax, %ebx
movl %eax, %edx
sarl $23, %ebx
andl $8388607, %edx
andl $255, %ebx
orl $8388608, %edx
andl $-2147483648, %eax
subl %ebx, %ecx
js L9
sarl %cl, %edx
movl %eax, %ecx
negl %ecx
xorl %ecx, %edx
addl %edx, %eax
popl %ebx
.cfi_remember_state
.cfi_def_cfa_offset 4
.cfi_restore 3
ret
.p2align 4,,7
L9:
.cfi_restore_state
negl %ecx
sall %cl, %edx
movl %eax, %ecx
negl %ecx
xorl %ecx, %edx
addl %edx, %eax
popl %ebx
.cfi_restore 3
.cfi_def_cfa_offset 4
ret
.cfi_endproc
Das ist ein extremer Unterschied. Dies zeigt sich auch im Profil, fast_trunc_one
ist rund 30% schneller als fast_trunc_two
. Nun meine Frage: Was verursacht das?
-S -O3 -da -fdump-tree-all
. Dadurch werden viele Schnappschüsse der Zwischendarstellung erstellt. Gehen Sie sie nebeneinander durch (sie sind nummeriert), und Sie sollten im ersten Fall in der Lage sein, die fehlende Optimierung zu finden.int
inunsigned int
und prüfen Sie, ob der Unterschied verschwindet.(r + shifted) ^ sign
nicht derselbe wier + (shifted ^ sign)
. Ich denke, das verwirrt den Optimierer? FWIW, MSVC 2010 (16.00.40219.01) erstellt Einträge, die fast identisch sind: gist.github.com/2430454Antworten:
Aktualisiert, um mit der Bearbeitung des OP zu synchronisieren
Durch das Basteln mit dem Code konnte ich sehen, wie GCC den ersten Fall optimiert.
Bevor wir verstehen können, warum sie so unterschiedlich sind, müssen wir zuerst verstehen, wie GCC optimiert
fast_trunc_one()
.Ob Sie es glauben oder nicht,
fast_trunc_one()
wird darauf optimiert:Dies ergibt genau die gleiche Baugruppe wie die Originalregisternamen
fast_trunc_one()
und alles.Beachten Sie, dass
xor
die Assembly für keine s enthältfast_trunc_one()
. Das hat es für mich verraten.Wie?
Schritt 1:
sign = -sign
Schauen wir uns zunächst die
sign
Variable an. Dasign = i & 0x80000000;
gibt es nur zwei mögliche Werte,sign
die annehmen können:sign = 0
sign = 0x80000000
Erkennen Sie nun, dass in beiden Fällen ,
sign == -sign
. Wenn ich also den Originalcode in folgenden Code ändere:Es wird genau die gleiche Baugruppe wie das Original hergestellt
fast_trunc_one()
. Ich werde Ihnen die Baugruppe ersparen, aber sie ist identisch - Registernamen und alles.Schritt 2: Mathematische Reduktion:
x + (y ^ x) = y
sign
kann nur einen von zwei Werten annehmen,0
oder0x80000000
.x = 0
, dannx + (y ^ x) = y
gilt Triviales.0x80000000
ist dasselbe. Es dreht das Vorzeichenbit um. Daherx + (y ^ x) = y
gilt auch wannx = 0x80000000
.Daher
x + (y ^ x)
reduziert sich aufy
. Und der Code vereinfacht dies:Auch dies wird zu genau derselben Assembly kompiliert - Registernamen und alle.
Diese obige Version reduziert sich schließlich auf Folgendes:
Das ist ziemlich genau das, was GCC in der Assembly generiert.
Warum optimiert der Compiler nicht
fast_trunc_two()
auf dasselbe?Der Schlüssel dazu
fast_trunc_one()
ist diex + (y ^ x) = y
Optimierung. Infast_trunc_two()
demx + (y ^ x)
Ausdruck wird über den Zweig geteilt.Ich vermute, dass dies ausreichen könnte, um GCC zu verwirren, diese Optimierung nicht vorzunehmen. (Es müsste das
^ -sign
aus dem Ast herausheben undr + sign
am Ende in das zusammenführen.)Dies erzeugt beispielsweise dieselbe Baugruppe wie
fast_trunc_one()
:quelle
Dies ist die Natur von Compilern. Die Annahme, dass sie den schnellsten oder besten Weg gehen, ist ziemlich falsch. Jeder, der impliziert, dass Sie nichts an Ihrem Code tun müssen, um ihn zu optimieren, weil "moderne Compiler" die Lücke ausfüllen, den besten Job machen, den schnellsten Code erstellen usw. Eigentlich habe ich gesehen, dass gcc von 3.x auf schlechter wird 4.x mindestens am Arm. 4.x hat zu diesem Zeitpunkt möglicherweise bis zu 3.x eingeholt, aber schon früh wurde langsamerer Code erzeugt. Mit etwas Übung können Sie lernen, wie Sie Ihren Code schreiben, damit der Compiler nicht so hart arbeiten muss und dadurch konsistentere und erwartete Ergebnisse erzielt.
Der Fehler hier sind Ihre Erwartungen an das, was produziert wird, nicht an das, was tatsächlich produziert wurde. Wenn Sie möchten, dass der Compiler dieselbe Ausgabe generiert, geben Sie dieselbe Eingabe ein. Nicht mathematisch gleich, nicht irgendwie gleich, aber tatsächlich gleich, keine unterschiedlichen Pfade, keine gemeinsamen oder verteilten Operationen von einer Version zur anderen. Dies ist eine gute Übung, um zu verstehen, wie Sie Ihren Code schreiben und was Compiler damit machen. Machen Sie nicht den Fehler anzunehmen, dass eine Version von gcc für ein Prozessorziel eines Tages ein bestimmtes Ergebnis liefert, dass dies eine Regel für alle Compiler und den gesamten Code ist. Sie müssen viele Compiler und viele Ziele verwenden, um ein Gefühl dafür zu bekommen, was los ist.
gcc ist ziemlich böse, ich lade Sie ein, hinter den Vorhang zu schauen, sich die Eingeweide von gcc anzusehen, zu versuchen, ein Ziel hinzuzufügen oder selbst etwas zu modifizieren. Es wird kaum durch Klebeband und Draht zusammengehalten. Eine zusätzliche Codezeile, die an kritischen Stellen hinzugefügt oder entfernt wird und zusammenbricht. Die Tatsache, dass überhaupt brauchbarer Code erzeugt wurde, ist etwas, über das man sich freuen kann, anstatt sich Gedanken darüber zu machen, warum er andere Erwartungen nicht erfüllt hat.
Hast du dir angesehen, welche verschiedenen Versionen von gcc produzieren? 3.x und 4.x insbesondere 4.5 vs 4.6 vs 4.7, etc? und für verschiedene Zielprozessoren, x86, Arm, Mips usw. oder verschiedene Varianten von x86, wenn dies der native Compiler ist, den Sie verwenden, 32-Bit vs 64-Bit usw.? Und dann llvm (Klirren) für verschiedene Ziele?
Mystical hat in dem Denkprozess, der erforderlich ist, um das Problem der Analyse / Optimierung des Codes zu lösen, hervorragende Arbeit geleistet und erwartet, dass ein Compiler irgendetwas davon entwickelt, was von keinem "modernen Compiler" erwartet wird.
Code dieser Form, ohne auf die mathematischen Eigenschaften einzugehen
führt den Compiler zu A: Implementieren Sie ihn in dieser Form, führen Sie das Wenn-Dann-Sonst aus und konvergieren Sie dann auf gemeinsamem Code, um den Vorgang abzuschließen und zurückzukehren. oder B: Speichern Sie einen Zweig, da dies das Ende der Funktion ist. Auch nicht mit r verwenden oder speichern.
Dann können Sie darauf eingehen, wie Mystical hervorhob, dass die Vorzeichenvariable für den geschriebenen Code alle zusammen verschwindet. Ich würde nicht erwarten, dass der Compiler sieht, dass die Vorzeichenvariable verschwindet, also hätten Sie das selbst tun sollen und den Compiler nicht gezwungen, es herauszufinden.
Dies ist eine perfekte Gelegenheit, um in den gcc-Quellcode einzutauchen. Anscheinend haben Sie einen Fall gefunden, in dem der Optimierer in einem Fall eine Sache gesehen hat, in einem anderen Fall eine andere. Machen Sie dann den nächsten Schritt und prüfen Sie, ob Sie gcc nicht dazu bringen können, diesen Fall zu sehen. Jede Optimierung ist da, weil eine Einzelperson oder Gruppe die Optimierung erkannt und absichtlich dort platziert hat. Damit diese Optimierung vorhanden ist und jedes Mal funktioniert, wenn jemand sie dort ablegen muss (und sie dann testen und dann in der Zukunft warten muss).
Gehen Sie auf keinen Fall davon aus, dass weniger Code schneller und mehr Code langsamer ist. Es ist sehr einfach, Beispiele dafür zu erstellen und zu finden, die nicht zutreffen. Es kann häufig vorkommen, dass weniger Code schneller ist als mehr Code. Wie ich von Anfang an gezeigt habe, können Sie jedoch mehr Code erstellen, um in diesem Fall Verzweigungen oder Schleifen usw. zu speichern, und das Nettoergebnis ist schnellerer Code.
Unter dem Strich haben Sie einem Compiler eine andere Quelle zugeführt und die gleichen Ergebnisse erwartet. Das Problem ist nicht die Compilerausgabe, sondern die Erwartungen des Benutzers. Für einen bestimmten Compiler und Prozessor ist es ziemlich einfach, das Hinzufügen einer Codezeile zu demonstrieren, wodurch eine ganze Funktion erheblich langsamer wird. Zum Beispiel, warum ändert sich a = b + 2; zu a = b + c + 2; Ursache _fill_in_the_blank_compiler_name_ radikal anderen und langsameren Code generieren? Die Antwort war natürlich, dass dem Compiler ein anderer Code für die Eingabe zugeführt wurde, sodass es für den Compiler vollkommen gültig ist, unterschiedliche Ausgaben zu generieren. (Noch besser ist es, wenn Sie zwei nicht zusammenhängende Codezeilen austauschen und die Ausgabe dramatisch ändern.) Es gibt keine erwartete Beziehung zwischen der Komplexität und Größe der Eingabe und der Komplexität und Größe der Ausgabe.
Es produzierte irgendwo zwischen 60-100 Assembler-Linien. Es rollte die Schleife ab. Ich habe die Zeilen nicht gezählt, wenn Sie darüber nachdenken, muss es hinzufügen, das Ergebnis in die Eingabe des Funktionsaufrufs kopieren, den Funktionsaufruf ausführen, mindestens drei Operationen. Abhängig vom Ziel sind dies wahrscheinlich mindestens 60 Anweisungen, 80, wenn vier pro Schleife, 100, wenn fünf pro Schleife usw.
quelle
Mysticial hat bereits eine großartige Erklärung gegeben, aber ich dachte, ich würde hinzufügen, FWIW, dass es wirklich nichts Grundlegendes gibt, warum ein Compiler die Optimierung für das eine und nicht für das andere vornehmen würde.
Der
clang
Compiler von LLVM gibt beispielsweise für beide Funktionen denselben Code an (mit Ausnahme des Funktionsnamens) und gibt Folgendes an:Dieser Code ist nicht so kurz wie die erste gcc-Version aus dem OP, aber nicht so lang wie die zweite.
Code von einem anderen Compiler (den ich nicht nennen werde), der für x86_64 kompiliert wird, erzeugt dies für beide Funktionen:
Das ist insofern faszinierend, als es beide Seiten des berechnet
if
und dann am Ende einen bedingten Zug verwendet, um den richtigen auszuwählen.Der Open64-Compiler erzeugt Folgendes:
und ähnlicher, aber nicht identischer Code für
fast_trunc_two
.Wenn es um Optimierung geht, ist es eine Lotterie - es ist, was es ist ... Es ist nicht immer einfach zu wissen, warum Ihr Code auf eine bestimmte Weise kompiliert wird.
quelle
icc
. Ich habe nur die 32-Bit-Variante, aber sie erzeugt Code, der diesem sehr ähnlich ist.