Ich habe über div
und mul
Montagevorgä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.s
Datei 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?
-3689348814741910323
wird inCCCCCCCCCCCCCCCD
eineuint64_t
oder nur etwa (2 ^ 64) * 4/5 umgewandelt.div
Anweisung an-O0
. (cc @ clifford)Antworten:
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 Befehlendiv
ist nur die Standardmethode von GCC, um durch Konstanten zu dividieren. Es erfordert keine betriebsübergreifende Optimierung und ändert auch beim Debuggen nichts. (Die Verwendung-Os
für kleine Codegrößen führt jedoch dazu, dass GCC verwendetdiv
wird.) Die Verwendung einer multiplikativen Inversen anstelle einer Division ist wie die Verwendunglea
anstelle vonmul
undadd
Infolgedessen sehen Sie
div
oder nuridiv
in 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 .
quelle
-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.)-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 aufgenommenDas 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
CCCCCCCCCCCCCCCD
in 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ünftel0.110011001100
wiederholt 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) oder0.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 kann0.111111111111...
, das offensichtlich gleich 1 ist, genauso wie die0.9999999...
Dezimalzahl gleich eins ist. Daher wissen wir , dassx + x/4 = 1
, so5x/4 = 1
,x=4/5
. Dies wird dannCCCCCCCCCCCCD
zum Runden als hexadezimal dargestellt (da die Binärziffer hinter der zuletzt vorhandenen a wäre1
).quelle
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.
quelle
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:
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:
quelle
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.
quelle