Jak działa 128-bitowa liczba całkowita Rusta „i128” w systemie 64-bitowym?

132

Rust ma 128-bitowe liczby całkowite, które są oznaczone typem danych i128(i u128dla liczb całkowitych bez znaku):

let a: i128 = 170141183460469231731687303715884105727;

Jak Rust sprawia, że ​​te i128wartoś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 i128wartości? A może zamiast tego używają jakiejś dużej struktury całkowitej do ich reprezentacji?

ruohola
źródło
56
Jak działa dwucyfrowa liczba całkowita, gdy masz tylko 10 palców?
Jörg W Mittag
27
@JorgWMittag: Ach - stara sztuczka „dwucyfrowa liczba z tylko dziesięcioma palcami”. Heh heh. Pomyślałem, że możesz mnie oszukać tym starym, co? Cóż, przyjacielu, jak mógłby ci powiedzieć każdy drugoklasista - po to są palce u nóg! ( Z żałosnymi przeprosinami dla Petera Sellersa ... i Lady Lytton :-)
Bob Jarvis - Przywróć Monikę
1
FWIW większość maszyn x86 ma specjalne 128-bitowe lub większe rejestry dla operacji SIMD. Zobacz en.wikipedia.org/wiki/Streaming_SIMD_Extensions Edytuj: Jakoś przegapiłem komentarz @ eckes
Ryan1729
4
@ JörgWMittag Nah, informatycy liczą binarnie, opuszczając lub wysuwając poszczególne palce. A teraz 132 wszyscy, jadę do domu ;-D
Marco

Odpowiedzi:

147

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, addjest 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 addinstrukcja na dwóch i8s może być emulowana z szerszą instrukcją, dodatkowe bity zostały odrzucone.)

Czy kompilator w jakiś sposób używa 2 rejestrów dla jednej i128wartości? A może używają jakiejś dużej struktury całkowitej do ich reprezentacji?

Na poziomie LLVM IR odpowiedź nie brzmi: i128pasuje 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.

trentcl
źródło
1
Huh, zastanawiam się, dlaczego to 2 ^ 23 zamiast bardziej typowego 2 ^ 32 (cóż, mówiąc ogólnie, pod względem tego, jak często te liczby się pojawiają, a nie w kategoriach maksymalnych szerokości bitowych liczb całkowitych obsługiwanych przez zaplecze kompilatora ...)
Fundacja Pozew Moniki
26
@NicHartley Niektóre z klas bazowych LLVM mają pole, w którym podklasy mogą przechowywać dane. W przypadku Typeklasy oznacza to, że istnieje 8 bitów do zapisania tego typu (funkcja, blok, liczba całkowita, ...) i 24 bity dla danych podklasy. Następnie IntegerTypeklasa wykorzystuje te 24 bity do przechowywania rozmiaru, umożliwiając dokładne dopasowanie instancji do 32 bitów!
Todd Sewell
58

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ść 42jest przechowywana w raxi rcx.

(uwaga redaktora: konwencje wywoływania x86-64 C zwracają 128-bitowe liczby całkowite w RDX: RAX. Ale to w mainogó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().

mcarton
źródło
4
@Anush Nie, rax / rsp / ... to rejestry 64-bitowe. Każda 128-bitowa liczba jest przechowywana w dwóch rejestrach / lokalizacjach pamięci, co powoduje dodanie dwóch 64-bitowych dodatków.
ManfP
5
@Anush: nie, po prostu używa tak wielu instrukcji, ponieważ jest skompilowany z wyłączoną optymalizacją. Zobaczyłbyś znacznie prostszy kod (jak tylko add / adc), gdybyś skompilował funkcję, która pobierała dwa u128argumenty 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.
Peter Cordes
3
@ CAD97 Tryb wydania wykorzystuje arytmetykę zawijania, ale nie sprawdza przepełnienia i paniki, jak robi to tryb debugowania. To zachowanie zostało zdefiniowane w dokumencie RFC 560 . To nie jest UB.
trentcl,
3
@PeterCordes: W szczególności Rust język określa, że ​​przepełnienie jest nieokreślone, a rustc (jedyny kompilator) określa dwa zachowania do wyboru: Panic lub Wrap. Idealnie byłoby, gdyby opcja Panic była używana domyślnie. W praktyce, ze względu na nieoptymalne generowanie kodu, w trybie wydania domyślnym jest Wrap, a długoterminowym celem jest przejście do Panic, gdy (jeśli w ogóle) generowanie kodu jest „wystarczająco dobre” do użytku głównego nurtu. Ponadto wszystkie typy całkowite Rusta obsługują nazwane operacje w celu wybrania zachowania: sprawdzone, zawijające, nasycające, ... więc możesz nadpisać wybrane zachowanie dla każdej operacji.
Matthieu M.,
1
@MatthieuM .: Tak, uwielbiam zawijanie, sprawdzanie i nasycanie, dodawanie / sub / przesuwanie / jakiekolwiek metody na typach prymitywnych. O wiele lepiej niż opakowanie C bez podpisu, UB podpisał, zmuszając cię do wyboru na tej podstawie. W każdym razie, niektóre ISA mogłyby zapewnić wydajną obsługę Panic, np. Lepka flaga, którą można sprawdzić po całej sekwencji operacji. (W przeciwieństwie do OF lub CF x86, które są nadpisywane przez 0 lub 1) np. Proponowany przez Agner Fog ForwardCom ISA ( agner.org/optimize/blog/read.php?i=421#478 ) Ale to nadal ogranicza optymalizację, aby nigdy nie wykonywać żadnych obliczeń źródło Rusta nie zrobiło. : /
Peter Cordes
31

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.

Hobbs
źródło
26

Aby zapewnić być może jaśniejszy przykład, na platformie x86_64, skompilowanej z -Oflagą, funkcja

pub 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ł u128raczej niż ten i128, 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 atej 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ę do a.

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 u128i 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.

Davislor
źródło
1
ostatni akapit: Aby wykryć, która z dwóch liczb bez znaku jest większa, patrząc na wyższy bit subwyniku, potrzebujesz n+1wyniku nbitowego 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).
Peter Cordes
1
re: divmod: Podejście AArch64 polega na zapewnieniu dzielenia i instrukcji wykonującej liczbę całkowitą 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.
Peter Cordes
1
re: flags: tak, wyjście flagi to drugie wyjście, które OoO exec + zmiana nazwy rejestru musi jakoś obsłużyć. Procesory x86 radzą sobie z tym, zachowując kilka dodatkowych bitów z wynikiem będącym liczbą całkowitą, na której opiera się wartość FLAGS, więc prawdopodobnie ZF, SF i PF są generowane w locie, gdy są potrzebne. Myślę, że jest na ten temat patent Intela. To redukuje liczbę wyjść, które muszą być śledzone oddzielnie z powrotem do 1. (W procesorach Intela żaden uop nie może nigdy zapisać więcej niż 1 rejestru całkowitego; np. mul r64Wynosi 2 uops, a drugi zapisuje wyższą połowę RDX).
Peter Cordes
1
Ale dla wydajnej rozszerzonej precyzji flagi są bardzo dobre. Głównym problemem jest to bez przemianowanie rejestrów do wykonania w superskalarnej zamówienie. flagi są zagrożeniem WAW (pisz po zapisaniu). Oczywiście instrukcje dodawania z przeniesieniem mają 3 wejścia i jest to również poważny problem do śledzenia. Intel przed Broadwell dekodowane adc, sbboraz cmovdo 2 UOPs każdy. (Haswell wprowadził 3-wejściowe Uops dla FMA, Broadwell rozszerzył to do liczby całkowitej.)
Peter Cordes
1
RISC ISA z flagami zwykle sprawiają, że ustawienie flagi jest opcjonalne, kontrolowane przez dodatkowy bit. np. ARM i SPARC są takie. PowerPC jak zwykle sprawia, że ​​wszystko jest bardziej skomplikowane: ma 8 rejestrów kodu stanu (spakowanych razem w jeden rejestr 32-bitowy do zapisywania / przywracania), dzięki czemu można porównać do cc0 lub cc7 lub cokolwiek innego. A potem razem kody warunków AND lub OR! Instrukcje Branch i cmov mogą wybrać, który rejestr CR ma zostać odczytany. Dzięki temu możesz mieć wiele flag dep w locie jednocześnie, takich jak x86 ADCX / ADOX. alanclements.org/power%20pc.html
Peter Cordes