Teilen, fischen, schnell und vollständig

Die Division ist eine der teuersten Operationen in modernen Prozessoren. Sie müssen nicht weit gehen, um den Beweis zu erbringen: Agner Fog [ 1 ] sendet, dass auf Intel / AMD-Prozessoren die Latenz in 25 bis 119 Taktzyklen und der wechselseitige Durchsatz von 25 bis 120 leicht erreicht werden können. Übersetzt ins Russische - LANGSAM ! Trotzdem besteht die Möglichkeit, die Teilungsanweisung in Ihrem Code zu vermeiden. In diesem Artikel werde ich Ihnen erklären, wie es funktioniert, insbesondere bei modernen Compilern (die dies bereits seit 20 Jahren können), und ich werde auch erläutern, wie das gewonnene Wissen verwendet werden kann, um den Code besser, schneller und leistungsfähiger zu machen.

Eigentlich spreche ich von: Wenn der Divisor in der Kompilierungsphase bekannt ist, ist es möglich, die ganzzahlige Division durch Multiplikation und eine logische Verschiebung nach rechts zu ersetzen (und manchmal können Sie überhaupt darauf verzichten - ich spreche sicherlich über die Implementierung in der Programmiersprache). Es klingt sehr ermutigend: Der Betrieb der Ganzzahlmultiplikation und eine Verschiebung nach rechts durch beispielsweise Intel Haswell dauert nicht länger als 5 Taktzyklen. Es bleibt nur zu verstehen, wie zum Beispiel durch Ausführen einer Ganzzahldivision durch 10 das gleiche Ergebnis durch Ganzzahlmultiplikation und eine logische Verschiebung nach rechts erzielt werden kann. Die Antwort auf diese Frage liegt im Verständnis ... Fixpunktarithmetik (im Folgenden: FPA). Ein bisschen Grundlagen.

Bei Verwendung von FP wird der Exponent (Exponent 2 => die Position des Punkts in der binären Darstellung der Zahl) nicht in der Zahl gespeichert (im Gegensatz zur Gleitkomma-Arithmetik, siehe IEE754), sondern als vereinbarter Wert angesehen, der den Programmierern bekannt ist. Nur die Mantisse (was nach dem Dezimalpunkt kommt) bleibt erhalten. Ein Beispiel:

$$

$$0.1 = .0001 1001 1001 1001 (1001) ... FP, exp = 0$$

0.1 - in binärer Notation hat es eine 'unendliche Darstellung', die im obigen Beispiel durch Klammern angegeben ist - dieser Teil wird von Zeit zu Zeit wiederholt und folgt in binärer FP-Notation der Nummer 0.1 aufeinander.

Wenn wir im obigen Beispiel 16-Bit-Register zum Speichern von FP-Nummern verwenden, können wir die FP-Darstellung der Nummer 0.1 nicht in ein solches Register einpassen, ohne an Genauigkeit zu verlieren, und dies wirkt sich wiederum auf das Ergebnis aller weiteren Berechnungen aus, an denen der Wert dieses Registers beteiligt ist.

Angenommen, wir erhalten eine 16-Bit-Ganzzahl A und einen 16-Bit-Bruchteil von B. Das Produkt von A durch B ergibt eine Zahl mit 16 Bit im Ganzzahlteil und 16 Bit im Bruchteil. Um nur den ganzzahligen Teil zu erhalten, müssen Sie das Ergebnis natürlich um 16 Bit nach rechts verschieben.

Herzlichen Glückwunsch, die Einführung in die FPA ist beendet.

Wir bilden die folgende Hypothese: Um eine ganzzahlige Division mit 10 durchzuführen, müssen wir die teilbare Zahl mit der FP-Darstellung der Zahl 0,1 multiplizieren, den ganzzahligen Teil und die Materie im Hut nehmen ... Moment mal ... Aber wird das Ergebnis genau sein, genauer gesagt sein ganzzahliger Teil? - Wie wir uns erinnern, ist in unserem Gedächtnis immerhin nur eine ungefähre Version der Zahl 0.1 gespeichert. Im Folgenden habe ich drei verschiedene Darstellungen von 0,1 geschrieben: eine unendlich genaue Darstellung von 0,1, abgeschnitten nach dem 16. Bit ohne Rundung, eine Darstellung von 0,1 und abgeschnitten nach dem 16. Bit mit Aufrundung, eine Darstellung von 0,1.

$$

$$0001 \: 1001 \: 1001 \: 1001 \: | \: 1001 \: 1001 .... - unendlich \: Präzision \: \: \: \: \: \: \: \: \: \: \: \: \ : \: \: \: \: \: \: \: \: \: \: \: \\ 0001 \: 1001 \: 1001 \: 1001 \: | \: 0000 \: 0000 .... - Abschneiden \: ohne \: Rundung \\ 0001 \: 1001 \: 1001 \: 1010 \: | \: 0000 \: 0000 .... - Abschneiden \: mit \: Rundung \: up \:$$

Lassen Sie uns die Fehler beim Abschneiden von Darstellungen der Zahl 0.1 schätzen:

$$

$$unendlich \: Präzision - Abschneiden \: ohne \: Rundung = 0,6 * 2 ^ {- 16} \\ Abschneiden \: mit \: Rundung \: up - Unendlichkeit \: Präzision = 0,1 * 2 ^ {- 14}$$

Damit das Ergebnis der Multiplikation der ganzen Zahl A mit der Näherung von 0,1 den exakten ganzzahligen Teil ergibt, müssen wir:

$$

$$IntegerPart (A * 0.1) = IntegerPart (A * (0.1 + 0.1 * 2 ^ {- 14})),$$

entweder

$$

$$IntegerPart (A * 0.1) = IntegerPart (A * (0.1 + 0.6 * 2 ^ {- 16}))$$

Es ist bequemer, den ersten Ausdruck zu verwenden: wann $$$0.1 * 2 ^ {-14} * A <0.1$ Wir bekommen immer die Identität (aber wohlgemerkt, nicht alle Entscheidungen sind im Rahmen dieses Problems mehr als genug). Lösen bekommen wir $$$A <2 ^ {14}$ . Das heißt, wenn wir eine beliebige 14-Bit-Zahl A durch Abschneiden mit Aufrunden der Darstellung von 0,1 multiplizieren, erhalten wir immer den exakten ganzzahligen Teil, den wir erhalten würden, wenn wir unendlich genau 0,1 mit A multiplizieren würden. Konventionell multiplizieren wir jedoch 16-Bit-Zahlen, was bedeutet In unserem Fall ist die Antwort ungenau und wir können nicht auf eine einfache Multiplikation durch Abschneiden mit Rundung von 0,1 vertrauen. Wenn wir nun in der FP-Darstellung der Zahl 0,1 nicht 16 Bit, sondern beispielsweise 19, 20 speichern könnten, wäre alles in Ordnung. Und schließlich können wir!
Wir schauen uns die binäre Darstellung genau an - Abschneiden mit Aufrunden von 0,1: Die höchsten drei Bits sind Null, was bedeutet, dass sie keinen Beitrag zum Multiplikationsergebnis leisten (neue Bits).
Folglich können wir unsere Zahl um drei Bits nach links verschieben, aufrunden und nach der Multiplikation und logischen Verschiebung nach rechts zuerst um 16 und dann um 3 (dh im Allgemeinen jeweils um 19) den gewünschten, exakten ganzzahligen Teil erhalten . Der Beweis für die Richtigkeit einer solchen 19-Bit-Multiplikation ähnelt dem vorherigen, mit dem einzigen Unterschied, dass sie für 16-Bit-Zahlen korrekt funktioniert. Ähnliches gilt auch für Zahlen mit größerer Kapazität und nicht nur für die Division durch 10.

Früher habe ich geschrieben, dass man im Allgemeinen überhaupt auf eine Verschiebung verzichten kann und sich auf die Multiplikation beschränkt. Wie? Assembler x86 / x64 auf der Trommel:
In modernen Prozessoren gibt es einen MUL-Befehl (es gibt auch Analoga von IMUL, MULX - BMI2), der mit einem beispielsweise 32/64-Bit-Parameter eine 64/128-Bit-Multiplikation durchführen kann und das Ergebnis in Teilen in zwei Registern (hohe 32/64-Bit) speichert bzw. jünger):

MUL RCX ;  RCX  RAX,   (128 )   RDX:RAX 

Lassen Sie eine ganze Zahl von 62-Bit A im RCX-Register speichern, und lassen Sie die 64-Bit-FA-Darstellung, die mit Aufrunden der Zahl 0,1 abgeschnitten wird, im RAX-Register speichern (beachten Sie, dass es keine Linksverschiebungen gibt). Nach Abschluss der 64-Bit-Multiplikation erhalten wir, dass die höchsten 64 Bit des Ergebnisses im RDX-Register gespeichert sind, genauer gesagt im ganzzahligen Teil, der für 62-Bit-Zahlen genau ist. Das heißt, eine Verschiebung nach rechts (SHR, SHRX) ist nicht erforderlich. Das Vorhandensein einer solchen Verschiebung lädt die Pipeline des Prozessors, unabhängig davon, ob sie OOOE unterstützt oder nicht: Zumindest gibt es eine zusätzliche Abhängigkeit in der wahrscheinlich bereits langen Kette solcher Abhängigkeiten (auch als Abhängigkeitskette bezeichnet). Und hier ist es sehr wichtig zu erwähnen, dass moderne Compiler, die einen Ausdruck der Form some_integer / 10 sehen, automatisch Assembler-Code für den gesamten Bereich teilbarer Zahlen generieren. Das heißt, wenn Sie wissen, dass Sie immer 53-Bit-Zahlen haben (genau so war es in meiner Aufgabe), erhalten Sie immer noch die zusätzliche Schichtanweisung. Aber jetzt, da Sie verstehen, wie es funktioniert, können Sie die Division leicht durch Multiplikation ersetzen, ohne sich auf die Gnade des Compilers verlassen zu müssen. Übrigens wird das Abrufen der hohen Bits eines 64-Bit-Produkts in C ++ - Code durch etwas wie mulh implementiert, das gemäß dem Asm-Code den Zeilen der obigen Anweisung {I} MUL {X} entsprechen sollte.

Vielleicht verbessert sich mit dem Aufkommen von Verträgen (in C ++ 20 warten wir nicht) die Situation, und in einigen Fällen können wir dem Auto vertrauen! Obwohl dies C ++ ist, ist der Programmierer hier für alles verantwortlich - nicht anders.

Die oben beschriebene Argumentation gilt für alle Teiler von Konstanten. Nachfolgend finden Sie eine Liste nützlicher Links:

[1] https://www.agner.org/optimize/instruction_tables.pdf
[2] Steiler als Agner Fogh
[3] Telegrammkanal mit nützlichen Informationen zu Optimierungen für Intel / AMD / ARM
[4] Über die vollständige Aufteilung, jedoch auf Englisch