Remove weak_rng and random?

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?

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

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.

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?

@pitdicker

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

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.

@vks

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+.

@pitdicker

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).

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

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

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.

Just deprecate if possible; you can see several examples of deprecation.

Good point; I advised using thread_rng() primarily because we were using OsRng at the time which can fail; we now have the same fall-back logic for new() though so XorShiftRng::new() is as reliable — but it will be slower if initialising many instances due to extra system calls. I'm not sure; perhaps we should just recommend using new() for odd use-cases but using thread_rng if already in use or if many instances are desired.

Replace `weak_rng()` with new `SmallRng`

@dhardy

@dhardy yeah I understand my "generate a random instance of my type" is whofully underspecified, part of the problem being that I don't know any better. The times I wanted it I really just wanted to forward the rng/distribution my struct's members, eg struct Foo { i: i32, f: f32 }: a random instance of my type is a Foo instance of random i32 and f32.

Trying to stay a bit more on the topic of this issue:

Looking at C#'s Random API, with Rust twist seems quite pleasant:

The function random() -> impl Rng returns an Rng seeded by the system secure rng, the returned rng does not have thread local state. The other constructor to provide a seed can also work eg. random_seeded(seed: &[u8]) -> impl Rng (type of seed argument tbd).

What I'm trying to say is, highly technical terminology and extreme flexibility are fine as long as there's some straight forward convenience methods that map the casual user's expectations.

Part of this suggestions is to drop ThreadRng as the default rng, instead favouring a simple rng initialized with a seed from the system's secure entropy. The specific type of rng returned is not that important, as long as it no longer depends on thread local state.

meta: Is this too far off-topic? I'm not sure. I'm suggesting to change random<T>() -> T (return random instances of T) to random() -> impl Rng (return an rng). This isn't quite what this issue is about though...

I made a PR to undeprecate random(), and took a stab at making the documentation a bit more friendly (at least the landing page of the API reference).

@pitdicker

Thanks @pitdicker

@CasualX @withoutboats The discussion about deprecating Rand and rand_derive is here. We tried to get feedback; most of it ends up being about something else.

random() -> impl Rng

Why? To me random sounds more like "make a random value" than "get a random value generator".

We could rename thread_rng → local_rng or thread_local_rng or something, but I don't see much benefit, though I realise people may find it confusing that the default randomness source is called thread_rng. Or we could rename to strong_rng or crypto_rng or just rng... but the former names are just going to make people wonder where to get randomness when they don't need cryptographic strength, and rng is likely to be used as a field or local variable name.

We already have another type of generator if you don't want one tied to thread-local storage: SmallRng::from_entropy() (similar to the old weak_rng()). This is fine, but there's not normally much reason to use it, hence why thread_rng is the default choice.

@dhardy

@dhardy I was looking at the C# random API where Random is the class name to generate random values, analogous to a random() function to construct the rng. I know it seems odd, but the random identifier is just too good to not use.

The approach C#'s random API takes also solves the performance issue of wrapping thread_rng().gen() in a function as there would be no more wrapping and to the user it's clear what to do next (either they read the docs after discovering random() or the IDE autocompletes the methods on the returned rng).

In short, random() to return an Rng solves several issues: the API is discoverable (search 'random'), performant: no repeated calls to get the rng and usable: random().| (that | is a cursor) will have the IDE autocomplete methods that you want. Further it follows an established API giving some confidence it can work.

@CasualX

@CasualX yes... personally I still hate the idea of using random almost as a verb (to get the thing which makes random values), but your argument has a certain sense to it.

Another thing which crossed my mind is that some applications may not want to use thread_rng — it uses a lot of memory (for e.g. embedded) and is slow to initialise (insignificant in large apps, but maybe an issue in some cases). Right now avoiding this is hard if dependency libs use it. We could however add a feature flag to the Rand crate to use different back-ends instead; e.g. ChaCha uses much less memory and is much faster to initialise, but has slower generation, while SmallRng (and several other RNGs) are small and fast, but not secure. With this in mind we could instead have two functions:

strong_rng(): normally StdRng (Hc128Rng) but optionally instead ChaChaRng
weak_rng(): normally also StdRng (the same instance) but optionally instead SmallRng

These would replace thread_rng but have the same implementation (thread-local auto-reseeding ...).

But is having two functions too confusing?
Is it worth the breakage, given that thread_rng is already widely used?

@dhardy

@dhardy
I think if there are very specific performance requirements, the RNG should be explicitly chosen by the user. Why add so much magic? If we want to have the thread-local auto-reseeding for more RNGs, why not provide it in a generic way?

Libraries should probably never assume any RNG and just consume a &mut Rng given by the user (i.e. the application).

Why add so much magic?

Because there are roughly two main cases, and this caters for them.

Libraries should probably never assume any RNG and just consume a &mut Rng given by the user

Many uses of an RNG are not to "create a random value" (like Distribution::sample) but some internal use; e.g. did you know that HashMap::new() uses an RNG? The only practical API in my opinion is a global function, and since we don't really want to use an unsafe extern(C) function declaration, allowing users to choose an implementation is non-trivial. Also, app developers may sometimes make poor choices (e.g. not realising that some part of their API requires an unpredictable random number).

@LukasKalbertodt

@LukasKalbertodt If you want "quick and dirty but can't cover all the cases" look no further.

@dhardy you can now feel free to abstract and specify to your heart's content ;P

@Lokathor

@Lokathor thanks, but I think there's still benefit in making this lib easy to use!

@dhardy

@dhardy Why not have an opaque wrapper type then? This is nicer than strong_rng() -> impl Rng, which can't be embedded in structs.

Yes, you're right. But this issue has run it's course and I don't think there's any hurry to start tweaking thread_rng (there's no current breaking change, so lets wait until the next release).

I voted not, but I think it should be removed. The main problem would be backward compatibility. So maybe after introducing "editions"?

There's not a strong compatibility issue since we're pre-1.0. Anything below 1.0 can have any change with only a minor version bump.

Replace `weak_rng()` with new `SmallRng`

Navigation Menu

Repository navigation

Remove `weak_rng` and `random`? #289

Performance

Quality

25 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Remove weak_rng and random? #289

Description

Activity

vks commented on Mar 8, 2018

pitdicker commented on Mar 8, 2018

vks commented on Mar 8, 2018

dhardy commented on Mar 8, 2018

dhardy commented on Mar 8, 2018

pitdicker commented on Mar 8, 2018

Performance

Quality

dhardy commented on Mar 9, 2018

vks commented on Mar 9, 2018

dhardy commented on Mar 9, 2018

vks commented on Mar 9, 2018

vks commented on Mar 12, 2018

dhardy commented on Mar 12, 2018

25 remaining items

CasualX commented on May 1, 2018

pitdicker commented on May 1, 2018

dhardy commented on May 1, 2018

CasualX commented on May 1, 2018

dhardy commented on May 1, 2018

vks commented on May 1, 2018

dhardy commented on May 1, 2018

Lokathor commented on May 2, 2018

dhardy commented on May 3, 2018

vks commented on May 3, 2018

dhardy commented on May 3, 2018

jaroslaw-weber commented on May 8, 2018

Lokathor commented on May 8, 2018

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions

Remove `weak_rng` and `random`? #289