Wie funktioniert Rusts 128-Bit-Ganzzahl "i128" auf einem 64-Bit-System?

128

Rust hat 128-Bit-Ganzzahlen, diese werden mit dem Datentyp i128(und u128für vorzeichenlose Ints) bezeichnet:

let a: i128 = 170141183460469231731687303715884105727;

Wie macht Rust diese? i128 Werte auf einem 64-Bit-System funktionieren? zB wie rechnet man damit?

Da der Wert meines Wissens nicht in ein Register einer x86-64-CPU passen kann, verwendet der Compiler irgendwie 2 Register für einen i128Wert? Oder verwenden sie stattdessen eine große Ganzzahlstruktur, um sie darzustellen?

Ruohola
quelle
54
Wie funktioniert eine zweistellige Ganzzahl, wenn Sie nur 10 Finger haben?
Jörg W Mittag
27
@JorgWMittag: Ah - der alte Trick "zweistellige Zahl mit nur zehn Fingern". Heh-heh. Dachten Sie, Sie könnten mich mit diesem alten täuschen, was? Nun, mein Freund, wie jeder Zweitklässler Ihnen sagen könnte - DAS sind die Zehen! ( Mit bitterer Entschuldigung an Peter Sellers ... und Lady Lytton :-)
Bob Jarvis - Wiedereinsetzung Monica
1
FWIW Die meisten x86-Computer verfügen über spezielle 128-Bit- oder größere Register für SIMD-Vorgänge. Siehe en.wikipedia.org/wiki/Streaming_SIMD_Extensions Bearbeiten: Ich habe @ eckes 'Kommentar irgendwie verpasst
Ryan1729
4
@ JörgWMittag Nein, Informatiker zählen binär, indem sie einzelne Finger senken oder strecken. Und jetzt, 132 Jahre alt, gehe ich nach Hause ;-D
Marco13

Antworten:

141

Alle Integer-Typen von Rust werden zu LLVM-Integer kompiliert . Die abstrakte LLVM-Maschine erlaubt Ganzzahlen mit einer beliebigen Bitbreite von 1 bis 2 ^ 23 - 1. * LLVM- Anweisungen arbeiten normalerweise mit Ganzzahlen jeder Größe.

Offensichtlich gibt es nicht viele 8388607-Bit-Architekturen. Wenn der Code zu nativem Maschinencode kompiliert wird, muss LLVM entscheiden, wie er implementiert werden soll. Die Semantik einer abstrakten Anweisung wie addwird von LLVM selbst definiert. In der Regel werden abstrakte Anweisungen mit einer einzelnen Anweisung, die im nativen Code entspricht, zu dieser nativen Anweisung kompiliert, während solche, die nicht emuliert werden, möglicherweise mit mehreren nativen Anweisungen. Die Antwort von mcarton zeigt, wie LLVM sowohl native als auch emulierte Anweisungen kompiliert.

(Dies gilt nicht nur für Ganzzahlen, die größer sind, als der native Computer unterstützen kann, sondern auch für solche, die kleiner sind. Beispielsweise unterstützen moderne Architekturen möglicherweise keine native 8-Bit-Arithmetik, sodass eine addAnweisung für zwei i8Sekunden emuliert werden kann mit einer breiteren Anweisung werden die zusätzlichen Bits verworfen.)

Verwendet der Compiler irgendwie 2 Register für einen i128Wert? Oder verwenden sie eine große Ganzzahlstruktur, um sie darzustellen?

Auf der Ebene von LLVM IR lautet die Antwort weder: i128Passt in ein einzelnes Register, genau wie jeder andere einwertige Typ . Auf der anderen Seite gibt es nach der Übersetzung in Maschinencode keinen wirklichen Unterschied zwischen den beiden, da Strukturen wie Ganzzahlen in Register zerlegt werden können. Beim Rechnen ist es jedoch ziemlich sicher, dass LLVM das Ganze nur in zwei Register lädt.


* Allerdings sind nicht alle LLVM-Backends gleich. Diese Antwort bezieht sich auf x86-64. Ich verstehe, dass die Backend-Unterstützung für Größen größer als 128 und Nicht-Zweierpotenzen unvollständig ist (was teilweise erklären kann, warum Rust nur 8-, 16-, 32-, 64- und 128-Bit-Ganzzahlen verfügbar macht). Laut est31 auf Reddit implementiert rustc 128-Bit-Ganzzahlen in Software, wenn es auf ein Backend abzielt, das sie nicht nativ unterstützt.

trentcl
quelle
1
Huh, ich frage mich, warum es 2 ^ 23 statt der typischeren 2 ^ 32 ist (nun, allgemein ausgedrückt, wie oft diese Zahlen erscheinen, nicht in Bezug auf die maximale Bitbreite von Ganzzahlen, die von Compiler-Backends unterstützt werden ...)
Fund Monicas Klage
26
@NicHartley Einige der LLVM-Basisklassen haben ein Feld, in dem Unterklassen Daten speichern können. Für die TypeKlasse bedeutet dies, dass 8 Bit zum Speichern des Typs (Funktion, Block, Ganzzahl, ...) und 24 Bit für Unterklassendaten vorhanden sind. Die IntegerTypeKlasse verwendet dann diese 24 Bit, um die Größe zu speichern, sodass Instanzen ordentlich in 32 Bit passen!
Todd Sewell
56

Der Compiler speichert diese in mehreren Registern und verwendet bei Bedarf mehrere Anweisungen, um diese Werte zu rechnen. Die meisten ISAs verfügen über eine Add-with-Carry-Anweisung wie x86,adc die es ziemlich effizient macht, Ganzzahlen-Add / Sub mit erweiterter Genauigkeit auszuführen .

Zum Beispiel gegeben

fn main() {
    let a = 42u128;
    let b = a + 1337;
}

Der Compiler generiert Folgendes, wenn er ohne Optimierung für x86-64 kompiliert:
(Kommentare von @PeterCordes hinzugefügt)

playground::main:
    sub rsp, 56
    mov qword ptr [rsp + 32], 0
    mov qword ptr [rsp + 24], 42         # store 128-bit 0:42 on the stack
                                         # little-endian = low half at lower address

    mov rax, qword ptr [rsp + 24]
    mov rcx, qword ptr [rsp + 32]        # reload it to registers

    add rax, 1337                        # add 1337 to the low half
    adc rcx, 0                           # propagate carry to the high half. 1337u128 >> 64 = 0

    setb    dl                           # save carry-out (setb is an alias for setc)
    mov rsi, rax
    test    dl, 1                        # check carry-out (to detect overflow)
    mov qword ptr [rsp + 16], rax        # store the low half result
    mov qword ptr [rsp + 8], rsi         # store another copy of the low half
    mov qword ptr [rsp], rcx             # store the high half
                             # These are temporary copies of the halves; probably the high half at lower address isn't intentional
    jne .LBB8_2                       # jump if 128-bit add overflowed (to another not-shown block of code after the ret, I think)

    mov rax, qword ptr [rsp + 16]
    mov qword ptr [rsp + 40], rax     # copy low half to RSP+40
    mov rcx, qword ptr [rsp]
    mov qword ptr [rsp + 48], rcx     # copy high half to RSP+48
                  # This is the actual b, in normal little-endian order, forming a u128 at RSP+40
    add rsp, 56
    ret                               # with retval in EAX/RAX = low half result

wo Sie sehen können, dass der Wert 42in raxund gespeichert ist rcx.

(Anmerkung des Herausgebers: x86-64 C-Aufrufkonventionen geben in RDX: RAX 128-Bit-Ganzzahlen zurück. Dies maingibt jedoch überhaupt keinen Wert zurück. Das redundante Kopieren erfolgt ausschließlich durch Deaktivieren der Optimierung, und Rust prüft tatsächlich, ob das Debug überläuft Modus.)

Zum Vergleich hier der ASM für Rust 64-Bit-Ganzzahlen auf x86-64, bei dem kein Add-with-Carry erforderlich ist, sondern nur ein einzelnes Register oder ein Stack-Slot für jeden Wert.

playground::main:
    sub rsp, 24
    mov qword ptr [rsp + 8], 42           # store
    mov rax, qword ptr [rsp + 8]          # reload
    add rax, 1337                         # add
    setb    cl
    test    cl, 1                         # check for carry-out (overflow)
    mov qword ptr [rsp], rax              # store the result
    jne .LBB8_2                           # branch on non-zero carry-out

    mov rax, qword ptr [rsp]              # reload the result
    mov qword ptr [rsp + 16], rax         # and copy it (to b)
    add rsp, 24
    ret

.LBB8_2:
    call panic function because of integer overflow

Das Setb / Test ist immer noch völlig redundant: jc(Sprung, wenn CF = 1) würde gut funktionieren.

Wenn die Optimierung aktiviert ist, prüft der Rust-Compiler nicht, ob ein Überlauf +vorliegt .wrapping_add().

mcarton
quelle
4
@Anush Nein, rax / rsp / ... sind 64-Bit-Register. Jede 128-Bit-Nummer wird in zwei Registern / Speicherstellen gespeichert, was zu den beiden 64-Bit-Additionen führt.
ManfP
5
@Anush: Nein, es werden nur so viele Anweisungen verwendet, weil es mit deaktivierter Optimierung kompiliert wurde. Sie würden viel einfacheren Code sehen (wie nur add / adc), wenn Sie eine Funktion kompilieren würden, die zwei u128Argumente benötigt und einen Wert zurückgibt (wie diesen godbolt.org/z/6JBza0 ), anstatt die Optimierung zu deaktivieren, um den Compiler daran zu hindern Konstante Ausbreitung auf Argumenten mit konstanter Kompilierungszeit.
Peter Cordes
3
Der @ CAD97-Freigabemodus verwendet eine Umbrucharithmetik, prüft jedoch nicht wie der Debug-Modus auf Überlauf und Panik. Dieses Verhalten wurde von RFC 560 definiert . Es ist nicht UB.
Trentcl
3
@PeterCordes: Insbesondere gibt die Sprache Rust an, dass der Überlauf nicht angegeben ist, und rustc (der einzige Compiler) gibt zwei Verhaltensweisen an, aus denen Sie auswählen können: Panic oder Wrap. Im Idealfall wird standardmäßig Panik verwendet. In der Praxis ist aufgrund der suboptimalen Codegenerierung im Release-Modus die Standardeinstellung Wrap, und ein langfristiges Ziel besteht darin, auf Panik umzusteigen, wenn (wenn überhaupt) die Codegenerierung für den Mainstream-Einsatz "gut genug" ist. Außerdem unterstützen alle Rust-Integraltypen benannte Operationen, um ein Verhalten auszuwählen: Aktiviert, Umbrechen, Sättigen, ..., sodass Sie das ausgewählte Verhalten pro Operation überschreiben können.
Matthieu M.
1
@MatthieuM.: Ja, ich liebe das Umbrechen vs. Überprüfen vs. Sättigen Add / Sub / Shift / was auch immer Methoden für primitive Typen. UB hat so viel besser als Cs Wrapping ohne Vorzeichen, dass Sie gezwungen sind, basierend darauf zu wählen. Auf jeden Fall könnten einige ISAs eine effiziente Unterstützung für Panic bieten, z. B. ein Sticky Flag, das Sie nach einer ganzen Abfolge von Vorgängen überprüfen können. (Im Gegensatz zu OF oder CF von x86, die mit 0 oder 1 überschrieben werden.) ZB die von Agner Fog vorgeschlagene ForwardCom ISA ( agner.org/optimize/blog/read.php?i=421#478 ) Die Rust-Quelle hat es nicht getan. : /
Peter Cordes
30

Ja, genauso wie 64-Bit-Ganzzahlen auf 32-Bit-Computern oder 32-Bit-Ganzzahlen auf 16-Bit-Computern oder sogar 16- und 32-Bit-Ganzzahlen auf 8-Bit-Computern behandelt wurden (gilt immer noch für Mikrocontroller! ). Ja, Sie speichern die Nummer in zwei Registern oder Speicherorten oder was auch immer (es spielt keine Rolle). Addition und Subtraktion sind trivial, nehmen zwei Anweisungen und verwenden das Übertragsflag. Die Multiplikation erfordert drei Multiplikationen und einige Additionen (es ist üblich, dass 64-Bit-Chips bereits eine 64x64-> 128-Multiplikationsoperation haben, die an zwei Register ausgegeben wird). Division ... erfordert eine Unterroutine und ist ziemlich langsam (außer in einigen Fällen, in denen die Division durch eine Konstante in eine Verschiebung oder eine Multiplikation umgewandelt werden kann), funktioniert aber trotzdem. Bitweise und / oder / xor müssen lediglich auf der oberen und unteren Hälfte getrennt ausgeführt werden. Verschiebungen können durch Drehen und Maskieren erreicht werden. Und das deckt so ziemlich alles ab.

Hobbs
quelle
26

Um vielleicht ein klareres Beispiel für x86_64 zu liefern, kompiliert mit dem -OFlag die Funktion

pub fn leet(a : i128) -> i128 {
    a + 1337
}

kompiliert zu

example::leet:
  mov rdx, rsi
  mov rax, rdi
  add rax, 1337
  adc rdx, 0
  ret

(Mein ursprünglicher Beitrag hatte u128eher als den i128, nach dem Sie gefragt haben. Die Funktion kompiliert in beiden Fällen denselben Code. Dies ist eine gute Demonstration, dass signierte und nicht signierte Additionen auf einer modernen CPU identisch sind.)

Die andere Auflistung erzeugte nicht optimierten Code. Es ist sicher, in einem Debugger durchzugehen, da dadurch sichergestellt wird, dass Sie überall einen Haltepunkt setzen und den Status einer Variablen in einer beliebigen Zeile des Programms überprüfen können. Es ist langsamer und schwerer zu lesen. Die optimierte Version kommt dem Code, der tatsächlich in der Produktion ausgeführt wird, viel näher.

Der Parameter adieser Funktion wird in einem Paar von 64-Bit-Registern, rsi: rdi, übergeben. Das Ergebnis wird in einem anderen Registerpaar, rdx: rax, zurückgegeben. Die ersten beiden Codezeilen initialisieren die Summe auf a.

Die dritte Zeile fügt dem niedrigen Wort der Eingabe 1337 hinzu. Wenn dies überläuft, trägt es die 1 im Übertragsflag der CPU. Die vierte Zeile addiert Null zum oberen Wort der Eingabe - plus die 1, wenn es übertragen wurde.

Sie können sich dies als einfaches Hinzufügen einer einstelligen Nummer zu einer zweistelligen Nummer vorstellen

  a  b
+ 0  7
______
 

aber in der Basis 18.446.744.073.709.551.616. Sie fügen immer noch zuerst die niedrigste „Ziffer“ hinzu, möglicherweise mit einer 1 in die nächste Spalte, und fügen dann die nächste Ziffer plus den Übertrag hinzu. Die Subtraktion ist sehr ähnlich.

Die Multiplikation muss die Identität (2⁶⁴a + b) (2⁶⁴c + d) = 2¹²⁸ac + 2⁶⁴ (ad + bc) + bd verwenden, wobei jede dieser Multiplikationen die obere Hälfte des Produkts in einem Register und die untere Hälfte des Produkts in zurückgibt Ein weiterer. Einige dieser Begriffe werden gelöscht, da Bits über dem 128. nicht in ein passen u128und verworfen werden. Dies erfordert jedoch eine Reihe von Maschinenanweisungen. Die Aufteilung erfolgt ebenfalls in mehreren Schritten. Für einen vorzeichenbehafteten Wert müssten Multiplikation und Division zusätzlich die Vorzeichen der Operanden und das Ergebnis konvertieren. Diese Operationen sind überhaupt nicht sehr effizient.

Bei anderen Architekturen wird es einfacher oder schwieriger. RISC-V definiert eine 128-Bit-Befehlssatzerweiterung, obwohl meines Wissens niemand sie in Silizium implementiert hat. Ohne diese Erweiterung empfiehlt das RISC-V-Architekturhandbuch eine bedingte Verzweigung:addi t0, t1, +imm; blt t0, t1, overflow

SPARC hat Steuercodes wie die Steuerflags von x86, aber Sie müssen eine spezielle Anweisung verwenden, add,ccum sie festzulegen. Bei MIPS hingegen müssen Sie überprüfen, ob die Summe zweier vorzeichenloser Ganzzahlen streng kleiner als einer der Operanden ist. Wenn ja, lief die Zugabe über. Zumindest können Sie ein anderes Register ohne bedingte Verzweigung auf den Wert des Übertragsbits setzen.

Davislor
quelle
1
letzter Absatz: Um zu erkennen, welche von zwei vorzeichenlosen Zahlen größer ist, indem Sie das hohe Bit eines subErgebnisses betrachten, benötigen Sie ein n+1Bit-Unterergebnis für nBiteingaben. Das heißt, Sie müssen sich die Ausführung ansehen, nicht das Vorzeichenbit mit dem Ergebnis gleicher Breite. Aus diesem Grund basieren x86-Verzweigungsbedingungen ohne Vorzeichen auf CF (Bit 64 oder 32 des vollständigen logischen Ergebnisses) und nicht auf SF (Bit 63 oder 31).
Peter Cordes
1
Der Ansatz von re: divmod: AArch64 besteht darin, eine Division und eine Anweisung bereitzustellen, die eine Ganzzahl ausführt x - (a*b), wobei der Rest aus Dividende, Quotient und Divisor berechnet wird. (Dies ist auch für konstante Teiler nützlich, die eine multiplikative Inverse für den Teilungsteil verwenden). Ich hatte nicht über ISAs gelesen, die div + mod-Anweisungen zu einer einzigen divmod-Operation zusammenführen. das ist ordentlich.
Peter Cordes
1
re: flags: ja, eine Flag-Ausgabe ist eine zweite Ausgabe, die OoO exec + register-renaming irgendwie verarbeiten muss. x86-CPUs verarbeiten dies, indem sie einige zusätzliche Bits mit dem ganzzahligen Ergebnis behalten, auf dem der FLAGS-Wert basiert. Daher werden wahrscheinlich ZF, SF und PF bei Bedarf im laufenden Betrieb generiert. Ich denke, es gibt ein Intel-Patent dafür. Dies reduziert die Anzahl der Ausgänge, die separat zurückverfolgt werden müssen, auf 1. (In Intel-CPUs kann kein UOP jemals mehr als ein Integer-Register schreiben; z. B. mul r642 Uops, wobei das zweite die hohe RDX-Hälfte schreibt).
Peter Cordes
1
Für eine effiziente erweiterte Genauigkeit sind Flags jedoch sehr gut. Das Hauptproblem besteht darin, dass das Register für die superskalare Ausführung in der Reihenfolge umbenannt wird. Flags sind eine WAW-Gefahr (Schreiben nach Schreiben). Add-with-Carry-Anweisungen sind natürlich 3 Eingänge, und das ist auch ein erhebliches Problem, das verfolgt werden muss. Intel vor Broadwell entschlüsselt adc, sbbund cmovauf jeweils 2 Uops. (Haswell führte 3-Input-Uops für FMA ein, Broadwell erweiterte dies auf Integer.)
Peter Cordes
1
RISC-ISAs mit Flags machen das Setzen von Flags normalerweise optional und werden durch ein zusätzliches Bit gesteuert. zB ARM und SPARC sind so. PowerPC wie gewohnt macht alles komplizierter: Es verfügt über 8 Bedingungscode-Register (zusammengepackt in ein 32-Bit-Register zum Speichern / Wiederherstellen), sodass Sie mit cc0 oder cc7 oder was auch immer vergleichen können. Und dann UND oder ODER Bedingungscodes zusammen! Verzweigungs- und cmov-Anweisungen können auswählen, welches CR-Register gelesen werden soll. Auf diese Weise können Sie mehrere Flaggen-Dep-Ketten gleichzeitig im Flug haben, z. B. x86 ADCX / ADOX. alanclements.org/power%20pc.html
Peter Cordes