Warum verwendet GCC bei der Implementierung der Ganzzahldivision die Multiplikation mit einer seltsamen Zahl?

227

Ich habe über divund mulMontagevorgänge gelesen und mich entschlossen, sie in Aktion zu sehen, indem ich ein einfaches Programm in C schrieb:

Dateidivision.c

#include <stdlib.h>
#include <stdio.h>

int main()
{
    size_t i = 9;
    size_t j = i / 5;
    printf("%zu\n",j);
    return 0;
}

Und dann Assembler-Code generieren mit:

gcc -S division.c -O0 -masm=intel

Wenn Sie sich die generierte division.sDatei ansehen, enthält sie keine Div-Operationen! Stattdessen macht es eine Art schwarze Magie mit Bitverschiebung und magischen Zahlen. Hier ist ein Code-Snippet, das berechnet i/5:

mov     rax, QWORD PTR [rbp-16]   ; Move i (=9) to RAX
movabs  rdx, -3689348814741910323 ; Move some magic number to RDX (?)
mul     rdx                       ; Multiply 9 by magic number
mov     rax, rdx                  ; Take only the upper 64 bits of the result
shr     rax, 2                    ; Shift these bits 2 places to the right (?)
mov     QWORD PTR [rbp-8], rax    ; Magically, RAX contains 9/5=1 now, 
                                  ; so we can assign it to j

Was ist denn hier los? Warum verwendet GCC div überhaupt nicht? Wie erzeugt es diese magische Zahl und warum funktioniert alles?

Qiubit
quelle
29
gcc optimiert die Division durch Konstanten, versucht die Division durch 2,3,4,5,6,7,8 und Sie werden höchstwahrscheinlich für jeden Fall einen sehr unterschiedlichen Code sehen.
Jabberwocky
28
Hinweis: Die magische Zahl -3689348814741910323wird in CCCCCCCCCCCCCCCDeine uint64_toder nur etwa (2 ^ 64) * 4/5 umgewandelt.
chux
32
@qiubit: Der Compiler generiert auch keinen perversen ineffizienten Code, nur weil die Optimierung deaktiviert ist. Eine triviale "Optimierung", die keine Neuordnung des Codes oder Eliminierung von Variablen beinhaltet, wird unabhängig davon durchgeführt. Im Wesentlichen wird eine einzelne Quellanweisung isoliert in den effizientesten Code für diese Operation übersetzt. Die Compileroptimierung berücksichtigt den umgebenden Code und nicht nur die einzelne Anweisung.
Clifford
20
Lesen Sie diesen fantastischen Artikel: Labor of Division
Jester
9
Einige Compiler tatsächlich wird perversely ineffizienten Code generieren , da diese Optimierung deaktiviert ist. Insbesondere werden sie dies tun, um das Debuggen zu vereinfachen, beispielsweise um Haltepunkte für einzelne Codezeilen festzulegen. GCC ist in der Tat insofern eher ungewöhnlich, als es keinen echten "Keine Optimierungen" -Modus gibt, da viele seiner Optimierungen konstitutiv aktiviert sind. Dies ist ein Beispiel dafür, wo Sie dies mit GCC sehen können. Clang, auf der anderen Seite, und MSVC, wird strahlen eine divAnweisung an -O0. (cc @ clifford)
Cody Gray

Antworten:

169

Die Ganzzahldivision ist eine der langsamsten arithmetischen Operationen, die Sie auf einem modernen Prozessor ausführen können, mit einer Latenz von bis zu Dutzenden von Zyklen und einem schlechten Durchsatz. (Informationen zu x86 finden Sie in den Anleitungstabellen und im Microarch-Handbuch von Agner Fog .)

Wenn Sie den Divisor im Voraus kennen, können Sie die Division vermeiden, indem Sie sie durch eine Reihe anderer Operationen (Multiplikationen, Additionen und Verschiebungen) ersetzen, die den gleichen Effekt haben. Selbst wenn mehrere Operationen erforderlich sind, ist es oft noch viel schneller als die Ganzzahldivision selbst.

Das Implementieren des C- /Operators auf diese Weise anstelle einer Sequenz mit mehreren Befehlen divist nur die Standardmethode von GCC, um durch Konstanten zu dividieren. Es erfordert keine betriebsübergreifende Optimierung und ändert auch beim Debuggen nichts. (Die Verwendung -Osfür kleine Codegrößen führt jedoch dazu, dass GCC verwendet divwird.) Die Verwendung einer multiplikativen Inversen anstelle einer Division ist wie die Verwendung leaanstelle von mulundadd

Infolgedessen sehen Sie divoder nur idivin der Ausgabe, wenn der Divisor zur Kompilierungszeit nicht bekannt ist.

Informationen dazu, wie der Compiler diese Sequenzen generiert, sowie Code, mit dem Sie sie selbst generieren können (mit ziemlicher Sicherheit nicht erforderlich, es sei denn, Sie arbeiten mit einem Braindead-Compiler), finden Sie unter libdivide .

Sneftel
quelle
5
Ich bin mir nicht sicher, ob es fair ist, FP- und Integer-Operationen in einem Geschwindigkeitsvergleich zusammenzufassen, @fuz. Vielleicht sollte Sneftel sagen, dass Division die langsamste Ganzzahloperation ist, die Sie auf einem modernen Prozessor ausführen können? Außerdem wurden in Kommentaren einige Links zu weiteren Erklärungen dieser "Magie" bereitgestellt. Halten Sie es für angemessen, sie in Ihrer Antwort für die Sichtbarkeit zu sammeln? 1 , 2 , 3
Cody Grey
1
Da die Reihenfolge der Operationen funktional identisch ist, ist dies auch bei immer eine Voraussetzung -O3. Der Compiler muss Code erstellen, der für alle möglichen Eingabewerte korrekte Ergebnisse liefert. Dies ändert sich nur für Gleitkommazahlen mit -ffast-math, und AFAIK gibt es keine "gefährlichen" Ganzzahloptimierungen. (Wenn die Optimierung aktiviert ist, kann der Compiler möglicherweise etwas über den möglichen Wertebereich beweisen, wodurch er etwas verwenden kann, das beispielsweise nur für nicht negativ vorzeichenbehaftete Ganzzahlen funktioniert.)
Peter Cordes
6
Die eigentliche Antwort ist, dass gcc -O0 immer noch Code durch interne Darstellungen umwandelt, um C in Maschinencode umzuwandeln . Es kommt nur vor, dass modulare multiplikative Inversen standardmäßig auch bei -O0(aber nicht bei -Os) aktiviert sind . Andere Compiler (wie clang) verwenden DIV für Konstanten ohne Potenz von 2 bei -O0. Verwandte: Ich glaube, ich habe einen Absatz darüber in meine handgeschriebene Antwort auf eine Collatz-Vermutung aufgenommen
Peter Cordes
6
@PeterCordes Und ja, ich denke, GCC (und viele andere Compiler) haben vergessen, eine gute Begründung dafür zu finden, "welche Arten von Optimierungen gelten, wenn die Optimierung deaktiviert ist". Nachdem ich den größten Teil eines Tages damit verbracht habe, einen obskuren Codegen-Fehler aufzuspüren, bin ich im Moment etwas verärgert darüber.
Sneftel
9
@Sneftel: Das liegt wahrscheinlich nur daran, dass die Anzahl der Anwendungsentwickler, die sich aktiv bei den Compiler-Entwicklern darüber beschweren , dass ihr Code schneller als erwartet ausgeführt wird, relativ gering ist.
Dan04
121

Das Teilen durch 5 entspricht dem Multiplizieren von 1/5, was wiederum dem Multiplizieren mit 4/5 und dem Verschieben von 2 Bits nach rechts entspricht. Der betreffende Wert ist CCCCCCCCCCCCCCCDin hexadezimal angegeben. Dies ist die binäre Darstellung von 4/5, wenn sie nach einem hexadezimalen Punkt steht (dh die Binärzahl für vier Fünftel 0.110011001100wiederholt sich - siehe unten, warum). Ich denke, Sie können es von hier nehmen! Möglicherweise möchten Sie die Festkomma-Arithmetik überprüfen (beachten Sie jedoch, dass sie am Ende auf eine Ganzzahl gerundet ist.

Die Multiplikation ist schneller als die Division, und wenn der Divisor fest ist, ist dies eine schnellere Route.

Unter Reziproke Multiplikation, einem Tutorial, finden Sie eine ausführliche Beschreibung der Funktionsweise, die in Bezug auf den Festkomma erklärt wird. Es zeigt, wie der Algorithmus zum Finden des Kehrwerts funktioniert und wie mit vorzeichenbehafteter Division und Modulo umgegangen wird.

Lassen Sie uns für eine Minute überlegen, warum 0.CCCCCCCC...(hex) oder 0.110011001100...binär 4/5 ist. Teilen Sie die binäre Darstellung durch 4 (2 Stellen nach rechts verschieben), und wir erhalten, 0.001100110011...welche durch triviale Prüfung das Original hinzugefügt werden kann 0.111111111111..., das offensichtlich gleich 1 ist, genauso wie die 0.9999999...Dezimalzahl gleich eins ist. Daher wissen wir , dass x + x/4 = 1, so 5x/4 = 1, x=4/5. Dies wird dann CCCCCCCCCCCCDzum Runden als hexadezimal dargestellt (da die Binärziffer hinter der zuletzt vorhandenen a wäre 1).

abligh
quelle
2
@ user2357112 zögern Sie nicht, Ihre eigene Antwort zu posten, aber ich stimme nicht zu. Sie können sich die Multiplikation als eine 64,0-Bit-mit-0,64-Bit-Multiplikation vorstellen, die eine 128-Bit-Festkomma-Antwort ergibt, von der die niedrigsten 64-Bit verworfen werden, und dann eine Division durch 4 (wie ich im ersten Absatz hervorhole). Möglicherweise können Sie eine alternative modulare arithmetische Antwort finden, die die Bitbewegungen gleich gut erklärt, aber ich bin mir ziemlich sicher, dass dies als Erklärung funktioniert.
Abligh
6
Der Wert ist tatsächlich "CCCCCCCCCCCCCCCD". Das letzte D ist wichtig. Es stellt sicher, dass beim Abschneiden des Ergebnisses exakte Divisionen mit der richtigen Antwort herauskommen.
Plugwash
4
Keine Ursache. Ich habe nicht gesehen, dass sie die oberen 64 Bits des 128-Bit-Multiplikationsergebnisses verwenden. Es ist nicht etwas, was man in den meisten Sprachen tun kann, also habe ich anfangs nicht bemerkt, dass es passiert. Diese Antwort würde durch eine explizite Erwähnung erheblich verbessert, wie die Verwendung der oberen 64 Bit des 128-Bit-Ergebnisses der Multiplikation mit einer Festkommazahl und der Abrundung entspricht. (Außerdem wäre es gut zu erklären, warum es 4/5 statt 1/5 sein muss und warum wir 4/5 nach oben statt nach unten runden müssen.)
user2357112 unterstützt Monica
2
Sie müssten herausfinden, wie groß ein Fehler ist, um eine Division um 5 über eine Rundungsgrenze nach oben zu werfen, und dies dann mit dem Worst-Case-Fehler in Ihrer Berechnung vergleichen. Vermutlich haben die gcc-Entwickler dies getan und sind zu dem Schluss gekommen, dass immer die richtigen Ergebnisse erzielt werden.
Plugwash
3
Eigentlich müssen Sie wahrscheinlich nur die 5 höchstmöglichen Eingabewerte überprüfen, wenn diese richtig runden, sollte auch alles andere.
Plugwash
60

Im Allgemeinen ist die Multiplikation viel schneller als die Division. Wenn wir also mit der Multiplikation mit dem Kehrwert davonkommen, können wir stattdessen die Division durch eine Konstante erheblich beschleunigen

Eine Falte ist, dass wir den Kehrwert nicht genau darstellen können (es sei denn, die Division war durch eine Zweierpotenz, aber in diesem Fall können wir die Division normalerweise nur in eine Bitverschiebung umwandeln). Um korrekte Antworten zu gewährleisten, müssen wir darauf achten, dass der Fehler in unserem Kehrwert keine Fehler in unserem Endergebnis verursacht.

-3689348814741910323 ist 0xCCCCCCCCCCCCCCCD, was einem Wert von etwas mehr als 4/5 entspricht, ausgedrückt in 0,64 Fixpunkten.

Wenn wir eine 64-Bit-Ganzzahl mit einer 0,64-Festkommazahl multiplizieren, erhalten wir ein 64,64-Ergebnis. Wir kürzen den Wert auf eine 64-Bit-Ganzzahl (runden ihn effektiv gegen Null) und führen dann eine weitere Verschiebung durch, die durch vier dividiert und erneut abgeschnitten wird. Wenn wir uns die Bitebene ansehen, ist klar, dass wir beide Kürzungen als eine einzige Kürzung behandeln können.

Dies gibt uns eindeutig mindestens eine Annäherung an die Division durch 5, aber gibt es uns eine genaue Antwort, die korrekt auf Null gerundet ist?

Um eine genaue Antwort zu erhalten, muss der Fehler klein genug sein, um die Antwort nicht über eine Rundungsgrenze zu verschieben.

Die genaue Antwort auf eine Division durch 5 hat immer einen Bruchteil von 0, 1/5, 2/5, 3/5 oder 4/5. Daher wird ein positiver Fehler von weniger als 1/5 im multiplizierten und verschobenen Ergebnis das Ergebnis niemals über eine Rundungsgrenze verschieben.

Der Fehler in unserer Konstante ist (1/5) * 2 -64 . Der Wert von i ist kleiner als 2 64, so dass der Fehler nach dem Multiplizieren kleiner als 1/5 ist. Nach der Division durch 4 ist der Fehler kleiner als (1/5) * 2 −2 .

(1/5) * 2 −2 <1/5, daher ist die Antwort immer gleichbedeutend mit einer exakten Division und einer Rundung gegen Null.


Leider funktioniert dies nicht bei allen Teilern.

Wenn wir versuchen, 4/7 als 0,64-Fixpunktzahl mit Abrundung von Null darzustellen, erhalten wir einen Fehler von (6/7) * 2 -64 . Nach dem Multiplizieren mit einem i-Wert von knapp 2 64 erhalten wir einen Fehler von knapp 6/7 und nach dem Teilen durch vier einen Fehler von knapp 1,5 / 7, der größer als 1/7 ist.

Um die Division durch 7 korrekt zu implementieren, müssen wir mit einer Festpunktzahl von 0,65 multiplizieren. Wir können dies implementieren, indem wir mit den unteren 64 Bits unserer Festkommazahl multiplizieren, dann die ursprüngliche Zahl addieren (dies kann in das Übertragsbit überlaufen) und dann eine Durchdrehung durchführen.

Plugwash
quelle
8
Diese Antwort verwandelte modulare multiplikative Umkehrungen von "Mathematik, die komplizierter aussieht, als ich mir die Zeit nehmen möchte" in etwas Sinnvolles. +1 für die leicht verständliche Version. Ich musste nie etwas anderes tun, als nur vom Compiler generierte Konstanten zu verwenden, also habe ich nur andere Artikel überflogen, in denen die Mathematik erklärt wurde.
Peter Cordes
2
Ich sehe im Code überhaupt nichts mit modularer Arithmetik zu tun. Keine Ahnung, woher einige andere Kommentatoren das beziehen.
Plugwash
3
Es ist Modulo 2 ^ n, wie alle Ganzzahlmathematik in einem Register. en.wikipedia.org/wiki/…
Peter Cordes
4
@ PeterCordes modulare multiplikative Inversen werden für die exakte Division verwendet, afaik sie sind nicht nützlich für die allgemeine Division
Harold
4
@ PeterCordes Multiplikation mit Festkomma reziprok? Ich weiß nicht, wie es jeder nennt, aber ich würde es wahrscheinlich so nennen, es ist ziemlich beschreibend
Harold
12

Hier ist ein Link zu einem Dokument eines Algorithmus, der die Werte und den Code erzeugt, die ich mit Visual Studio sehe (in den meisten Fällen) und von denen ich annehme, dass sie in GCC immer noch zur Division einer variablen Ganzzahl durch eine konstante Ganzzahl verwendet werden.

http://gmplib.org/~tege/divcnst-pldi94.pdf

In dem Artikel hat ein U-Wort N Bits, ein U-Wort hat 2 N Bits, n = Zähler = Dividende, d = Nenner = Divisor, ℓ wird anfänglich auf Ceil gesetzt (log2 (d)), shpre ist Pre-Shift (wird vor dem Multiplizieren verwendet ) = e = Anzahl der nachgestellten Nullbits in d, shpost ist post-shift (wird nach Multiplikation verwendet), prec ist präzise = N - e = N - shpre. Ziel ist es, die Berechnung von n / d mithilfe von Pre-Shift, Multiplikation und Post-Shift zu optimieren.

Scrollen Sie nach unten zu Abbildung 6.2, in der definiert ist, wie ein udword-Multiplikator (maximale Größe ist N + 1 Bit) generiert wird, der Vorgang jedoch nicht klar erläutert wird. Ich werde das unten erklären.

Abbildung 4.2 und Abbildung 6.2 zeigen, wie der Multiplikator für die meisten Teiler auf ein N-Bit- oder weniger-Multiplikator reduziert werden kann. Gleichung 4.5 erklärt, wie die Formel für den Umgang mit N + 1-Bit-Multiplikatoren in Abbildung 4.1 und 4.2 abgeleitet wurde.

Bei modernen X86- und anderen Prozessoren ist die Multiplikationszeit festgelegt, sodass die Vorverschiebung bei diesen Prozessoren nicht hilfreich ist, der Multiplikator jedoch von N + 1 Bit auf N Bit reduziert werden kann. Ich weiß nicht, ob GCC oder Visual Studio die Vorverschiebung für X86-Ziele eliminiert haben.

Zurück zu Abbildung 6.2. Der Zähler (Dividende) für mlow und mhigh kann nur dann größer als ein udword sein, wenn der Nenner (Divisor)> 2 ^ (N-1) (wenn ℓ == N => mlow = 2 ^ (2N)) ist, in diesem Fall der Ein optimierter Ersatz für n / d ist ein Vergleich (wenn n> = d, q = 1, sonst q = 0), sodass kein Multiplikator generiert wird. Die Anfangswerte von mlow und mhigh sind N + 1 Bit, und zwei udword / uword-Teilungen können verwendet werden, um jeden N + 1-Bit-Wert (mlow oder mhigh) zu erzeugen. Verwenden von X86 im 64-Bit-Modus als Beispiel:

; upper 8 bytes of dividend = 2^(ℓ) = (upper part of 2^(N+ℓ))
; lower 8 bytes of dividend for mlow  = 0
; lower 8 bytes of dividend for mhigh = 2^(N+ℓ-prec) = 2^(ℓ+shpre) = 2^(ℓ+e)
dividend  dq    2 dup(?)        ;16 byte dividend
divisor   dq    1 dup(?)        ; 8 byte divisor

; ...
        mov     rcx,divisor
        mov     rdx,0
        mov     rax,dividend+8     ;upper 8 bytes of dividend
        div     rcx                ;after div, rax == 1
        mov     rax,dividend       ;lower 8 bytes of dividend
        div     rcx
        mov     rdx,1              ;rdx:rax = N+1 bit value = 65 bit value

Sie können dies mit GCC testen. Sie haben bereits gesehen, wie mit j = i / 5 umgegangen wird. Schauen Sie sich an, wie mit j = i / 7 umgegangen wird (dies sollte der N + 1-Bit-Multiplikatorfall sein).

Bei den meisten aktuellen Prozessoren hat Multiplizieren ein festes Timing, sodass keine Vorverschiebung erforderlich ist. Für X86 ist das Endergebnis eine Zwei-Befehlsfolge für die meisten Teiler und eine Fünf-Befehlsfolge für Teiler wie 7 (um einen N + 1-Bit-Multiplikator zu emulieren, wie in Gleichung 4.5 und Abbildung 4.2 der PDF-Datei gezeigt). Beispiel X86-64 Code:

;       rax = dividend, rbx = 64 bit (or less) multiplier, rcx = post shift count
;       two instruction sequence for most divisors:

        mul     rbx                     ;rdx = upper 64 bits of product
        shr     rdx,cl                  ;rdx = quotient
;
;       five instruction sequence for divisors like 7
;       to emulate 65 bit multiplier (rbx = lower 64 bits of multiplier)

        mul     rbx                     ;rdx = upper 64 bits of product
        sub     rbx,rdx                 ;rbx -= rdx
        shr     rbx,1                   ;rbx >>= 1
        add     rdx,rbx                 ;rdx = upper 64 bits of corrected product
        shr     rdx,cl                  ;rdx = quotient
;       ...
rcgldr
quelle
In diesem Dokument wird die Implementierung in gcc beschrieben. Ich denke, es ist eine sichere Annahme, dass immer noch dasselbe Algo verwendet wird.
Peter Cordes
In diesem Artikel aus dem Jahr 1994 wird die Implementierung in gcc beschrieben. Daher hatte gcc Zeit, seinen Algorithmus zu aktualisieren. Nur für den Fall, dass andere nicht die Zeit haben, zu überprüfen, was die 94 in dieser URL bedeutet.
Ed Grimm
0

Ich werde aus einem etwas anderen Blickwinkel antworten: Weil es erlaubt ist, es zu tun.

C und C ++ werden gegen eine abstrakte Maschine definiert. Der Compiler wandelt dieses Programm in Bezug auf die abstrakte Maschine nach der Als-ob- Regel in eine konkrete Maschine um.

  • Der Compiler darf JEDE Änderung vornehmen, solange er das von der abstrakten Maschine angegebene beobachtbare Verhalten nicht ändert. Es besteht keine vernünftige Erwartung, dass der Compiler Ihren Code auf möglichst einfache Weise transformiert (selbst wenn viele C-Programmierer dies annehmen). Dies geschieht normalerweise, weil der Compiler die Leistung im Vergleich zum einfachen Ansatz optimieren möchte (wie in den anderen Antworten ausführlich erläutert).
  • Wenn der Compiler unter keinen Umständen ein korrektes Programm für etwas "optimiert", das ein anderes beobachtbares Verhalten aufweist, ist dies ein Compiler-Fehler.
  • Jedes undefinierte Verhalten in unserem Code (signierter Ganzzahlüberlauf ist ein klassisches Beispiel) und dieser Vertrag ist ungültig.
dmeister
quelle