Rust ma 128-bitowe liczby całkowite, które są oznaczone typem danych i128
(i u128
dla liczb całkowitych bez znaku):
let a: i128 = 170141183460469231731687303715884105727;
Jak Rust sprawia, że te i128
wartości działają w systemie 64-bitowym; np. jak to robi na nich arytmetykę?
Ponieważ o ile wiem, wartość nie mieści się w jednym rejestrze procesora x86-64, czy kompilator w jakiś sposób używa 2 rejestrów dla jednej i128
wartości? A może zamiast tego używają jakiejś dużej struktury całkowitej do ich reprezentacji?
Odpowiedzi:
Wszystkie typy całkowite Rusta są kompilowane do liczb całkowitych LLVM . Maszyna abstrakcyjna LLVM dopuszcza liczby całkowite o dowolnej szerokości bitowej od 1 do 2 ^ 23 - 1. * Instrukcje LLVM zwykle działają na liczbach całkowitych o dowolnej wielkości.
Oczywiście nie ma wielu 8388607-bitowych architektur, więc kiedy kod jest kompilowany do natywnego kodu maszynowego, LLVM musi zdecydować, jak go zaimplementować. Semantyka abstrakcyjnych instrukcji, takich jak,
add
jest definiowana przez sam LLVM. Zwykle abstrakcyjne instrukcje, które mają odpowiednik pojedynczej instrukcji w kodzie natywnym, zostaną skompilowane do tej instrukcji natywnej, podczas gdy te, które nie są emulowane, prawdopodobnie z wieloma instrukcjami natywnymi. Odpowiedź mcarton pokazuje, jak LLVM kompiluje zarówno natywne, jak i emulowane instrukcje.(Dotyczy to nie tylko liczb całkowitych, które są większe niż może obsługiwać maszyna natywna, ale także tych, które są mniejsze. Na przykład nowoczesne architektury mogą nie obsługiwać natywnej arytmetyki 8-bitowej, więc
add
instrukcja na dwóchi8
s może być emulowana z szerszą instrukcją, dodatkowe bity zostały odrzucone.)Na poziomie LLVM IR odpowiedź nie brzmi:
i128
pasuje do jednego rejestru, tak jak każdy inny typ jednowartościowy . Z drugiej strony, po przetłumaczeniu na kod maszynowy, tak naprawdę nie ma między nimi różnicy, ponieważ struktury mogą być rozłożone na rejestry, tak jak liczby całkowite. Jednak podczas wykonywania arytmetyki można się założyć, że LLVM załaduje całość do dwóch rejestrów.* Jednak nie wszystkie backendy LLVM są sobie równe. Ta odpowiedź dotyczy x86-64. Rozumiem, że obsługa zaplecza dla rozmiarów większych niż 128 i innych niż potęgi dwóch jest nierówna (co może częściowo wyjaśniać, dlaczego Rust eksponuje tylko 8-, 16-, 32-, 64- i 128-bitowe liczby całkowite). Według est31 na Reddit , rustc implementuje 128-bitowe liczby całkowite w oprogramowaniu, gdy jest ukierunkowany na zaplecze, które nie obsługuje ich natywnie.
źródło
Type
klasy oznacza to, że istnieje 8 bitów do zapisania tego typu (funkcja, blok, liczba całkowita, ...) i 24 bity dla danych podklasy. NastępnieIntegerType
klasa wykorzystuje te 24 bity do przechowywania rozmiaru, umożliwiając dokładne dopasowanie instancji do 32 bitów!Kompilator zapisze je w wielu rejestrach i użyje wielu instrukcji do wykonania arytmetyki na tych wartościach, jeśli to konieczne. Większość ISA ma instrukcje dodawania z przenoszeniem, takie jak x86,
adc
co sprawia, że wykonywanie add / sub o rozszerzonej precyzji liczb całkowitych jest dość wydajne.Na przykład podane
fn main() { let a = 42u128; let b = a + 1337; }
kompilator generuje następujące dane podczas kompilacji dla x86-64 bez optymalizacji:
(komentarze dodane przez @PeterCordes)
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
gdzie widać, że wartość
42
jest przechowywana wrax
ircx
.(uwaga redaktora: konwencje wywoływania x86-64 C zwracają 128-bitowe liczby całkowite w RDX: RAX. Ale to w
main
ogóle nie zwraca wartości. Całe nadmiarowe kopiowanie jest wyłącznie wynikiem wyłączenia optymalizacji, a Rust faktycznie sprawdza przepełnienie podczas debugowania tryb.)Dla porównania, oto asm dla 64-bitowych liczb całkowitych Rusta na x86-64, gdzie nie jest potrzebny żaden dodatek z przenoszeniem, tylko jeden rejestr lub miejsce na stos dla każdej wartości.
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
Setb / test jest nadal całkowicie redundantny:
jc
(skok, jeśli CF = 1) działałby dobrze.Po włączeniu optymalizacji kompilator Rust nie sprawdza przepełnienia, więc
+
działa tak jak.wrapping_add()
.źródło
u128
argumenty i zwracała wartość (jak ta godbolt.org/z/6JBza0 ), zamiast wyłączać optymalizację, aby zatrzymać działanie kompilatora stała propagacja na argumentach stałych w czasie kompilacji.Tak, tak samo jak 64-bitowe liczby całkowite na maszynach 32-bitowych, 32-bitowe liczby całkowite na maszynach 16-bitowych, a nawet 16- i 32-bitowe liczby całkowite na maszynach 8-bitowych (nadal stosowane do mikrokontrolerów! ). Tak, przechowujesz liczbę w dwóch rejestrach lub lokalizacjach pamięci, czy cokolwiek (to naprawdę nie ma znaczenia). Dodawanie i odejmowanie są trywialne, wymagają dwóch instrukcji i używają flagi przeniesienia. Mnożenie wymaga trzech mnożeń i pewnych dodatków (często 64-bitowe chipy mają już operację mnożenia 64x64-> 128, która wyprowadza do dwóch rejestrów). Dzielenie ... wymaga podprogramu i jest dość powolne (z wyjątkiem niektórych przypadków, gdy dzielenie przez stałą można przekształcić w przesunięcie lub mnożenie), ale nadal działa. Bitowo i / lub / xor wystarczy wykonać osobno na górnej i dolnej połowie. Przesunięcia można osiągnąć za pomocą rotacji i maskowania. I to prawie wszystko obejmuje.
źródło
Aby zapewnić być może jaśniejszy przykład, na platformie x86_64, skompilowanej z
-O
flagą, funkcjapub fn leet(a : i128) -> i128 { a + 1337 }
kompiluje się do
example::leet: mov rdx, rsi mov rax, rdi add rax, 1337 adc rdx, 0 ret
(Mój oryginalny post miał
u128
raczej niż teni128
, o który pytałeś. Funkcja kompiluje ten sam kod w obu przypadkach, dobra demonstracja, że dodawanie ze znakiem i bez znaku jest takie samo na nowoczesnym procesorze.)Druga lista wygenerowała niezoptymalizowany kod. Bezpiecznie jest przejść przez debuger, ponieważ zapewnia on możliwość umieszczenia punktu przerwania w dowolnym miejscu i sprawdzenia stanu dowolnej zmiennej w dowolnym wierszu programu. Czytanie jest wolniejsze i trudniejsze. Zoptymalizowana wersja jest znacznie bliższa kodowi, który faktycznie będzie działał w środowisku produkcyjnym.
Parametr
a
tej funkcji jest przekazywany w parze rejestrów 64-bitowych, rsi: rdi. Wynik jest zwracany w innej parze rejestrów, rdx: rax. Pierwsze dwa wiersze kodu inicjują sumę doa
.Trzecia linia dodaje 1337 do młodszego słowa wejścia. Jeśli to się przepełni, przenosi 1 we fladze przenoszenia procesora. Czwarta linia dodaje zero do starszego słowa wejścia - plus 1, jeśli zostało przeniesione.
Możesz o tym myśleć jako o prostym dodaniu liczby jednocyfrowej do liczby dwucyfrowej
a b + 0 7 ______
ale w bazie 18,446,744,073,709,551,616. Nadal dodajesz najpierw najniższą „cyfrę”, prawdopodobnie przenosząc 1 do następnej kolumny, a następnie dodajesz następną cyfrę plus przeniesienie. Odejmowanie jest bardzo podobne.
Mnożenie musi wykorzystywać tożsamość (2⁶⁴a + b) (2⁶⁴c + d) = 2¹²⁸ac + 2⁶⁴ (ad + bc) + bd, gdzie każde z tych mnożeń zwraca górną połowę iloczynu w jednym rejestrze i dolną połowę iloczynu w inne. Niektóre z tych terminów zostaną usunięte, ponieważ bity powyżej 128-go nie pasują do a
u128
i są odrzucane. Mimo to wymaga to wielu instrukcji maszynowych. Podział ma również kilka kroków. W przypadku wartości ze znakiem mnożenie i dzielenie musiałyby dodatkowo konwertować znaki operandów i wynik. Te operacje wcale nie są zbyt wydajne.Na innych architekturach staje się to łatwiejsze lub trudniejsze. RISC-V definiuje 128-bitowe rozszerzenie zestawu instrukcji, chociaż według mojej wiedzy nikt nie zaimplementował go w krzemie. Bez tego rozszerzenia podręcznik architektury RISC-V zaleca gałąź warunkową:
addi t0, t1, +imm; blt t0, t1, overflow
SPARC ma kody sterujące, takie jak flagi kontrolne x86, ale musisz użyć specjalnej instrukcji
add,cc
, aby je ustawić. Z drugiej strony MIPS wymaga sprawdzenia, czy suma dwóch liczb całkowitych bez znaku jest dokładnie mniejsza niż jeden z operandów. Jeśli tak, dodatek się przepełnił. Przynajmniej możesz ustawić inny rejestr na wartość przenoszonego bitu bez gałęzi warunkowej.źródło
sub
wyniku, potrzebujeszn+1
wynikun
bitowego dla danych wejściowych bitowych. tzn. musisz patrzeć na wykonanie, a nie na bit znaku wyniku o tej samej szerokości. Dlatego warunki rozgałęzienia bez znaku x86 są oparte na CF (bit 64 lub 32 pełnego wyniku logicznego), a nie SF (bit 63 lub 31).x - (a*b)
, obliczając resztę z dywidendy, ilorazu i dzielnika. (Jest to przydatne nawet w przypadku stałych dzielników przy użyciu multiplikatywnej odwrotności dla części dzielenia). Nie czytałem o ISA, które łączą instrukcje div + mod w jedną operację divmod; to jest fajne.mul r64
Wynosi 2 uops, a drugi zapisuje wyższą połowę RDX).adc
,sbb
orazcmov
do 2 UOPs każdy. (Haswell wprowadził 3-wejściowe Uops dla FMA, Broadwell rozszerzył to do liczby całkowitej.)