Mengapa saya mem-fork `rand` demi API angka acak yang lebih kecil dan konsisten

• Crate angka acak utama Rust, rand, menyebarkan operasi sehari-hari ke banyak trait, sehingga dikembangkan urandom dengan permukaan publik dan implementasi yang lebih kecil serta pengalaman penggunaan yang konsisten
• Operasi tingkat tinggi dikumpulkan ke dalam satu struktur Random dan trait Rng disegel, sehingga kemudahan menemukan API dan optimasi internal diprioritaskan daripada dukungan generator acak sembarang
• Tanpa memperkenalkan algoritme angka acak baru, fungsi output Xoshiro256 dipilih sesuai penggunaan, dan pada benchmark pembuatan 1.000 f64 tercatat throughput sekitar 31% lebih tinggi dibanding rand 0.10.2
• Sampling integer uniform menyatukan jalur yang dapat dipakai ulang dan sekali pakai dengan satu implementasi tak bias yang menghitung ambang secara tertunda, dan pada benchmark rentang 500..20_000 lebih cepat daripada dua jalur milik rand
• Output mentah dengan seed eksplisit menjamin reproduktibilitas di arsitektur yang didukung dan rilis kompatibel SemVer, tetapi penyambungan generator acak sembarang serta ekosistem distribusi dan integrasi pihak ketiga rand yang luas harus dikorbankan

---

API Random yang disatukan

• Operasi berguna di rand tersebar di beberapa trait
  • Untuk membuat angka acak dalam rentang diperlukan RngExt, untuk memilih dari sekuens diperlukan IndexedRandom, dan untuk mengacak diperlukan SliceRandom
  • rand 0.10 menyediakan helper level-root seperti rand::random_range untuk pemanggilan sekali pakai
  • Namun jika ingin mempertahankan handle RNG atau memakai operasi sekuens seperti memilih dan mengacak, Anda tetap harus mencari metode di beberapa trait
• Sekalipun impor dikurangi dengan prelude, Anda tetap harus tahu extension method itu berlaku pada tipe RNG, slice, atau iterator, sehingga sulit ditemukan hanya lewat autocomplete IDE
• urandom menempatkan API konsumen tingkat tinggi ke dalam satu struktur pembungkus Random
  • urandom::new() membuat Random<urandom::rng::Xoshiro256Rng>
  • uniform, choose, dan shuffle dapat dipanggil dari objek yang sama
  • Lewat autocomplete Anda bisa melihat random, uniform, chance, choose, shuffle, sample, dan lainnya
  • Semuanya adalah metode inheren, jadi tidak perlu mencari atau mengimpor trait ekstensi tingkat tinggi

Rng tersegel yang memilih optimasi dibanding ekstensibilitas

• rand memperlakukan trait RNG tingkat rendah sebagai titik ekstensi publik, tetapi trait Rng di urandom disegel, sehingga generator yang didukung dipilih dan diimplementasikan di dalam crate
  • Generator acak sembarang tidak bisa disambungkan ke Random
  • Untuk menambahkan generator baru, urandom sendiri harus diubah
• Jika tujuannya adalah algoritme yang lebih baik, saat ini Xoshiro256 dan ChaCha sudah mapan sebagai pilihan baku untuk peran masing-masing, dan rekomendasinya juga berubah secara lambat
  • Jika ada pilihan yang lebih baik, itu bisa diadopsi pada rilis mayor mendatang
• Untuk kompatibilitas dengan proyek lain, bahasa pemrograman lain, algoritme lama, perangkat keras khusus, atau generator khusus simulasi, generator yang sama saja tidak cukup
  • Algoritme terkait seperti sampling uniform dan pengacakan juga harus sama, jadi implementasi khusus yang mewujudkan seluruh kontrak lebih cocok
• Berkat trait yang disegel, urandom hanya perlu menambahkan operasi mentah yang memang dibutuhkan, tanpa harus merancang dan mendokumentasikan kontrak implementasi untuk generator tak dikenal dan berbagai kondisi pengecualian
  • Generator dan algoritme bisa dispesialisasikan agar saling cocok, sehingga memungkinkan beberapa optimasi yang tidak dapat digunakan di rand
• Untuk sebagian besar aplikasi, pemilihan entropi lebih berguna daripada implementasi PRNG baru
  • Generator konkret mengekspos konstruktor native from_seed
  • Anda bisa membuat Random dengan seed eksplisit seperti ChaCha12Rng::from_seed(seed)
  • Meskipun tidak menerima implementasi RNG sembarang, titik ekstensi yang kemungkinan dibutuhkan pengguna tingkat lanjut tetap dipertahankan

Peningkatan performa dari algoritme yang sama

• urandom tidak memakai algoritme pembangkit angka acak yang baru
  • Pada sistem 64-bit, urandom::new() untuk penggunaan non-kriptografis dan rand::rngs::SmallRng sama-sama memakai keluarga Xoshiro256
  • Untuk penggunaan kriptografis, urandom::csprng() dan rand::rngs::StdRng memakai ChaCha12
  • Generator internal dari fungsi praktis rand::rng() juga ChaCha12
• Antarmuka generator rand menyediakan word integer dan pengisian byte, sehingga distribusi yang membutuhkan f64 pun meminta mulai dari u64 penuh
• urandom::Rng menyediakan bukan hanya next_u32 dan next_u64, tetapi juga next_f32 dan next_f64
  • Angka acak floating-point membutuhkan lebih sedikit bit acak daripada satu word penuh
  • Generator dapat menimpa metode-metode ini dengan fungsi output yang lebih murah
• Implementasi Xoshiro memisahkan jalur output sambil berbagi transisi state
  • Untuk u64, tetap memakai Xoshiro256++
  • Untuk u32 dan floating-point, dipakai Xoshiro256+ yang lebih cepat, dengan bit atas yang dirancang untuk penggunaan tersebut
• Hasil microbenchmark pembuatan masing-masing 1.000 angka acak dengan urandom 1.0 dan rand 0.10.2 adalah sebagai berikut
  • Xoshiro u64: keduanya 814ns
  • Xoshiro u32: rand 836ns, urandom 788ns
  • Xoshiro f64: rand 1,033ns, urandom 788ns
  • ChaCha12 f64: rand 2,199ns, urandom 2,011ns
• Throughput end-to-end untuk Xoshiro f64 sekitar 31% lebih tinggi dan waktu eksekusinya 24% lebih singkat, tetapi jalur u64 yang melakukan pekerjaan serupa pada dasarnya imbang
• Karena ChaCha12 tidak menimpa next_f64, performanya secara umum mirip
• Waktu pastinya bergantung pada mesin dan compiler, dan syarat detailnya dapat dilihat di catatan benchmark lengkap

Jalur sampling uniform yang disatukan

• Jika integer dipetakan ke panjang rentang hanya dengan operasi sisa sederhana, akan timbul bias, sehingga sampling integer uniform yang benar harus menolak sebagian output generator
• Menghitung ambang penolakan yang tepat membutuhkan operasi sisa yang mahal
  • Jika sampler dipakai berulang kali, ini bisa ditanggung sebagai biaya setup awal
  • Jika hanya membuat satu nilai, biaya ini menjadi relatif besar
• rand mengekspos perbedaan ini lewat trait UniformSampler
  • UniformInt yang dibuat akan menghitung ambang lebih dulu lalu mengambil sampel tanpa bias
  • Rng::random_range memakai hook sample_single atau sample_single_inclusive terpisah untuk menghindari setup awal
  • Dalam fitur default, jalur singkat sekali pakai memakai algoritme kedua yang sedikit bias
  • Fitur opsional unbiased menggantinya dengan versi berulang yang lebih kompleks
• urandom menghitung ambang secara tertunda dan memakai satu implementasi perkalian-penolakan tak bias untuk rentang yang dapat dipakai ulang maupun sekali pakai
  • Mengikuti pendekatan yang dijelaskan dalam paper Daniel Lemire tahun 2018, Fast Random Integer Generation in an Interval
  • Pada sebagian besar rentang praktis, kandidat pertama dikembalikan sebelum pembagian
  • Jika kandidat pertama tidak bisa dikembalikan, ambang yang tepat dihitung lalu pengulangan dilakukan tanpa bias
  • Kasus khusus range == 0 saat seluruh rentang diminta juga ditangani
• Distribusi yang dipakai ulang dan rentang sekali pakai ditangani dengan implementasi yang sama, tanpa metode terpisah, algoritme kedua, biaya setup di muka, atau jalur cepat yang bias
• Hasil benchmark pengambilan 1.000 sampel pada rentang 500..20_000 adalah sebagai berikut
  • UniformInt pakai ulang: rand 1,098ns, urandom 950ns
  • Rentang sekali pakai: rand 1,079ns, urandom 942ns
• Hasil rand menggunakan fitur default, jadi baris sekali pakai yang lebih cepat masih memakai jalur yang sedikit bias, sementara urandom lebih cepat dari kedua jalur itu dalam keadaan tak bias

Reproduksibilitas lintas rilis dan arsitektur

• urandom memperlakukan reproduksibilitas sebagai bagian dari kontrak publik
  • Dengan seed eksplisit yang sama dan urutan pemanggilan RNG tingkat rendah yang sama, output mentah dari generator deterministik dipertahankan
  • Stabilitas dijamin di seluruh arsitektur yang didukung dan rilis yang kompatibel dengan SemVer
  • Server 64-bit dan klien WebAssembly 32-bit dapat memakai basis generator yang sama untuk replay
• Demi menjaga kompatibilitas ini, performa di arsitektur 32-bit dikorbankan
• Ini adalah jaminan yang lebih kuat daripada kebijakan reproduksibilitas rand
  • Output generator portabel dan algoritme sampling rand dapat berubah pada rilis minor
  • SmallRng dan StdRng secara eksplisit tidak portabel dan juga dapat berubah tergantung platform atau rilis pustaka

Biaya pilihan dan kapan cocok dipakai

• urandom mengumpulkan operasi umum ke dalam Random sehingga mudah ditemukan tanpa trait ekstensi
• Dengan merancang generator dan distribusi bersama-sama, ia mengimplementasikan jalur output Xoshiro yang lebih murah dan satu jalur sampling uniform tak bias
• Stream mentah yang stabil dari generator dengan seed eksplisit bisa dimanfaatkan untuk game dan simulasi deterministik
• Sebagai gantinya, generator acak sembarang tidak bisa dibawa masuk, dan ia juga tidak memiliki daftar distribusi yang lebih besar serta ekosistem integrasi pihak ketiga yang disediakan rand
• Jika membutuhkan ekosistem yang luas, rand lebih cocok; jika Anda lebih menyukai permukaan API yang kecil, kemudahan penemuan, optimasi yang terintegrasi, dan kebijakan reproduksibilitas yang kuat, Anda bisa memilih urandom
• Paketnya dapat dilihat di crates.io, dokumentasi API, dan kode sumber GitHub

[GN⁺]

Komentar di Lobste.rs

• Ada cukup alasan untuk mem-fork rand, tetapi nama urandom terdengar seperti library yang terkait dengan /dev/urandom

  • Terlihat berguna, tetapi namanya bisa membingungkan. Kalau hanya melihat namanya tanpa membaca artikelnya, saya mungkin mengira library ini bergantung pada I/O file dan tidak akan meninjaunya

• Saya setuju dengan masalah yang diangkat, tetapi tidak suka pub fn new() -> Random<impl Rng + Clone>
  Jika seluruh aplikasi diparameterisasi sebagai Random<T> where T: Rng, pekerjaan merepotkan akan bertambah, dan masalah terkait waktu kompilasi serta dyn menjadi serius. Saya lebih memilih struct Random memiliki tipe konkret, atau sebagai opsi kedua, memilih struct Random<T = rng::Xoshiro256Rng>

• Karena frustrasi serupa, saya sudah pernah membuat sendiri, tetapi bukan fork, dan fiturnya jauh lebih sedikit daripada rand

• Senang melihat ada orang lain yang merasakan masalah yang sama seperti saya dan benar-benar mencoba menyelesaikannya. Rust tampaknya punya kecenderungan aneh untuk mendorong pembuatan library trait soup
  Tipe data inti pada basis data yang saya tangani di pekerjaan harus mengimplementasikan setidaknya 15 trait, sehingga autocomplete berantakan dan dokumentasinya juga membingungkan. Kami sudah mengurangi sebagian jumlah trait, tetapi sering terhambat oleh dependensi siklik atau masalah yang membuat pengujian inti tidak bisa ditulis

  • Ini terjadi karena para architecture astronaut dari latar belakang Java menerapkan gaya berorientasi objek yang sama ke Rust. Dependensi siklik adalah tanda bahwa satu hal yang belum bisa dipisahkan dipaksa dipecah, atau tiga hal tidak dibedakan dengan benar. Jika Anda bisa mengendalikan seluruh kode, gunakan enum alih-alih trait
  • Di ekosistem kriptografi Rust, masalah trait soup sangat parah sampai membuat frustrasi

• Library ini mengingatkan saya pada deep interface dari APOSD dan pekerjaan kriptografi Filippo yang dirancang agar sulit disalahgunakan; keduanya merupakan pujian besar

  • Namun, karena urandom::new() tidak mengembalikan pembangkit bilangan acak yang aman secara kriptografis, desainnya belum sepenuhnya tidak mungkin disalahgunakan. Ini makin membingungkan terutama karena /dev/urandom di Linux aman

• Sebagai alternatif lain untuk rand, ada fastrand, pembangkit bilangan acak yang sederhana dan cepat. Lebih sederhana daripada rand dan urandom, tetapi fiturnya juga lebih sedikit