Adding a wyrand-based PRNG?

[hoxxep]

I recently spun rapidrand out of rapidhash and decided to benchmark and test it properly. It's a wyrand construction, and so perhaps could be argued that it's theoretically weaker than xoshiro++, but it still passes BigCrush and PractRand at 16TB and is twice as fast as xoshiro++ and SmallRng.

For non-cryptographic use cases, would we be interested in a rust-random wyrand implementation? I'm happy to create a PR in the rust-random/rng style adding a wyrand PRNG?

Benchmarks

M1 Max

RNG	u64	u32	fill 1 KiB
rapidrand RapidRng	0.51 ns	0.51 ns	21.67 GB/s
fastrand Rng*	0.51 ns	0.52 ns	21.49 GB/s
turborand Rng*	1.25 ns	0.51 ns	21.56 GB/s
nanorand WyRand*	0.51 ns	0.51 ns	3.57 GB/s
rand SmallRng	1.13 ns	1.20 ns	7.05 GB/s
rand_xoshiro Xoshiro256PlusPlus	1.14 ns	1.19 ns	7.04 GB/s
rand_xoshiro Xoshiro256StarStar	1.30 ns	1.37 ns	5.84 GB/s
rand_pcg Pcg32	2.06 ns	1.02 ns	3.93 GB/s
rand_pcg Pcg64	1.64 ns	1.65 ns	4.81 GB/s
rand StdRng (ChaCha12)	4.11 ns	2.26 ns	2.02 GB/s
rand_chacha ChaCha8Rng	5.86 ns	3.04 ns	1.45 GB/s
rand_chacha ChaCha20Rng	13.24 ns	6.70 ns	0.62 GB/s

*wyrand-based PRNGs that use their own random traits outside of the rust-random ecosystem.

DigitalOcean x86 droplet (Intel, CPU-optimized, dedicated vCPU)

RNG	u64	u32	fill 1 KiB
rapidrand RapidRng	0.62 ns	0.62 ns	7.97 GB/s
fastrand Rng	0.62 ns	0.62 ns	7.99 GB/s
nanorand WyRand	0.62 ns	0.62 ns	2.57 GB/s
rand SmallRng	1.18 ns	1.21 ns	6.62 GB/s
rand_xoshiro Xoshiro256PlusPlus	1.17 ns	1.21 ns	6.61 GB/s
rand_xoshiro Xoshiro256StarStar	1.26 ns	1.19 ns	6.92 GB/s
turborand Rng	2.10 ns	2.06 ns	8.04 GB/s
rand_chacha ChaCha8Rng	2.51 ns	1.44 ns	4.31 GB/s
rand_pcg Pcg64	2.08 ns	2.07 ns	4.14 GB/s
rand_pcg Pcg32	2.78 ns	1.31 ns	2.96 GB/s
rand StdRng (ChaCha12)	3.22 ns	1.88 ns	2.88 GB/s
rand_chacha ChaCha20Rng	5.00 ns	2.74 ns	1.83 GB/s

[dhardy]

I added rapidrand to the rngs benchmarks and ran on my 5800X. Numbers are cycles-per-byte.

RNG	u32	u64	bytes
rapidrand	0.56	0.27	0.34
splitmix64	0.63	0.39	0.42
chacha8	0.89	0.75	0.56
sfc64	0.78	0.30	0.41
xoshiro128plusplus	0.64	0.71	0.69
xoshiro256plus	0.61	0.29	0.29
xoshiro256plusplus	0.73	0.33	0.35
xoshiro256starstar	0.72	0.35	0.34
pcg32	0.90	0.84	0.81
pcg64	1.14	0.59	0.63
pcg64mcg	0.89	0.47	0.51

So fast, but not anomalously fast like your benchmarks suggest. Or maybe Apple M1 is weird (wouldn't be the first time I've seen it benchmarks quite differently).

In case you want to run yourself, here's a patch for this repo: https://gist.github.com/dhardy/273ef9d0f68a67a58a233f8ea3ca9651

CC @vigna

[vigna]

There's some bias finding going on with WyRand real now, unleashed by my proposal to replace it in fastrand because it fails collisions tests. Maybe you can consider one of the fixed versions @reinerp is designing.

You can also try to see whether rapidrand has similar problem using my crate for large-scale collision tests. You can run tests traditionally needing dozens of terabytes on a standard workstation. You should at least be able to pass PractRact with -tf 2 -te 1 at 32TB and a collision test for the same amount to data (i.e., 4T 64-bit points).

[hoxxep]

@dhardy I added x86 wall-time benchmarks to my original comment to compare, which still show an improvement, but the 1kb uplift is much more modest. I can't run criterion-cycles-per-byte on macOS sadly, and rented servers mostly deny the rdpru instruction and I don't have an x86 machine to hand, so I can't get a reliable cycles-per-byte reading.

@vigna funny that between glancing at the wyhash repo last night and releasing rapidrand that @reinerp has submitted an improvement. I agree his structure looks better, and that's interesting to know the minimums for PractRand. I'll review and implement the new version, run the expected tests, and report back in a few days, thanks.

[vks]

The benchmarks look quite noisy. Why is ChaCha12 faster than ChaCha8?

[hoxxep]

@vks those are implementation differences, not benchmark noise.

RandStd uses RustCrypto's chacha20 crate for ChaCha12, which is heavily optimised with sse2 and avx2 backends. While the ChaCha20 and ChaCha8 benchmarks are using rust-random's rand_chacha crate.