SmallRng algorithm

[dhardy]

This type is introduced as follows:

An RNG recommended when small state, cheap initialization and good
performance are required. The PRNG algorithm in SmallRng is chosen to be
efficient on the current platform, without consideration for cryptography
or security. The size of its state is much smaller than for StdRng.

There is general consensus that the current algorithm, Xorshift, is not an ideal choice due to quality (poor results in PractRand and BigCrush) and trivial predictability (to the point that seeding one instance from another effectively creates a clone). Ideally we should replace this for the 0.6 release.

Existing work:

• Move PRNG algorithms out of Rand #431 lists a rough plan for introducing additional generators but does not concern SmallRng directly
• To provide (or not) specific PRNGs? dhardy/rand#58 is an older discussion on the same problem
• Requirements for a small fast RNG dhardy/rand#60 includes detailed evaluations of many candidate algorithms by @pitdicker
• Shootout: small, fast PRNGs dhardy/rand#52 is a parallel discussion to Requirements for a small fast RNG dhardy/rand#60
• pitdicker/small-rngs is a repo implementing these candidates
• Remove weak_rng and random? #289 discusses replacing weak_rng with SmallRng

---

I'm creating this new issue for visibility (most of the previous discussions happened on a fork) and to refresh this issue.

(First note: "reproducible" is used here to mean deterministic, portable, and a commitment not to tweak the algorithm in future updates. All reproducible PRNGs should eventually be migrated out of Rand proper to sub-libs, as discussed in dhardy#58 and #431.)

Question 1: is the current API with two non-reproducible PRNGs, StdRng and SmallRng, the right one? As I understand the current choice is reasonably well accepted, although there have been suggestions to add more categories of PRNG.

Question 2: which algorithm should we use for SmallRng? (The choice may vary by platform.)

[dhardy]

I should ping @pitdicker @vks @huonw @Lokathor @Ichoran who discussed this in the past and @huonw.

dhardy#60 starts with a list of potential requirements for a general-purpose PRNG:

• minimum cycle length and/or number of streams
• minimum state and key size
• quality: passing PractRand and BigCrush (though some have suggested that certain failures should be allowed)
• high speed
• low memory usage
• not trivial to predict
• some theoretical basis
• applicable licence

There is some question of the relative importance of each requirement (small PRNGs are all about trading off quality for speed and low memory usage), but the above is a good starting point.

[dhardy]

We can, if need be, select a different algorithm for Intel x86, x86_64, ARMv7, ARMv8 etc.

It is not so easy to select a different algorithm for u32 generation vs u64 or fill_bytes performance; in theory we could provide e.g. SmallRng32 and SmallRng64, but most likely a single simple choice is better. Users can if necessary benchmark their particular problem on their platform and choose an appropriate algorithm themselves.

[vks]

For now, I would just replace xorshift with PCG or xoshiro. In the long term, we might want to use a SIMD/AES-NI based RNG on platforms where that is possible.

[Lokathor]

You can do a pcg32 as a single 64-bit number. Going smaller than that makes your quality drop off a cliff though.

[dhardy]

As @vks says, lets just select something reasonable for now. From this summary, lets use pcg_xsl_128_mcg for x86_64, and pcg_xsh_64_lcg for x86. These aren't the fastest but never show terrible performance. Note that of the other options here, Xorshift is only listed for performance comparison, SFC is interesting but could do with further analysis, and xoroshiro_mt_64of128 is put together by @pitdicker and deserves further analysis before use. Xoshiro was not analysed here but should be, along with plain 128-bit MCGs and LCGs, but that is a job for another day.

So, a job list, open to all takers:

• create a rand_pcg crate with the above two algorithms, probably based on this code with cross-checking against @imneme's code
• make SmallRng a wrapper around the above algorithms, depending on platform
• (optional) create a rand_sfc crate

Please make these crates sub-directories of the small-rngs repo.

[Lokathor]

Consider that you have 32-bit machines in some places still, so you should probably pick a smaller gen on those machines, the 128 bit based generator is just too much overkill.

[dhardy]

Yes, the 128-bit generator appears to have terrible performance on x86, that's why I suggested we only use it on x86_64 (or 64-bit in general).

[Lokathor]

Ah, right. Forgot the naming for a moment. The only 32-bit machine I've used in ages is rpi boards and similar, which is all 32 bit ARM.

[vks]

Consider that you have 32-bit machines in some places still, so you should probably pick a smaller gen on those machines, the 128 bit based generator is just too much overkill.

There are decent generators with 128 bits of state that use 32 bit arithmetic (i.e. xoshiro). 64 bits of state is not enough for massively parallel applications.

[Lokathor]

I'm fully familiar. PCG32 is in fact one such thing.

[dhardy]

There are decent generators with 128 bits of state that use 32 bit arithmetic (i.e. xoshiro). 64 bits of state is not enough for massively parallel applications.

The one suggested has 127 bits. It relies on PCG streams to achieve this so not ideal, but I think this is acceptable for now.

[Lokathor]

You can also have a PCG32 variant that automatically jumps from stream to stream at some pre-determined point (such as seed = 0), effectively dumping all 127 bits of state into a single stream.

Then again, if you have an important and massively parallel operation I don't think that you'll be using the least capable RNG that still functions that your platform offers.

[dhardy]

We don't need 127 bits of state in a single cycle. But for parallel usage, it's somewhat important that there is a low probability of two randomly-seeded instances are not close to one another, and a 64-bit seed is on the small side here.

[Lokathor]

So, here's your options for Pcg32:

• 64 bits of state and a baked in stream selection. This keeps the generator extremely small but obviously there's concerns to be had in some situations.
• 64 bits of state and 63 bits of stream selection (EDIT: you can even use a NonZero type here to let the compiler use part of that final bit for niche optimization). This is plenty flexible if you want to fork a generator into another thread.
• The exact same generator as above but every time the seed lands on 0 you also jump the stream in some cyclic way, thus effectively making it 127 bits of state.

If none of those are what you want for SmallRNG, then you just don't want PCG32 as your SmallRNG. I'm sure that someone might pick to have as small a state as possible without regard to massively parallel operations. It might be best to worry less about picking particular RNGs for particular specially named RNG types, and just provide all the RNGs you can muster (that are reasonably effective) and then list some pros on each one and then have the rand::rngs have a little table that says "if you want the smallest one we suggest X, if you want to do Y then we suggest Z` and so on. Which is deeply subjective and all that, but it's a lot easier than fretting too much over what's best for every possible use case ever.

[dhardy]

@Lokathor this has all been discussed in various places. #431 has some plans for additional generators and we have a new repo to house these: small-rngs. @pitdicker evaluated the period and chance of overlap last November (see also requirements at the beginning of this issue: ~2^50 words cycle length, ~128 bits state size).

Yes, we want the middle option you suggested.

[dhardy]

FYI: I've started on the rand_pcg crate

[coltfred]

@dhardy I didn't see your post here until now. I've also pushed up a rand_pcg crate which just contains the code @pitdicker wrote, while adjusting it to only depend on RngCore. https://github.com/coltfred/small-rngs/tree/pcg_algos

[dhardy]

Sorry, I actually started a couple of days ago but it took longer than I expected. Perhaps you could take a look at my PR? rust-random/small-rngs#4

[dhardy]

This has now been implemented.