Frage Warum verwendet GCC die Multiplikation mit einer seltsamen Zahl bei der Implementierung einer ganzzahligen Division?


Ich habe gelesen div und mul Montageoperationen, und ich beschloss, sie in Aktion zu sehen, indem ich ein einfaches Programm in C schrieb:

Datei division.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 generieren Assembler-Code mit:

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

Aber betrachtet erzeugt division.s Datei, es enthält keine Div-Operationen! Stattdessen macht es eine Art schwarze Magie mit Bitverschiebungen 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 benutzt GCC überhaupt kein div? Wie generiert es diese magische Zahl und warum funktioniert alles?


170
2017-12-16 11:59


Ursprung


Antworten:


Die Integer-Division ist eine der langsamsten arithmetischen Operationen, die Sie auf einem modernen Prozessor durchführen können, mit einer Latenz von bis zu mehreren Dutzend Zyklen und einem schlechten Durchsatz. (Für x86, siehe Agner Fogs Instruktionstabellen und Microarch Guide).

Wenn Sie den Divisor im Voraus kennen, können Sie die Division vermeiden, indem Sie ihn durch eine Reihe anderer Operationen (Multiplikationen, Additionen und Verschiebungen) ersetzen, die die gleiche Wirkung haben. Selbst wenn mehrere Operationen benötigt werden, ist es oft noch viel schneller als die Ganzzahl-Division selbst.

Implementierung des C / Operator auf diese Weise statt mit einer Multi-Befehl-Sequenz mit div ist nur die Standardmethode von GCC, die Division durch Konstanten zu machen. Es erfordert keine übergreifende Optimierung und ändert auch nichts beim Debuggen. (Verwendung von -Os Für kleine Code-Größe wird GCC verwendet divaber.) Verwenden eines multiplikativen Inversen anstelle von Division ist wie Verwenden lea Anstatt von mul und add

Als Ergebnis neigen Sie nur dazu, zu sehen div oder idiv in der Ausgabe, wenn der Divisor zur Kompilierungszeit nicht bekannt ist.

Informationen darüber, wie der Compiler diese Sequenzen generiert, sowie Code, mit dem Sie diese für sich selbst generieren können (fast sicher unnötig, es sei denn, Sie arbeiten mit einem Braindead-Compiler), siehe libdivide.


133
2017-12-16 12:09



Teilen um 5 ist das gleiche wie Multiplizieren von 1/5, was wieder das Gleiche ist wie Multiplizieren mit 4/5 und Verschieben von 2 Bits nach rechts. Der betreffende Wert ist CCCCCCCCCCCCD in hex, was die binäre Darstellung von 4/5 ist, wenn sie nach einem hexadezimalen Punkt gesetzt ist (d. h. die Binärzahl für vier Fünftel ist 0.110011001100 wiederkehrend - siehe unten für warum). Ich denke du kannst es von hier aus nehmen! Vielleicht möchten Sie auschecken Festpunktarithmetik (obwohl es am Ende auf eine ganze Zahl gerundet wird.

Warum ist Multiplikation schneller als Division, und wenn der Divisor fixiert ist, ist dies eine schnellere Route.

Sehen Gegenseitige Multiplikation, ein Tutorial für eine detaillierte Beschreibung, wie es funktioniert, erklärt in Bezug auf Festpunkt. Es zeigt, wie der Algorithmus zum Auffinden des Reziproken funktioniert und wie mit der unterzeichneten Division und Modulo umzugehen ist.

Lassen Sie uns kurz überlegen, warum 0.CCCCCCCC... (hex) oder 0.110011001100... Binär ist 4/5. Teilen Sie die binäre Darstellung durch 4 (Verschiebung um 2 Stellen), und wir werden erhalten 0.001100110011...was durch triviale Inspektion hinzugefügt werden kann, um das Original zu bekommen 0.111111111111..., die offensichtlich gleich 1 ist, auf die gleiche Weise 0.9999999... in dezimal ist gleich eins. Deshalb wissen wir das x + x/4 = 1, damit 5x/4 = 1, x=4/5. Dies wird dann als dargestellt CCCCCCCCCCCCD hex für die Rundung (da die binäre Zahl hinter der letzten vorhandenen wäre a 1).


94
2017-12-16 13:44



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

Eine Falte ist, dass wir das Reziproke nicht genau darstellen können (es sei denn, die Division wurde durch eine Zweierpotenz ausgeführt, aber in diesem Fall können wir die Division normalerweise einfach in eine Bitverschiebung umwandeln). Um korrekte Antworten zu erhalten, müssen wir also darauf achten, dass der Fehler in unserem Gegenstück keine Fehler in unserem Endergebnis verursacht.

-3689348814741910323 ist 0xCCCCCCCCCCCCCCCD, was ein Wert von etwas über 4/5 ist, ausgedrückt in 0,64 Fixpunkt.

Wenn wir eine 64-Bit-Ganzzahl mit einer 0,64-Festkommazahl multiplizieren, erhalten wir ein Ergebnis von 64,64. Wir schneiden den Wert auf eine 64-Bit-Ganzzahl ab (runden ihn praktisch gegen Null) und führen dann eine weitere Verschiebung durch, die durch vier teilt und erneut schneidet. Wenn wir uns die Bit-Ebene anschauen, ist klar, dass wir beide Kürzungen als eine einzige Kürzung behandeln können.

Dies gibt uns eindeutig eine Annäherung der Teilung um 5, aber gibt es uns eine genaue Antwort korrekt auf Null gerundet?

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

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 in dem multiplizierten und verschobenen Ergebnis niemals das Ergebnis über eine Rundungsgrenze hinaus drücken.

Der Fehler in unserer Konstante ist (1/5) * 2-64. Der Wert von ich ist weniger als 264 Der Fehler nach dem Multiplizieren ist also kleiner als 1/5. Nach der Division durch 4 ist der Fehler kleiner als (1/5) * 2-2.

(1/5) * 2-2 <1/5, so wird die Antwort immer gleich einer genauen Division und Rundung gegen Null sein.


Leider funktioniert das nicht für alle Teiler.

Wenn wir versuchen, 4/7 als 0.64 Festkommazahl mit Abrundung von Null zu repräsentieren, ergibt sich ein Fehler von (6/7) * 2-64. Nach Multiplikation mit einem i-Wert von knapp unter 264 wir haben einen Fehler knapp unter 6/7 und nach der Division durch vier ergibt sich ein Fehler von knapp 1,5 / 7, der größer als 1/7 ist.

Um Divison um 7 korrekt zu implementieren, müssen wir also mit einer Festkommazahl 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 Übertrags-Bit überlaufen), und dann eine Drehung durch Übertrag ausführen.


48
2017-12-16 21:04



Hier ist der Link zu einem Dokument eines Algorithmus, der die Werte und den Code erzeugt, den ich in Visual Studio sehe (in den meisten Fällen) und von dem ich annehme, dass er immer noch in GCC für die Division einer variablen Ganzzahl durch eine konstante Ganzzahl verwendet wird.

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

In dem Artikel hat ein Unwort N Bits, ein Unwort hat 2N Bits, n = Zähler, d = Nenner = Teiler, l wird anfänglich auf ceil gesetzt (log2 (d)), shpre ist Vorverschiebung (verwendet vor Multiplikation) = e = Anzahl der hinteren Null-Bits in d, shpost ist post-shift (wird nach multiply verwendet), prec ist precision = N - e = N - shpre. Ziel ist es, die Berechnung von n / d anhand einer Pre-Shift-, Multiply- und Post-Shift-Methode zu optimieren.

Scrollen Sie nach unten zu Abbildung 6.2, in der festgelegt ist, wie ein Ungültigkeitsmultiplikator (maximale Größe ist N + 1 Bit) generiert wird, aber den Prozess nicht eindeutig erklärt. Ich werde das unten erklären.

Abbildung 4.2 und Abbildung 6.2 zeigen, wie der Multiplikator für die meisten Teiler auf einen Multiplikator von N Bit oder weniger reduziert werden kann. Gleichung 4.5 erklärt, wie die Formel zur Behandlung von N + 1-Bit-Multiplikatoren in Abbildung 4.1 und 4.2 hergeleitet wurde.

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

; upper 8 bytes of numerator = 2^(ℓ) = (upper part of 2^(N+ℓ))
; lower 8 bytes of numerator for mlow  = 0
; lower 8 bytes of numerator for mhigh = 2^(N+ℓ-prec) = 2^(ℓ+shpre) = 2^(ℓ+e)
numerator dq    2 dup(?)        ;16 byte numerator
divisor   dq    1 dup(?)        ; 8 byte divisor
; ...
        mov     rcx,divisor
        mov     rdx,0
        mov     rax,numerator+8    ;upper 8 bytes of numerator
        div     rcx                ;after div, rax == 1
        mov     rax,numerator      ;lower 8 bytes of numerator
        div     rcx
        mov     rdx,1              ;rdx:rax = N+1 bit value = 65 bit value

Sie können dies mit GCC testen. Sie sehen bereits, wie j = i / 5 gehandhabt wird. Sehen Sie sich an, wie j = i / 7 gehandhabt wird (was der N + 1-Bit-Multiplikationsfall sein sollte).


9
2017-12-19 13:52