Reproducibility of usize samples across architectures

[dhardy]

One of the CI failures in #792 is:

$ cross test --target mips-unknown-linux-gnu --tests --no-default-features
[...]
---- seq::test::test_slice_choose stdout ----
thread 'main' panicked at 'assertion failed: -20 <= err && err <= 20', src/seq/mod.rs:481:13

This is a deterministic test that passes on x86_64 arches but is now failing on 32-bit MIPS. Why does it fail now? The RNG changed from StdRng (Hc128Rng) to Pcg32, which obviously breaks tests depending on the exact RNG output — this test doesn't, but it does perform a test which only probably succeeds, and happens here not to.

However, it now fails on two architectures (MIPS and ARMv7, both 32-bit). The test uses choose_mut which uses rng.gen_range(0, len) where len: usize... and Pcg32 is a 32-bit RNG with different implementations of gen for 32-bit and 64-bit usize.

Okay, it's kind of obvious that gen::<usize>() is going to be different on different-sized architectures, but it's also a pain. Should we do something about this? @burdges

We probably don't want to impose breaking changes like always forcing gen::<usize>() to use u64 or removing it altogether. And since this function is implemented in the Rng trait (which is automatically implemented for all RngCore) we can't customise it based on the RNG.

Are there any other good options for making things like list.choose(&mut rng) reproducible across architectures?

[dhardy]

It seems the core problem here is not how we generate usize values but that Vec::len's type is arch-dependent. If I am allowed to dream a little, a "solution" would be to have Vec<T, I: Index = u32> (i.e. give all Vecs 32-bit index and capacity by default) — since almost nobody wants arrays larger than 4 GiB and using a Vec is probably not an option on 16-bit machines anyway, this should suit almost everyone except that it's a breaking change.

However, I doubt an RFC with this would fly (even though it lowers memory usage), so it doesn't help us much.

[dhardy]

Maybe there is something we could take advantage of: rng.gen_range(0, len) uses the Uniform implementation for usize — since the len (max parameter) should often be less than u32::MAX, we could test, and use the appropriate path. This trades one extra if to only use a single u32, thus probably has little performance impact (maybe even a gain) and should achieve the goal of deterministic behaviour when sampling lengths.

The drawbacks are that (a) the effect of sampling a usize from a Uniform on an RNG now depends on the value of the parameters (which is already the case for many distributions) and (b) it might have a performance impact on CPUs without good branch prediction (although the if should optimise away on 32-bit platforms, so probably not a big deal).

Obviously it needs benchmarking, but I think this sounds promising?

[burdges]

I agree gen::<usize>() being different sounds unavoidable, but rust devs know usize acts funny.

I also agree rng.gen_range(0, len) and choose should work consistently across architectures. If I understand, you want it to consume only as much randomness as required? That's probably okay.

[dhardy]

For consistency, I think the best solution is to always consume a single u32 except where the upper bound is larger than u32::MAX.

[burdges]

If usize were u16 then you'd need to truncate, not round, but sure. I'd think the real concern is that len < 256 is actually extremely common, so you're paying 2-4 there. oh well

[dhardy]

If usize were u16 then ...

you have 64 kiB address space, so I don't expect you'll be using large libraries like Rand.

Most of our RNGs produce output of 32-bit or larger words, and although the byte-oriented API can theoretically consume smaller amounts of random bits, in practice it's not worth it for performance.

[vks]

I would suggest to document the portability hazard, suggest to use fixed-width integers and casts instead, and close this issue.

Note that #809 made list.choose(&mut rng) portable by using u32 internally if possible.

[dhardy]

Telling users to use casts like rng.gen_range(0, len as u32) as usize is really not very idiomatic, but I guess it's the best we've got for those after reproducibility.

[dhardy]

This is documented here. I guess we can close this issue now.