Remove `weak_rng` and `random`?

[dhardy]

Decision:

• Remove random() function
• Replace weak_rng() function with SmallRng wrapper
• Change algorithm used by SmallRng (but off topic here, thus not a blocker for this issue)

---

Both the weak_rng and the random function are little helpers, but don't really do much. To be clear, in the next release users may simply:

• replace random() with thread_rng().gen()
• replace weak_rng() with XorShiftRng::new() (or a different PRNG)

The first is pure convenience (but also a minor anti-pattern since caching the result of thread_rng can improve performance).

The second has a small advantage: users may specify simply that they want a fast, weak PRNG, and don't mind if the implementation changes. XorShiftRng is reproducible, meaning that library updates won't change its output; weak_rng is not reproducible, meaning the library may replace the internals with better generators in the future.

Note that currently weak_rng() returns XorShiftRng which makes changing the former a breaking change; we should introduce a wrapper around the generator used (i.e. fn weak_rng() -> WeakRng) or drop the function and only use a wrapper type (WeakRng::new()).

Note also that thread_rng() is staying because it is widely used and has additional features.

---

We already wish to change the weak_rng algorithm and have two candidates (see dhardy#52 and dhardy#60), so it's possible we could have two variants, e.g. FastRng and SmallRng. This issue is not about which algorithm we choose.

• remove the random() convenience function?
• keep weak_rng() or rename or only keep wrapper types, or remove completely?

[vks]

What is the difference between FastRng and SmallRng? Does small mean 64 bits of state?

[pitdicker]

I completely agree to remove random(), and to replace weak_rng() with a wrapper.

I would not add any more wrappers than ThreadRng, StdRng and SmallRng (somewhat as discussed in dhardy#58).

Than we have a clear story about when to use which:

• StdRng: Good statistical quality, unpredictable. An any situations where there could be an adversary, use this one.
• SmallRng: Good statistical quality, will usually use (much) less memory and be faster than StdRng. But it can be predictable with a little effort.
• ThreadRng: 'managed' StdRng, especially useful when you have no place to hold the state of the RNG.

When we start to add any more wrappers to differentiate between RNGs, where do we stop? Should we have wrappers to differentiate between the memory-efficient, SIMD-capable ChaCha, and the fast, array based HC-128 (both stream cipher based), and the block cipher based AES-CTR DRBG that may have native hardware support? I think we should have just one wrapper for CSPRNGs: StdRng. With the same thinking we should have just one wrapper for 'normal' RNGs.

What is the difference between FastRng and SmallRng? Does small mean 64 bits of state?

SmallRng is a name meant to differentiate it from cryptographic RNGs. It sounds better than 'simple', or 'weak'. And FastRng may sound like a promise to be faster than StdRng, which I don't think we can always keep. In any case 64 bits of state is just not enough for many uses.

[vks]

I agree that it is nice to only have two options, possibly suggesting other, more specialized crates in the documentation.

However, I'm not a fan of the nameSmallRng. This name only makes sense to me if you know the implementation detail that StdRng has a large state, and usually you care more about the speed than the state size. I think SmallRng makes more sense for generators with 64 bits of state, which are useful to initialize generators with a large state.

And FastRng may sound like a promise to be faster than StdRng, which I don't think we can always keep.

Why not? When would StdRng be faster?

[dhardy]

What is the difference between FastRng and SmallRng? Does small mean 64 bits of state?

Yet to be defined and not really on topic here (it's partly a compromise since you two can't seem to agree on which PRNG to make default). But I agree with @pitdicker that it doesn't make much sense having two.

According to the benchmarks HC-128 is not much slower faster than Xorshift in some cases anyway, though it takes up much more memory. I think SmallRng is a reasonable name based on this:

test gen_bytes_hc128       ... bench:     441,867 ns/iter (+/- 15,706) = 2317 MB/s
test gen_bytes_xorshift    ... bench:   1,138,435 ns/iter (+/- 65,539) = 899 MB/s
test gen_u32_hc128         ... bench:       2,943 ns/iter (+/- 252) = 1359 MB/s
test gen_u32_xorshift      ... bench:       4,383 ns/iter (+/- 142) = 912 MB/s
test gen_u64_hc128         ... bench:       4,309 ns/iter (+/- 255) = 1856 MB/s
test gen_u64_xorshift      ... bench:       2,879 ns/iter (+/- 129) = 2778 MB/s
test init_hc128            ... bench:       4,518 ns/iter (+/- 308)
test init_xorshift         ... bench:          23 ns/iter (+/- 0)
Size of Hc128Rng: 4176
Size of XorShiftRng: 16

[dhardy]

You can also see the benchmarks I did on my ARM v7 phone where Xorshift is definitely faster, if you want more context. Any way you look at it though, the biggest reason not to use a cryptographic generator would seem to be the size of the PRNG; this is more significant if multiple PRNGs are used.

[pitdicker]

I think it is going to be difficult for you @vks and me to find agreement, because we look at it in a different way.

I think we can basically agree that all the known RNG algorithms are looking for the best balance between generating numbers as fast as possible, with simple code, and having the numbers look as 'random' as possible. The quest for performance is a very practical concern, and that which mostly interest @vks. The quest for quality is what has driven many of the 'big names' and developments behind RNGs, like George Marsaglia and Pierre L’Ecuyer, and is what I prefer.

As I have said again, I have nothing (well, almost) against Xoroshiro128+. It is great for many situations, like generating many floating-point values. Both Xoroshiro128+ and PCG definitely have a place.

Performance

On one hand, I care quite a bit about performance (@dhardy can confirm the effort I have spent optimizing stuff in rand 😄). But the raw performance of the RNGs does not seem to matter all that much in the end... I have collected a few benchmarks:

Raw performance generating u64:

test gen_u64_xoroshiro_128_plus ... bench:       1,079 ns/iter (+/- 3) = 7414 MB/s
test gen_u64_xoroshiro_mt       ... bench:       1,236 ns/iter (+/- 24) = 6472 MB/s
test gen_u64_pcg_xsh_64_lcg     ... bench:       3,578 ns/iter (+/- 30) = 2235 MB/s
test gen_u64_pcg_xsl_128_mcg    ... bench:       1,467 ns/iter (+/- 18) = 5453 MB/s

Adding a tiny bit of use: converting to an f64:

test gen_f64_xoroshiro_128_plus ... bench:       1,316 ns/iter (+/- 3) = 6079 MB/s
test gen_f64_xoroshiro_mt       ... bench:       2,659 ns/iter (+/- 18) = 3008 MB/s
test gen_f64_pcg_xsh_64_lcg     ... bench:       3,852 ns/iter (+/- 2) = 2076 MB/s
test gen_f64_pcg_xsl_128_mcg    ... bench:       1,788 ns/iter (+/- 1) = 4474 MB/s

Generating an f64 range:

test range_0_10_xoroshiro_128_plus ... bench:       2,442 ns/iter (+/- 15) = 3276 MB/s
test range_0_10_xoroshiro_mt       ... bench:       2,891 ns/iter (+/- 9) = 2767 MB/s
test range_0_10_pcg_xsh_64_lcg     ... bench:       3,897 ns/iter (+/- 52) = 2052 MB/s
test range_0_10_pcg_xsl_128_mcg    ... bench:       2,857 ns/iter (+/- 26) = 2800 MB/s

Generating numbers in a distribution (Normal using the Ziggurat algorithm)

test gen_normal_xoroshiro_128_plus ... bench:       5,224 ns/iter (+/- 16) = 1531 MB/s
test gen_normal_xoroshiro_mt       ... bench:       5,595 ns/iter (+/- 25) = 1429 MB/s
test gen_normal_pcg_xsh_64_lcg     ... bench:       7,344 ns/iter (+/- 32) = 1089 MB/s
test gen_normal_pcg_xsl_128_mcg    ... bench:       6,746 ns/iter (+/- 52) = 1185 MB/s

Generating integers in a range:

test gen_u64_xoroshiro_128_plus ... bench:       2,486 ns/iter (+/- 25) = 3218 MB/s
test gen_u64_xoroshiro_mt       ... bench:       3,086 ns/iter (+/- 25) = 2592 MB/s
test gen_u64_pcg_xsh_64_lcg     ... bench:       4,170 ns/iter (+/- 7) = 1918 MB/s
test gen_u64_pcg_xsl_128_mcg    ... bench:       2,671 ns/iter (+/- 28) = 2995 MB/s

So converting the output of the RNG into a number you can actually use in your code often already halves the performance, and then you are not even using it meaningfully yet! Still, in these benchmarks Xoroshiro128+ is often 20% faster than PCG-XSL-128, and that is not a number to ignore. But that number only keeps getting lower when you consider the real-world surrounding code.

Quality

I think a must read when talking about RNG quality is the paper '"Good random number generators are (not so) easy to find"](http://random.mat.sbg.ac.at/results/peter/A19final.pdf) by P. Hellekalek. The best way to make sure an RNG is suitable for many kinds of different uses is by measuring how well it performs on the RNG test suites designed for this (TestU01 and PractRand). And to be honest I don't know how all the tests they perform map to which real-world situations.

To be honest again there is one thing that I have against Xoroshiro, and that is its design history. Sebastiano Vigna did valuable work by improving existing Xorshift variants. His method was to run the TestU01 benchmarks countless times, to figure out the best constants to use in Xorshift* and Xorshift+. But this is basically optimising an RNG to pass a specific test suite. When another one came along, PractRand, it failed instantly. And also when others began testing and evaluating Xorshift+ and Xoroshiro+ it turned out to pass tests a less often. This indicates there are situations for which Xoroshiro128+ is not the best choice.

PCG was also designed in combination with the TestU01 test suite, but with a much stronger theoretical basis. It really strives to remove any kinds of patterns. And, as in proper testing, kept weakening the RNG to figure out how much headroom there is before the tests actually fail. This explains why when the other test suite came along (PractRand) there where no problems.

One argument to prefer better quality over performance is one I have seen in several other discussion in the Rust forums. One aspect is very easy to test and measure, the other very difficult. It is very easy to measure whether the PRNG you use is a performance bottleneck. It is very hard to test and measure whether the random numbers that get generated are as 'random' as you expect them to be. That is why I would like to see both, but make the 'safest choice' the default.

Edit: one more think I would like to mention when it comes to quality is that I have spent effort to make the float conversion code, generating bools, and generating integer ranges avoid the weaker bits of Xoroshiro128+. There where real algorithms that needed changing. But I wanted rand to be safe to use as much as possible with RNGs like Xoroshiro128+.

[dhardy]

I think you're getting off the original topic there @pitdicker. Yes, I can confirm you have done a lot of optimisation work! I didn't want to discuss which algorithm we pick here because we already have at least two threads about that — perhaps you'd like to copy your post elsewhere?

@vks are you happy to use the name SmallRng now? Really small size and single-value-generation are the defining characteristics of these "non cryptographic PRNGs" and I prefer categorising by positive characteristics, not negative ones (you don't select an algorithm for an application based on which properties it doesn't have).

[vks]

Yet to be defined and not really on topic here (it's partly a compromise since you two can't seem to agree on which PRNG to make default).

I agree it is better to have just one. I don't feel strongly about the default, PCG is close enough to my personal optimum, and it is very easy for me to use another RNG.

@vks are you happy to use the name SmallRng now?

Yes, I'm convinced now. It is a good name to distinguish such generators from faster ones with larger state (e.g. xorshift1024 is faster than xorshift128).

[dhardy]

I added a tracker to the top. Anyone want to implement the first two items?

[vks]

I'm interested. I'll try to get a PR done until Monday.

[vks]

Should I remove the functions or just deprecate them?

Another problem is that weak_rng() is not equivalent to XorShiftRng::new(), because it uses thread_rng() to initialize the generator.