Sebagian besar tulisan saya tentang pembuatan angka acak terutama berkaitan dengan properti dari berbagai skema generasi. Ini mungkin ternyata tidak terduga, tetapi kinerja algoritma pengacakan tidak tergantung pada skema generasi yang dipilih, tetapi pada faktor-faktor lain. Dalam posting ini (yang saya terinspirasi oleh
artikel yang sangat bagus
oleh Daniel Lemyr ), kami akan memeriksa alasan utama untuk penurunan kinerja generasi nomor acak, yang sering melebihi kinerja mesin PRN.
Bayangkan situasi ini:
Sebagai pekerjaan rumah, Juan dan Sasha menerapkan algoritma acak yang sama di C ++, yang akan berjalan di komputer universitas yang sama dan dengan satu set data. Kode mereka hampir identik dan hanya berbeda dalam generasi angka acak. Juan sedang terburu-buru untuk pelajaran musiknya, jadi dia hanya memilih angin puyuh Mersenne. Sasha, di sisi lain, menghabiskan beberapa jam ekstra untuk meneliti. Sasha melakukan tolok ukur beberapa PRNG tercepat, yang baru-baru ini ia pelajari dari jejaring sosial, dan memilih yang tercepat. Pada pertemuan itu, Sasha tidak sabar untuk menyombongkan diri, dan dia bertanya kepada Juan: "PRNG apa yang kamu gunakan?"
"Secara pribadi, saya baru saja mengambil pusaran Mersenne - itu dibangun ke dalam bahasa dan tampaknya bekerja dengan cukup baik."
"Ha!" Jawab Sasha. “Saya menggunakan
jsf32 . Ini jauh lebih cepat daripada angin puyuh Mersenne yang lama dan lambat! Program saya berjalan dalam 3 menit 15 detik! "
"Hmm, tidak buruk, tapi milikku bisa melakukannya dalam waktu kurang dari satu menit," kata Juan dan mengangkat bahu. “Kalau begitu, aku harus pergi ke konser. Maukah Anda ikut dengan saya? "
"Tidak," jawab Sasha. "Aku ... eh ... perlu melihat kodeku lagi."
Situasi fiksi yang canggung ini
tidak terlalu fiksi; ini didasarkan pada hasil nyata. Jika algoritma acak Anda tidak berjalan secepat yang kami inginkan, dan bottleneck tampaknya menjadi nomor acak, maka, anehnya, masalahnya mungkin bukan pada generator angka acak!
Pendahuluan: Angka Acak dalam Praktek
Kebanyakan generator angka acak modern berkualitas tinggi menciptakan kata-kata mesin yang diisi dengan bit acak, yaitu, mereka biasanya menghasilkan angka dalam interval [0..2
32 ] atau [0..2
64 ). Tetapi dalam banyak kasus penggunaan, pengguna membutuhkan angka dalam interval tertentu - misalnya, untuk melempar dadu atau memilih kartu bermain acak, angka diperlukan dalam interval konstan kecil. Namun, banyak algoritma, dari
pencampuran dan
pengambilan sampel reservoir hingga
pohon pencarian biner acak, membutuhkan angka yang diambil dari interval lain.
Metode
Kami akan melihat banyak metode yang berbeda. Untuk menyederhanakan diskusi, alih-alih menghasilkan angka dalam interval [
i ..
j ) atau [
i ..
j ], kita akan menghasilkan angka dalam interval [0 ..
k ). Dengan skema seperti itu, kita dapat, misalnya, menghasilkan angka dalam interval [
i ..
j ) dengan mengatur
k =
j -
i , menghasilkan angka dalam interval [0 ..
k ), dan kemudian menambahkan
i ke dalamnya.
Alat C ++ bawaan
Banyak bahasa memiliki alat bawaan untuk mendapatkan angka acak dalam interval yang ditentukan. Sebagai contoh, untuk menghapus kartu dari tumpukan dengan 52 kartu dalam bahasa scripting seperti Perl dan Python, kita dapat menulis
int(rand(52)) dan
random.randint(0,52) . [Catatan Pengguna
CryptoPirate :
Menurut saya ada kesalahan di sini, dalam Python randint (a, b) menghasilkan angka dari a ke b termasuk b. Dan karena ada 52 kartu di dek dan yang pertama adalah "0", itu harus acak.randint (0,51) .] Dalam C ++, kita dapat menggunakan
uniform_int_distribution dengan
uniform_int_distribution sama.
Kode C ++ untuk mengimplementasikan pendekatan ini sederhana:
uint32_t bounded_rand(rng_t& rng, uint32_t range) { std::uniform_int_distribution<uint32_t> dist(0, range-1); return dist(rng); }
Biasanya, salah satu teknik yang dijelaskan di bawah ini digunakan dalam alat bawaan, tetapi sebagian besar pengguna hanya menggunakan alat ini, tidak memikirkan apa yang terjadi "di bawah tenda," percaya bahwa alat ini dirancang dengan benar dan cukup efektif. Dalam C ++, alat bawaan lebih kompleks karena mereka harus dapat bekerja dengan mesin generasi yang sewenang-wenang - generator yang menghasilkan nilai dalam kisaran dari -3 hingga 17 bisa sangat valid dan dapat digunakan dengan
std::uniform_int_distribution untuk membuat angka dalam interval apa pun, misalnya [0..1000). Artinya, alat C ++ bawaan terlalu rumit untuk sebagian besar kasus di mana mereka digunakan.
Sisa klasik dari divisi (condong)
Mari kita beralih dari pendekatan yang terlalu disederhanakan ke pendekatan yang terlalu sederhana.
Ketika saya mempelajari pemrograman, kami menghasilkan angka dalam interval (misalnya, untuk memilih kartu dalam setumpuk 52 kartu) menggunakan operator sisanya. Untuk mendapatkan nomor dalam interval [0..52), kami menulis
rand() % 52 .
Dalam C ++, pendekatan ini dapat diimplementasikan sebagai berikut:
uint32_t bounded_rand(rng_t& rng, uint32_t range) { return rng() % range; }
Terlepas dari kesederhanaan pendekatan ini, ini menunjukkan alasan bahwa mendapatkan angka pada interval yang tepat biasanya merupakan tugas yang lambat - ini membutuhkan pembagian (untuk menghitung sisanya yang diperoleh oleh
% operator). Membagi biasanya setidaknya urutan besarnya lebih lambat dari operasi aritmatika lainnya, sehingga operasi aritmatika tunggal membutuhkan waktu lebih lama dari semua pekerjaan yang dilakukan oleh PRNG cepat.
Namun selain kecepatan rendah, ia juga
condong . Untuk memahami mengapa
rand() % 52 mengembalikan angka miring, misalkan
rand() membuat angka dalam interval [0..2
32 ), dan perhatikan bahwa 52 tidak membagi 2
32 sepenuhnya, ia membaginya 82 595 524 kali dengan sisanya. 48. Yaitu, jika kita menggunakan
rand() % 52 , maka kita akan memiliki 82 595 525 cara untuk memilih 48 kartu pertama dari tumpukan dan hanya 82 595 524 cara untuk memilih empat kartu terakhir. Dengan kata lain, ada kemiringan 0,00000121% terhadap empat kartu terakhir ini (mungkin ini adalah raja!). Ketika saya masih mahasiswa dan menulis pekerjaan rumah tentang melempar dadu atau menggambar kartu, biasanya tidak ada yang peduli tentang distorsi sekecil itu, tetapi dengan peningkatan interval, distorsi tumbuh secara linear. Untuk PRNG 32-bit, interval terbatas kurang dari 2
24 memiliki kemiringan kurang dari 0,5%, tetapi di atas 2
31 kemiringan 50% - beberapa angka akan kembali dua kali lebih sering daripada yang lain.
Dalam artikel ini, kami terutama akan mempertimbangkan teknik yang menggunakan strategi untuk menghilangkan kesalahan sistematis, tetapi mungkin layak dikatakan bahwa untuk PRNG 64-bit, nilai miring pada aplikasi biasa cenderung diabaikan.
Masalah lain mungkin beberapa generator memiliki bit rendah yang lemah. Misalnya, keluarga GPRS Xoroshiro + dan Xoshiro + memiliki bit rendah yang tidak lulus tes statistik. Ketika kita mengeksekusi
% 52 (karena 52 genap), kita meneruskan bit orde rendah langsung ke output.
Mengalikan angka floating point (condong)
Teknik umum lainnya adalah penggunaan PRNG yang menghasilkan angka floating point dalam interval [0..1) dengan konversi selanjutnya dari angka-angka ini ke interval yang diinginkan. Pendekatan ini digunakan dalam Perl,
disarankan untuk menggunakan
int(rand(10)) untuk menghasilkan integer dalam interval [0..10) dengan menghasilkan angka titik-mengambang diikuti dengan pembulatan ke bawah.
Dalam C ++, pendekatan ini ditulis seperti ini:
static uint32_t bounded_rand(rng_t& rng, uint32_t range) { double zeroone = 0x1.0p-32 * rng(); return range * zeroone; }
(Perhatikan bahwa
0x1.0p-32 adalah konstanta titik-mengambang biner untuk 2
-32 , yang kami gunakan untuk mengonversi bilangan bulat acak dalam interval [0..2
32 ) menjadi dua kali lipat dalam interval unit; alih-alih, kita dapat melakukan konversi seperti itu menggunakan
ldexp(rng(), -32) , tetapi ketika saya membandingkan pendekatan ini, ternyata lebih lambat.)
Pendekatan ini sama miringnya dengan sisa klasik pembagian, tetapi kemiringan tampak berbeda. Sebagai contoh, jika kita memilih angka dalam interval [0..52), maka angka 0, 13, 26, dan 39 akan muncul sekali lebih jarang daripada yang lain.
Versi ini, ketika digeneralisasikan ke 64 bit, bahkan lebih tidak menyenangkan, karena memerlukan tipe floating point yang mantissanya setidaknya 64 bit. Pada mesin x86 dengan Linux dan macOS, kita dapat menggunakan
long double untuk memanfaatkan peningkatan angka floating-point x86 presisi yang memiliki mantissa 64-bit, tetapi
long double tidak secara universal diangkut ke semua sistem - dalam beberapa sistem,
long double setara dengan
double .
Ada sisi baiknya - pendekatan ini lebih cepat daripada solusi residual untuk PRNG dengan bit rendah yang lemah.
Multiplikasi Integer (Miring)
Metode multiplikasi dapat disesuaikan dengan aritmatika fixed daripada floating point. Bahkan, kami hanya terus-menerus mengalikan dengan
32 ,
uint32_t bounded_rand(rng_t& rng, uint32_t range) { uint32_t x = rng(); uint64_t m = uint64_t(x) * uint64_t(range); return m >> 32; }
Tampaknya versi ini membutuhkan aritmatika 64-bit, pada prosesor x86, kompiler yang baik akan mengkompilasi kode ini menjadi instruksi
mult -bit 32-bit (yang memberi kita dua nilai output 32-bit, salah satunya adalah nilai balik). Versi ini bisa diharapkan cepat, tetapi miring persis seperti metode mengalikan angka floating point.
Jatuhkan divisi (tidak condong)
Kita dapat memodifikasi skema perkalian floating point menjadi skema berbasis divisi. Alih-alih mengalikan
x * range / 2**32 kami menghitung
x / (2**32 / range) . Karena kami bekerja dengan bilangan bulat aritmatika, pembulatan dalam versi ini akan dilakukan secara berbeda, dan terkadang menghasilkan nilai di luar interval yang diinginkan. Jika kita membuang nilai-nilai ini (misalnya, membuangnya dan menghasilkan nilai-nilai baru), maka sebagai hasilnya kita mendapatkan teknik tanpa distorsi.
Misalnya, dalam kasus mengeluarkan kartu menggunakan PRNG 32-bit, kita dapat menghasilkan nomor 32-bit dan membaginya dengan 2 32/52 = 82 595 524 untuk memilih kartu. Teknik ini berfungsi jika nilai acak dari PRNG 32-bit kurang dari 52 × 82595524 = 2 32/32 - 48. Jika nilai acak dari PRNR adalah salah satu dari 48 nilai terakhir dari bagian atas interval generator, maka Anda harus membuangnya dan mencari yang lain.
Kode kami untuk versi ini menggunakan trik dengan membagi 2
32 berdasarkan
range tanpa menggunakan matematika 64-bit. Untuk perhitungan langsung
2**32 / range kita perlu merepresentasikan angka 2
32 , yang terlalu besar (per satu!) Untuk direpresentasikan sebagai integer 32-bit. Sebagai gantinya, kami memperhitungkan bahwa untuk bilangan bulat tak bertanda, kisaran operasi negasi unary menghitung nilai positif dari
range 2
32 ; membagi nilai ini dengan
range , kami mendapat respons yang kurang dari
2**32 / range .
Oleh karena itu, kode C ++ untuk menghasilkan angka menggunakan pembagian dan penurunan terlihat seperti ini:
uint32_t bounded_rand(rng_t& rng, uint32_t range) {
Tentu saja, pendekatan ini membutuhkan dua operasi lambat berdasarkan divisi, yang biasanya lebih lambat daripada operasi aritmatika lainnya, jadi Anda seharusnya tidak mengharapkannya cepat.
Sisa dari divisi (ganda) tanpa distorsi - teknik OpenBSD
Kita juga dapat mengambil pendekatan jatuhkan untuk menghilangkan kemiringan dalam metode pembagian divisi klasik. Dalam contoh dengan bermain kartu, kita perlu lagi menjatuhkan 48 nilai. Dalam versi ini, alih-alih membuang 48 nilai
terakhir , kami (setara) membuang 48 nilai
pertama .
Berikut ini adalah implementasi dari pendekatan ini dalam C ++:
uint32_t bounded_rand(rng_t& rng, uint32_t range) {
Teknik ini menghilangkan kemiringan, tetapi membutuhkan dua operasi pembagian yang memakan waktu dengan sisa dari masing-masing nilai output (dan Anda mungkin memerlukan generator internal untuk membuat beberapa angka). Oleh karena itu, harus diharapkan bahwa metode ini akan menjadi sekitar dua kali lebih lambat daripada pendekatan kemiringan klasik.
arc4random_uniform OpenBSD arc4random_uniform (yang juga digunakan pada OS X dan iOS) menggunakan strategi ini.
Sisa pembagian (tunggal) tanpa metodologi miring - Jawa
Java menggunakan pendekatan yang berbeda untuk menghasilkan angka dalam interval yang hanya menggunakan satu operasi pembagian sisa, dengan pengecualian kasus yang cukup jarang membuang hasil. Kode:
static uint32_t bounded_rand(rng_t& rng, uint32_t range) { uint32_t x, r; do { x = rng(); r = x % range; } while (x - r > (-range)); return r; }
Untuk memahami mengapa opsi ini berfungsi, Anda perlu berpikir sedikit. Berbeda dengan versi sebelumnya yang didasarkan pada residu, yang menghilangkan bias dengan menghapus bagian dari nilai terendah dari mesin pembangkitan internal, versi ini memfilter nilai dari bagian atas interval mesin.
Perkalian bilangan bulat miring - Metode Lemira
Dalam banyak cara yang sama kita menghilangkan bias dari sisa metode pembagian, kita dapat menghilangkan bias dari teknik multiplikasi bilangan bulat. Teknik ini ditemukan oleh Lemyr.
uint32_t bounded_rand(rng_t& rng, uint32_t range) { uint32_t t = (-range) % range; do { uint32_t x = rng(); uint64_t m = uint64_t(x) * uint64_t(range); uint32_t l = uint32_t(m); } while (l < t); return m >> 32; }
Drop bitmask (no skew) - Teknik Apple
Dalam pendekatan terakhir kami, operasi divisi dan sisanya sepenuhnya dihilangkan. Sebagai gantinya, ia menggunakan operasi masking sederhana untuk mendapatkan angka acak dalam interval [0..2
k ), di mana
k adalah nilai terkecil, sehingga 2
k lebih besar dari interval. Jika nilainya terlalu besar untuk interval kami, kami membuangnya dan mencoba untuk mendapatkan yang lain. Kode ditunjukkan di bawah ini:
uint32_t bounded_rand(rng_t& rng, uint32_t range) { uint32_t mask = ~uint32_t(0); --range; mask >>= __builtin_clz(range|1); uint32_t x; do { x = rng() & mask; } while (x > range); return x; }
Pendekatan ini diadopsi oleh Apple ketika (dalam rilis macOS Sierra) melakukan
revisi sendiri terhadap kode
arc4random_uniform .
Membandingkan teknik dasar
Sekarang kami memiliki beberapa pendekatan yang dapat dievaluasi. Sayangnya, ketika kita khawatir tentang biaya operasi divisi tunggal, pembandingan menjadi hal yang tidak sepele. Tidak ada patokan yang dapat memperhitungkan semua faktor yang mempengaruhi bidang aplikasi, dan tidak ada jaminan bahwa opsi terbaik untuk aplikasi Anda tentu akan menjadi yang terbaik untuk tambang.
Kami menggunakan tiga tolok ukur dan menguji teknik dengan banyak PRNG yang berbeda.
Benchmark Large-Shuffle
Mungkin tolok ukur yang paling jelas adalah pencampuran. Dalam tolok ukur ini, kami mensimulasikan melakukan pencampuran skala besar. Untuk mengurutkan array ukuran
N, kita harus menghasilkan angka dalam interval [0 ..
N ), [0 .. (
N -1)), ..., [0..1). Dalam tolok ukur ini, kita akan menganggap bahwa
N adalah angka maksimum yang mungkin (untuk
uint32_t adalah 2
32 -1). Kode:
for (uint32_t i = 0xffffffff; i > 0; --i) { uint32_t bval = bounded_rand(rng, i); assert(bval < i); sum += bval; }
Perhatikan bahwa kami "menggunakan" setiap angka dengan menambahkannya ke
sum (sehingga tidak akan dibuang dengan optimasi), tetapi kami tidak melakukan pencampuran apa pun untuk fokus pada generasi angka.
Untuk pengujian generasi 64-bit, kami memiliki tes yang serupa, tetapi akan tidak praktis untuk melakukan tes yang sesuai dengan pencampuran array ukuran 2
64 - 1 (karena akan membutuhkan ribuan tahun untuk menyelesaikan benchmark yang lebih besar ini). Sebagai gantinya, kami melintasi seluruh interval 64-bit, tetapi menghasilkan jumlah nilai output yang sama seperti pada uji 32-bit. Kode:
for (uint32_t i = 0xffffffff; i > 0; --i) { uint64_t bound = (uint64_t(i)<<32) | i; uint64_t bval = bounded_rand(rng, bound ); assert(bval < bound); sum += bval; }
Hasil vortex Mersenne
Hasil yang ditunjukkan di bawah ini menunjukkan kinerja tolok ukur ini untuk masing-masing metode yang kami teliti ketika menggunakan Mersenne vortex dan mengujinya pada 32-bit (menggunakan
std::mt19937 dari
libstdc++ ) dan kode 64-bit yang serupa (menggunakan
std:mt19937_64 dari
libstdc++ ) Hasilnya adalah rata-rata geometris 15 run dengan nilai seed yang berbeda, yang kemudian dinormalisasi sehingga metode pembagian divisi klasik memiliki waktu run tunggal.
Tampaknya kami memiliki jawaban yang jelas tentang kinerja - tampaknya Anda dapat membangun teknik untuk kesempurnaan mereka, dan bertanya pada diri sendiri apa yang dipikirkan pengembang
libstdc++ ketika mereka menulis implementasi yang mengerikan untuk angka 32-bit. Tetapi, seperti yang sering terjadi dengan pembandingan, situasinya lebih rumit daripada yang terlihat dari hasil ini. Pertama, ada risiko bahwa hasilnya mungkin spesifik untuk pusaran Mersenne, jadi kami akan memperluas banyak PRNG yang diuji. Kedua, mungkin ada masalah dengan benchmark itu sendiri. Mari kita berurusan dengan pertanyaan pertama.
Hasil dari berbagai PRNG
Kami akan menguji
arc4_rand32 32-bit dengan
arc4_rand32 ,
chacha8r ,
gjrand32 ,
jsf32 ,
mt19937 ,
pcg32 ,
pcg32_fast ,
sfc32 ,
splitmix32 ,
xoroshiro64+ ,
xorshift*64/32 xoshiro128+ ,
xoshiro128+ dan
xoshiro128** , dan
gjrand64 dengan
gjrand64 jsf64 ,
mcg128 ,
mcg128_fast ,
mt19937_64 ,
pcg64 ,
pcg64_fast ,
sfc64 ,
splitmix64 ,
xoroshiro128+ ,
xorshift*128/64 xoshiro256+ ,
xoshiro256+ dan
xoshiro256* . Kit ini akan memberi kita beberapa PRN lambat dan banyak yang sangat cepat.
Inilah hasilnya:
Kita bisa melihat perbedaan utama dari hasil dengan vortex Mersenne. PRNG lebih cepat menggeser kesetimbangan ke arah kode terikat, dan oleh karena itu perbedaan antara pendekatan yang berbeda menjadi lebih jelas, terutama dalam kasus PRNR 64-bit. Dengan serangkaian
libstc++ lebih luas
libstc++ implementasi
libstc++ tidak lagi tampak mengerikan.
Kesimpulan
Dalam benchmark ini dengan margin yang signifikan, pendekatan yang didasarkan pada multiplikasi dengan bias menang dalam kecepatan. Ada banyak situasi di mana batas-batasnya akan relatif kecil dibandingkan dengan ukuran PRNG, dan kinerja sangat penting. Dalam situasi seperti itu, sedikit bias tidak mungkin memiliki efek yang nyata, tetapi kecepatan PRNG akan memiliki. Salah satu contohnya adalah Quicksort dengan titik referensi acak. Dari metode yang miring, teknik bitmask terlihat menjanjikan.
Tetapi sebelum membuat kesimpulan yang serius, kita perlu menunjukkan masalah besar dari tolok ukur ini - sebagian besar waktu dihabiskan untuk batas yang sangat tinggi, yang kemungkinan besar memberikan kepentingan berlebihan pada interval besar. Karena itu, kita perlu menuju ke benchmark kedua.
Benchmark Small-Shuffle
Benchmark ini mirip dengan yang sebelumnya, tetapi melakukan jauh lebih sedikit "pencampuran array" (beberapa). Kode: for (uint32_t j = 0; j < 0xffff; ++j) { for (uint32_t i = 0xffff; i > 0; --i) { uint32_t bval = bounded_rand(rng, i); assert(bval < i); sum += bval; } }
Hasil vortex Mersenne
Hasil dari berbagai PRNG
Kesimpulan
Benchmark ini menghindari terlalu banyak penekanan pada batas besar dan lebih akurat mencerminkan kasus penggunaan dunia nyata, tetapi sekarang benar-benar membuang batas besar.Benchmark untuk semua interval
Penghitungan ini bertujuan untuk menghindari kerugian dari dua yang sebelumnya; ia melakukan pengujian pada setiap ukuran kekuatan dua sehingga setiap ukuran hadir, tetapi pengaruhnya tidak berlebihan. for (uint32_t bit = 1; bit != 0; bit <<= 1) { for (uint32_t i = 0; i < 0x1000000; ++i) { uint32_t bound = bit | (i & (bit - 1)); uint32_t bval = bounded_rand(rng, bound); assert(bval < bound); sum += bval; } }
Hasil vortex Mersenne
Hasil dari berbagai PRNG
Kesimpulan
Banyak temuan kami yang tidak berubah. Metode condong cepat jika kita bisa tahan dengan kesalahan, dan skema bitmask tampaknya menjadi pilihan rata-rata yang baik.Kita dapat mengakhiri ini jika kita tidak ingin kembali, melihat kode kita secara kritis dan mengubahnya.Lakukan peningkatan
Hingga saat ini, semua metode eliminasi condong memerlukan penggunaan operasi sisa divisi tambahan, itulah sebabnya mereka dilakukan jauh lebih lambat daripada metode condong. Akan sangat membantu jika kita dapat mengurangi keuntungan ini.Penurunan Berbasis Ambang Lebih Cepat
Beberapa algoritme kami memiliki kode menggunakan nilai ambang, misalnya: uint32_t bounded_rand(rng_t& rng, uint32_t range) {
Ketika rangekecil dibandingkan dengan interval output PRNG, paling sering angkanya akan jauh lebih besar dari ambang. Artinya, jika kita dapat menambahkan perkiraan awal ambang batas, yang mungkin sedikit lebih banyak, kita akan menghemat operasi mahal dengan mengambil sisa divisi.Kode berikut menangani tugas ini: uint32_t bounded_rand(rng_t& rng, uint32_t range) { uint32_t r = rng(); if (r < range) { uint32_t t = (-range) % range; while (r < t) r = rng(); } return r % range; }
Perubahan ini dapat diterapkan pada "Mod ganda tanpa distorsi" (lihat di atas), dan "perkalian integer tanpa distorsi". Gagasan itu ditemukan oleh Lemir, yang menerapkannya pada metode kedua (tetapi tidak pada metode pertama).Hasil Benchmark Acak Besar
Optimalisasi ini mengarah ke peningkatan yang signifikan dalam hasil benchmark 64-bit (di mana mod bahkan lebih lambat), tetapi sebenarnya sedikit menurunkan kinerja dalam benchmark 32-bit. Meskipun ada perbaikan, metode bitmask masih menang.Hasil Tolok Ukur Kecil
Di sisi lain, perubahan ini secara signifikan mempercepat benchmark shuffle kecil untuk metode perkalian bilangan bulat dan metode pembagian sisa ganda. Dalam kedua kasus, kinerjanya bergeser lebih dekat ke hasil opsi tanpa distorsi. Kinerja metode residu ganda (OpenBSD) sekarang hampir sama dengan kinerja metode residu tunggal (Java).Hasil benchmark untuk semua interval
Kami melihat peningkatan yang serupa dalam tolok ukur untuk semua interval.Sepertinya kita dapat mengumumkan pemenang universal baru: metode yang dioptimalkan untuk mengalikan bilangan bulat Lemire tanpa miring.Optimasi sisa divisi
Biasanya, perhitungan a % bmembutuhkan pembagian, tetapi dalam situasi di mana a < bhasilnya sederhana adan pembagian tidak diperlukan. Dan ketika a/2 < b, hasilnya sederhana a - b. Karena itu, alih-alih komputasi a %= b;
kita bisa memenuhi if (a >= b) { a -= b; if (a >= b) a %= b; }
Biaya pembagian sangat signifikan sehingga meningkatkan biaya kode yang lebih kompleks ini dapat membenarkan dirinya sendiri dengan menghemat waktu karena kurangnya pembagian.Hasil Benchmark Acak Besar
Menambahkan pengoptimalan ini sangat meningkatkan hasil tolok ukur besar-acak. Sekali lagi ini lebih terlihat dalam kode 64-bit, di mana operasi mengambil sisanya lebih mahal. Metode double-sisa (gaya OpenBSD) menunjukkan versi dengan optimisasi hanya untuk satu operasi sisa dan untuk keduanya.Dalam tolok ukur ini, topeng bit masih menjadi pemenang, tetapi batas antara itu dan pendekatan Lemira telah menyempit secara signifikan.Hasil Tolok Ukur Kecil
Menambahkan pengoptimalan ini tidak meningkatkan kinerja patokan shuffle kecil, jadi pertanyaannya hanya apakah itu menambah biaya yang signifikan. Dalam beberapa kasus, tidak, dalam kasus lain, biaya sedikit meningkat.Hasil benchmark untuk semua interval
Dalam tolok ukur untuk semua interval, perubahan juga kecil.Bonus: hasil perbandingan PRSP
Alasan utama untuk menggunakan banyak PRNG untuk menguji skema angka dalam interval adalah untuk menghindari distorsi hasil yang tidak disengaja karena kekhasan pengoperasian skema PRNG individu. Tapi kita bisa menggunakan hasil tes internal yang sama untuk membandingkan skema generasi itu sendiri.PRNG dengan output 32-bit
Grafik di bawah ini menunjukkan kinerja berbagai skema generasi 32-bit, rata-rata untuk semua metode dan lima belas langkah, dinormalisasi dengan kinerja 32-bit Mersenne vortex:Di satu sisi, saya senang melihat bahwa pcg32_fastini sangat cepat - hanya dikalahkan oleh versi kecil Xoroshiro (yang tidak lulus tes statistik). Tetapi ini juga menunjukkan mengapa saya jarang marah karena kinerja PRSP tujuan umum modern berkinerja tinggi - perbedaan antara metode yang berbeda sangat tidak signifikan. Secara khusus, empat sirkuit tercepat berbeda dalam kinerja kurang dari 5%, dan saya percaya bahwa ini hanya disebabkan oleh "noise".PRNG dengan output angka 64-bit
Grafik menunjukkan kinerja berbagai skema generasi 64-bit yang dirata-rata di antara semua teknik dan lima belas proses dinormalisasi dengan kinerja 32-bit Mersenne vortex. Mungkin tampak aneh bahwa normalisasi dilakukan menggunakan vortex Mersenne 32-bit, tetapi ini memungkinkan kita untuk melihat biaya tambahan menggunakan generasi 64-bit dalam kasus di mana generasi 32-bit sudah cukup.Hasil ini mengkonfirmasi bahwa ini mcg128_fastsangat cepat, tetapi empat teknik terakhir lagi hanya berbeda sekitar 5%, sehingga sulit untuk memilih dari metode tercepat. pcg64dan pcg64_fastharus lebih lambat mcg128_fast, karena generator dasarnya adalah generator kongruen linier 128-bit (LCG) dan generator kongruen multiplikatif 128-bit (MCG, MCG). Terlepas dari kenyataan bahwa mereka bukan teknik tercepat dalam set ini, mereka pcg64masih 20% lebih cepat dari 64-bit Mersenne vortex.Tetapi mungkin yang lebih penting, hasil ini juga menunjukkan bahwa jika Anda tidak membutuhkan output 64-bit, maka PRNG 64-bit biasanya lebih lambat daripada 32-bit.Kesimpulan
Dari tolok ukur kami, kami dapat melihat bahwa transisi dari PRNG yang digunakan secara standar (misalnya, vortex Mersenne 32-bit) ke PRNP yang lebih cepat mengurangi waktu eksekusi benchmark sebesar 45%. Tetapi transisi dari metode standar untuk menemukan angka dalam interval ke metode tercepat kami memungkinkan kami untuk mengurangi waktu benchmark sekitar 66%; dengan kata lain, hingga sepertiga dari waktu aslinya.Metode tercepat (tanpa distorsi) adalah metode Lemira (dengan optimasi tambahan saya). Ini dia: uint32_t bounded_rand(rng_t& rng, uint32_t range) { uint32_t x = rng(); uint64_t m = uint64_t(x) * uint64_t(range); uint32_t l = uint32_t(m); if (l < range) { uint32_t t = -range; if (t >= range) { t -= range; if (t >= range) t %= range; } while (l < t) { x = rng(); m = uint64_t(x) * uint64_t(range); l = uint32_t(m); } } return m >> 32; }
Menggunakan metode Lemira akan meningkatkan kinerja sebagian besar algoritma acak lebih dari bergerak dari mesin generasi cepat ke yang lebih cepat.Lampiran: Catatan Pengujian
Kode semua tes diposting di GitHub . Secara total, saya menguji 23 metode untuk bounded_randmenggunakan 26 PRN yang berbeda (13 PRN 32-bit dan 13 64-bit), dalam dua kompiler (GCC 8 dan LLVM 6), yang memberi saya 26 * 23 * 2 = 1196 file yang dapat dieksekusi, masing-masing di mana itu dilakukan dengan 15 biji yang sama, yang memberikan 1196 * 15 = 17.940 tes berjalan unik, di mana masing-masing tiga tolok ukur digabungkan. Pada dasarnya, saya menjalankan tes pada mesin 48-core dengan empat prosesor 2,1 GHz Xeon E7-4830v3. Melakukan serangkaian uji penuh memerlukan waktu prosesor kurang dari sebulan.Pada akhirnya, kita kembali ke situasi dari pengantar artikel. Bayangkan bahwa Sasha digunakan jsf32.STD-libc++, dan Juan -mt19937.BIASED_FP_MULT_SCALE. Dalam benchmark 3, yang terakhir membutuhkan waktu 69,6% lebih sedikit. Artinya, waktu dari situasi fiksi ini didasarkan pada data dari kenyataan.