Rust memiliki integer 128-bit, ini dilambangkan dengan tipe data i128
(dan u128
untuk int yang tidak ditandatangani):
let a: i128 = 170141183460469231731687303715884105727;
Bagaimana cara Rust membuat i128
nilai - nilai ini bekerja pada sistem 64-bit; misalnya bagaimana cara menghitungnya?
Karena, sejauh yang saya tahu, nilai tidak dapat masuk dalam satu register CPU x86-64, apakah kompiler entah bagaimana menggunakan 2 register untuk satu i128
nilai? Atau apakah mereka malah menggunakan semacam integ integ besar untuk mewakili mereka?
Jawaban:
Semua tipe integer Rust dikompilasi ke integer LLVM . Mesin abstrak LLVM memungkinkan bilangan bulat dari lebar bit dari 1 hingga 2 ^ 23 - 1. * Petunjuk LLVM biasanya bekerja pada bilangan bulat dari berbagai ukuran.
Jelas, tidak banyak arsitektur 8388607-bit di luar sana, jadi ketika kode dikompilasi ke kode mesin asli, LLVM harus memutuskan bagaimana mengimplementasikannya. Semantik dari instruksi abstrak seperti
add
didefinisikan oleh LLVM itu sendiri. Biasanya, instruksi abstrak yang memiliki instruksi tunggal yang setara dalam kode asli akan dikompilasi dengan instruksi asli itu, sedangkan instruksi yang tidak akan ditiru, mungkin dengan beberapa instruksi asli. jawaban mcarton menunjukkan bagaimana LLVM mengkompilasi baik instruksi asli maupun yang ditiru.(Ini tidak hanya berlaku untuk bilangan bulat yang lebih besar dari yang dapat didukung oleh mesin asli, tetapi juga yang lebih kecil. Misalnya, arsitektur modern mungkin tidak mendukung aritmatika 8-bit asli, sehingga
add
instruksi pada duai8
s dapat ditiru dengan instruksi yang lebih luas, bit ekstra dibuang.)Pada tingkat LLVM IR, jawabannya adalah tidak:
i128
cocok dalam satu register, sama seperti setiap jenis lainnya yang bernilai tunggal . Di sisi lain, setelah diterjemahkan ke kode mesin, sebenarnya tidak ada perbedaan di antara keduanya, karena struct dapat didekomposisi menjadi register seperti integer. Ketika melakukan aritmatika, bagaimanapun, itu adalah taruhan yang cukup aman bahwa LLVM hanya akan memuat semuanya menjadi dua register.* Namun, tidak semua backend LLVM dibuat sama. Jawaban ini berkaitan dengan x86-64. Saya mengerti bahwa dukungan backend untuk ukuran yang lebih besar dari 128 dan non-power dari dua adalah jerawatan (yang sebagian dapat menjelaskan mengapa Rust hanya memperlihatkan bilangan bulat 8-, 16-, 32-, 64-, dan 128-bit). Menurut est31 pada Reddit , rustc mengimplementasikan integer 128 bit dalam perangkat lunak ketika menargetkan backend yang tidak mendukungnya secara asli.
sumber
Type
kelas ini berarti ada 8 bit untuk menyimpan jenisnya (fungsi, blok, integer, ...) dan 24 bit untuk data subkelas. TheIntegerType
kelas kemudian menggunakan mereka 24 bit untuk menyimpan ukuran, yang memungkinkan contoh untuk menyesuaikan dengan rapi di 32 bit!Kompiler akan menyimpan ini di banyak register dan menggunakan banyak instruksi untuk melakukan aritmatika pada nilai-nilai tersebut jika diperlukan. Sebagian besar ISA memiliki instruksi add-with-carry seperti x86
adc
yang membuatnya cukup efisien untuk melakukan add / sub integer dengan presisi yang diperluas.Misalnya diberikan
kompiler menghasilkan yang berikut ketika mengkompilasi untuk x86-64 tanpa optimisasi:
(komentar ditambahkan oleh @PeterCordes)
di mana Anda dapat melihat bahwa nilai
42
disimpan dirax
danrcx
.(catatan editor: konvensi pemanggilan x86-64 C mengembalikan bilangan bulat 128-bit dalam RDX: RAX. Tetapi ini
main
tidak mengembalikan nilai sama sekali. Semua penyalinan yang berlebihan adalah murni dari menonaktifkan optimasi, dan bahwa Rust benar-benar memeriksa overflow pada debug mode.)Sebagai perbandingan, di sini adalah ASM untuk integer Rust 64-bit pada x86-64 di mana tidak diperlukan add-with-carry, hanya satu register atau stack-slot untuk setiap nilai.
Setb / test masih benar-benar berlebihan:
jc
(melompat jika CF = 1) akan bekerja dengan baik.Dengan optimasi diaktifkan, compiler Rust tidak memeriksa overflow sehingga
+
karya seperti.wrapping_add()
.sumber
u128
argumen dan mengembalikan nilai (seperti ini godbolt.org/z/6JBza0 ), alih-alih menonaktifkan pengoptimalan untuk menghentikan kompiler melakukan propagasi konstan pada compile-time-constant args.Ya, sama seperti penanganan integer 64-bit pada mesin 32-bit, atau integer 32-bit pada mesin 16-bit, atau bahkan integer 16-dan 32-bit pada mesin 8-bit (masih berlaku untuk mikrokontroler! ). Ya, Anda menyimpan nomor dalam dua register, atau lokasi memori, atau apa pun (itu tidak masalah). Penambahan dan pengurangan sepele, mengambil dua instruksi dan menggunakan flag carry. Perkalian membutuhkan tiga perkalian dan beberapa tambahan (itu umum untuk chip 64-bit untuk sudah memiliki operasi multiplikasi 64x64-> 128 yang menghasilkan dua register). Divisi ... membutuhkan subrutin dan cukup lambat (kecuali dalam beberapa kasus di mana pembagian oleh konstanta dapat diubah menjadi shift atau multiply), tetapi masih berfungsi. Bitwise dan / atau / atau hanya harus dilakukan pada bagian atas dan bawah secara terpisah. Pergeseran dapat dilakukan dengan rotasi dan masking. Dan itu mencakup banyak hal.
sumber
Untuk memberikan contoh yang lebih jelas, pada x86_64, dikompilasi dengan
-O
flag, fungsinyakompilasi ke
(Posting asli saya
u128
lebih baik daripada yangi128
Anda tanyakan. Fungsi mengkompilasi kode yang sama, demonstrasi yang baik yang ditandatangani dan tidak ditandatangani sama pada CPU modern.)Daftar lainnya menghasilkan kode yang tidak dioptimalkan. Aman untuk melangkah melalui debugger, karena memastikan Anda dapat meletakkan breakpoint di mana saja dan memeriksa status variabel apa pun di setiap baris program. Lebih lambat dan sulit dibaca. Versi yang dioptimalkan jauh lebih dekat dengan kode yang benar-benar akan berjalan dalam produksi.
Parameter
a
fungsi ini dilewatkan dalam sepasang register 64-bit, rsi: rdi. Hasilnya dikembalikan dalam pasangan register lain, rdx: rax. Dua baris kode pertama menginisialisasi jumlah kea
.Baris ketiga menambahkan 1337 ke kata input yang rendah. Jika ini meluap, ia membawa 1 di flag carry CPU. Baris keempat menambahkan nol pada kata tinggi input — ditambah 1 jika dijalankan.
Anda dapat menganggap ini sebagai penambahan sederhana dari nomor satu digit ke nomor dua digit
tetapi dalam basis 18.446.744.073.709.551.616. Anda masih menambahkan "digit" terendah terlebih dahulu, mungkin membawa 1 ke kolom berikutnya, lalu menambahkan digit berikutnya ditambah carry. Pengurangan sangat mirip.
Perkalian harus menggunakan identitas (2⁶⁴a + b) (2⁶⁴c + d) = 2¹²⁸ac + 2⁶⁴ (ad + bc) + bd, di mana masing-masing perkalian ini mengembalikan bagian atas produk dalam satu register dan bagian bawah produk dalam lain. Beberapa istilah tersebut akan dihapus, karena bit di atas 128 tidak cocok dengan a
u128
dan dibuang. Meski begitu, ini membutuhkan sejumlah instruksi mesin. Divisi juga mengambil beberapa langkah. Untuk nilai yang ditandatangani, perkalian dan pembagian juga perlu mengubah tanda-tanda operan dan hasilnya. Operasi-operasi itu sama sekali tidak efisien.Pada arsitektur lain, itu menjadi lebih mudah atau lebih sulit. RISC-V mendefinisikan ekstensi set instruksi 128-bit, meskipun setahu saya tidak ada yang menerapkannya dalam silikon. Tanpa ekstensi ini, manual arsitektur RISC-V merekomendasikan cabang bersyarat:
addi t0, t1, +imm; blt t0, t1, overflow
SPARC memiliki kode kontrol seperti flag kontrol x86, tetapi Anda harus menggunakan instruksi khusus
add,cc
,, untuk mengaturnya. MIPS, di sisi lain, mengharuskan Anda untuk memeriksa apakah jumlah dua bilangan bulat yang tidak ditandatangani benar-benar kurang dari satu operan. Jika demikian, penambahan meluap. Setidaknya Anda dapat mengatur register lain ke nilai carry bit tanpa cabang kondisional.sumber
sub
hasil yang tinggi, Anda memerlukann+1
sub hasiln
bit untuk input bit. yaitu Anda perlu melihat pelaksanaan, bukan tanda sedikit dari hasil yang sama lebarnya. Itu sebabnya kondisi cabang unsigned x86 didasarkan pada CF (bit 64 atau 32 dari hasil logis penuh), bukan SF (bit 63 atau 31).x - (a*b)
, menghitung sisanya dari dividen, pembagian, dan pembagi. (Itu berguna bahkan untuk pembagi konstan menggunakan invers multiplikasi untuk bagian divisi). Saya belum membaca tentang ISA yang memadukan instruksi div + mod ke dalam operasi divmod tunggal; itu rapi.mul r64
2 uops, dengan yang ke-2 menulis RDX setengah tinggi).adc
,sbb
dancmov
untuk 2 UOPs setiap. (Haswell memperkenalkan 3-input uops untuk FMA, Broadwell memperluasnya ke integer.)