Shootout: small, fast PRNGs

[dhardy]

We've already had a lot of discussion on this. Lets summarise algorithms here.

This is about small, fast PRNGs. Speed, size and performance in tests like PractRand and TestU01 is of interest here; cryptographic quality is not.

---

Edit: see @pitdicker's work in #60.

[vks]

I have some benchmarks:

test rand_bytes_aes           ... bench:   8,389,735 ns/iter (+/- 273,533) = 124 MB/s              
test rand_bytes_chacha        ... bench:   3,691,665 ns/iter (+/- 101,794) = 284 MB/s              
test rand_bytes_isaac         ... bench:   2,043,659 ns/iter (+/- 93,872) = 513 MB/s               
test rand_bytes_isaac64       ... bench:   1,272,982 ns/iter (+/- 79,964) = 823 MB/s               
test rand_bytes_splitmix      ... bench:     245,919 ns/iter (+/- 12,513) = 4263 MB/s              
test rand_bytes_xoroshiro     ... bench:     334,576 ns/iter (+/- 24,947) = 3134 MB/s              
test rand_bytes_xoroshirostar ... bench:     430,575 ns/iter (+/- 64,488) = 2435 MB/s              
test rand_bytes_xorshift      ... bench:   1,306,342 ns/iter (+/- 95,741) = 802 MB/s               
test rand_bytes_xorshift1024  ... bench:     364,495 ns/iter (+/- 21,676) = 2876 MB/s              
test rand_u64_aes             ... bench:   6,385,340 ns/iter (+/- 289,658) = 125 MB/s              
test rand_u64_chacha          ... bench:   2,224,053 ns/iter (+/- 130,170) = 359 MB/s              
test rand_u64_isaac           ... bench:   1,038,451 ns/iter (+/- 93,778) = 770 MB/s               
test rand_u64_isaac64         ... bench:     370,893 ns/iter (+/- 27,691) = 2156 MB/s              
test rand_u64_splitmix        ... bench:     108,328 ns/iter (+/- 6,140) = 7384 MB/s               
test rand_u64_xoroshiro       ... bench:      85,963 ns/iter (+/- 4,069) = 9306 MB/s               
test rand_u64_xoroshirostar   ... bench:      98,519 ns/iter (+/- 4,330) = 8120 MB/s               
test rand_u64_xorshift        ... bench:     212,814 ns/iter (+/- 6,618) = 3759 MB/s               
test rand_u64_xorshift1024    ... bench:     274,191 ns/iter (+/- 7,599) = 2917 MB/s

However, I don't trust them that much, because I experienced systematic differences just by reordering the benchmarks.

[dhardy]

Added XorShiftRng. PractRand results:

$ target/debug/examples/cat_rng xorshift | practrand stdin
RNG_test using PractRand version 0.93
RNG = RNG_stdin, seed = 0xa4893a88
test set = normal, folding = standard(unknown format)

rng=RNG_stdin, seed=0xa4893a88
length= 64 megabytes (2^26 bytes), time= 3.3 seconds
  Test Name                         Raw       Processed     Evaluation
  BRank(12):256(2)                  R= +3748  p~=  3e-1129    FAIL !!!!!!!!  
  BRank(12):384(1)                  R= +5405  p~=  3e-1628    FAIL !!!!!!!!  
  BRank(12):512(2)                  R=+11541  p~=  2e-3475    FAIL !!!!!!!!  
  BRank(12):768(1)                  R=+13672  p~=  1e-4116    FAIL !!!!!!!!  
  BRank(12):1K(1)                   R=+19183  p~=  1e-5775    FAIL !!!!!!!!  
  [Low1/8]BRank(12):128(2)          R= +1312  p~=  5.4e-396   FAIL !!!!!!!   
  [Low1/8]BRank(12):256(2)          R= +3748  p~=  3e-1129    FAIL !!!!!!!!  
  [Low1/8]BRank(12):384(1)          R= +5405  p~=  3e-1628    FAIL !!!!!!!!  
  [Low1/8]BRank(12):512(1)          R= +8161  p~=  1e-2457    FAIL !!!!!!!!  
  [Low4/32]BRank(12):256(2)         R= +3748  p~=  3e-1129    FAIL !!!!!!!!  
  [Low4/32]BRank(12):384(1)         R= +5405  p~=  3e-1628    FAIL !!!!!!!!  
  [Low4/32]BRank(12):512(1)         R= +8161  p~=  1e-2457    FAIL !!!!!!!!  
  [Low1/32]BRank(12):256(2)         R= +3748  p~=  3e-1129    FAIL !!!!!!!!  
  [Low1/32]BRank(12):384(1)         R= +5405  p~=  3e-1628    FAIL !!!!!!!!  
  ...and 125 test result(s) without anomalies

[dhardy]

@vks quite possibly you should call black_box on your buf after this line.

But anyway this is about much more than just speed. Which in particular do you think I should test?

[vks]

I think the most interesting ones are xoroshiro128+ and xorshift1024*, as suggested by Vigna. I don't have an opinion on cryptographic generators.

It is important to understand what the binary rank test does when judging the failures, see http://xoroshiro.di.unimi.it/:

In all papers describing these generators, the authors (including Marsaglia itself) consider the failure of the binary-rank test irrelevant from a practical viewpoint, as the output of the generator is used as a number, not as a vector on Z/2Z.

(I did not look up Marsaglia's paper to verify this claim.)

[dhardy]

I adapted your crate to use rand_core and ran some tests.

Interestingly SplitMix64 does very well on PractRand. I should look at running TestU01 too.

In light of your arguments about binary rank tests, it might be interesting to try PractRand with those disabled (if it has other useful tests). But I am not convinced we should ignore them entirely.

Test output:

14:40 dhardy@localhost:~/rust/rand$ target/release/examples/cat_rng SplitMix64 | practrand stdin
RNG_test using PractRand version 0.93
RNG = RNG_stdin, seed = 0x3be4c794
test set = normal, folding = standard(unknown format)

rng=RNG_stdin, seed=0x3be4c794
length= 256 megabytes (2^28 bytes), time= 3.4 seconds
  no anomalies in 162 test result(s)

rng=RNG_stdin, seed=0x3be4c794
length= 512 megabytes (2^29 bytes), time= 7.2 seconds
  no anomalies in 171 test result(s)

rng=RNG_stdin, seed=0x3be4c794
length= 1 gigabyte (2^30 bytes), time= 14.5 seconds
  no anomalies in 183 test result(s)

rng=RNG_stdin, seed=0x3be4c794
length= 2 gigabytes (2^31 bytes), time= 28.5 seconds
  no anomalies in 194 test result(s)

rng=RNG_stdin, seed=0x3be4c794
length= 4 gigabytes (2^32 bytes), time= 55.7 seconds
  no anomalies in 203 test result(s)

rng=RNG_stdin, seed=0x3be4c794
length= 8 gigabytes (2^33 bytes), time= 111 seconds
  no anomalies in 215 test result(s)

rng=RNG_stdin, seed=0x3be4c794
length= 16 gigabytes (2^34 bytes), time= 219 seconds
  no anomalies in 226 test result(s)

rng=RNG_stdin, seed=0x3be4c794
length= 32 gigabytes (2^35 bytes), time= 434 seconds
  Test Name                         Raw       Processed     Evaluation
  DC6-9x1Bytes-1                    R=  +4.9  p =  2.8e-3   unusual          
  ...and 234 test result(s) without anomalies

^C
14:50 dhardy@localhost:~/rust/rand$ target/release/examples/cat_rng XoroShiro128 | practrand stdin
RNG_test using PractRand version 0.93
RNG = RNG_stdin, seed = 0xa6ddb56d
test set = normal, folding = standard(unknown format)

rng=RNG_stdin, seed=0xa6ddb56d
length= 256 megabytes (2^28 bytes), time= 3.4 seconds
  Test Name                         Raw       Processed     Evaluation
  [Low1/32]BRank(12):384(1)         R= +1272  p~=  5.4e-384   FAIL !!!!!!!   
  [Low1/32]BRank(12):512(1)         R= +2650  p~=  9.8e-799   FAIL !!!!!!!   
  ...and 160 test result(s) without anomalies

thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: Error { repr: Os { code: 32, message: "Broken pipe" } }', /checkout/src/libcore/result.rs:860:4
note: Run with `RUST_BACKTRACE=1` for a backtrace.
14:50 dhardy@localhost:~/rust/rand$ target/release/examples/cat_rng XorShift1024 | practrand stdin
RNG_test using PractRand version 0.93
RNG = RNG_stdin, seed = 0x1575d306
test set = normal, folding = standard(unknown format)

rng=RNG_stdin, seed=0x1575d306
length= 256 megabytes (2^28 bytes), time= 3.4 seconds
  no anomalies in 162 test result(s)

rng=RNG_stdin, seed=0x1575d306
length= 512 megabytes (2^29 bytes), time= 7.2 seconds
  no anomalies in 171 test result(s)

rng=RNG_stdin, seed=0x1575d306
length= 1 gigabyte (2^30 bytes), time= 14.6 seconds
  no anomalies in 183 test result(s)

rng=RNG_stdin, seed=0x1575d306
length= 2 gigabytes (2^31 bytes), time= 28.9 seconds
  no anomalies in 194 test result(s)

rng=RNG_stdin, seed=0x1575d306
length= 4 gigabytes (2^32 bytes), time= 56.0 seconds
  no anomalies in 203 test result(s)

rng=RNG_stdin, seed=0x1575d306
length= 8 gigabytes (2^33 bytes), time= 112 seconds
  Test Name                         Raw       Processed     Evaluation
  [Low1/8]FPF-14+6/16:cross         R=  +4.7  p =  2.7e-4   unusual          
  ...and 214 test result(s) without anomalies

rng=RNG_stdin, seed=0x1575d306
length= 16 gigabytes (2^34 bytes), time= 221 seconds
  no anomalies in 226 test result(s)

rng=RNG_stdin, seed=0x1575d306
length= 32 gigabytes (2^35 bytes), time= 436 seconds
  Test Name                         Raw       Processed     Evaluation
  [Low4/32]BCFN(2+1,13-0,T)         R=  +7.4  p =  1.7e-3   unusual          
  [Low1/32]BRank(12):3K(1)          R=+10916  p~=  3e-3287    FAIL !!!!!!!!  
  ...and 233 test result(s) without anomalies

thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: Error { repr: Os { code: 32, message: "Broken pipe" } }', /checkout/src/libcore/result.rs:860:4
note: Run with `RUST_BACKTRACE=1` for a backtrace.

[vks]

Splitmix64 is recommended by Vigna for seeding xoroshiro128+ and xorshift1024*. It works with any seed (even zero), but it has a period of 2^64 which might be a bit short.

[pitdicker]

I have done a lot of experiments on Xoroshiro128+, SplitMix etc.

Xoroshiro128+ is always the fastest, with a margin of up to 20%. But it has several weaknesses, and should be used with a lot of care unless you use it to generate f32's of f64's.

I personally like truncated Xorshift*, and PCG. I have optimized and well-tested implementations here that are mostly ready. They are flawless under PractRand and TestU01.

Benchmarks from a month ago:

2017-10-15 8:30 x86_64
test gen_u32_chacha            ... bench:      10,821 ns/iter (+/- 807) = 369 MB/s
test gen_u32_isaac             ... bench:       4,192 ns/iter (+/- 4) = 954 MB/s
test gen_u32_isaac64           ... bench:       4,238 ns/iter (+/- 23) = 943 MB/s
test gen_u32_pcg               ... bench:       1,223 ns/iter (+/- 10) = 3270 MB/s
test gen_u32_pcg64             ... bench:       1,940 ns/iter (+/- 7) = 2061 MB/s
test gen_u32_xorshift          ... bench:       1,084 ns/iter (+/- 8) = 3690 MB/s
test gen_u32_xorshiftmult      ... bench:       1,127 ns/iter (+/- 3) = 3549 MB/s
test gen_u32_xorshiftmult32    ... bench:       1,121 ns/iter (+/- 2) = 3568 MB/s
test gen_u32_xorshiftmult64_32 ... bench:       1,686 ns/iter (+/- 18) = 2372 MB/s
test gen_u32_truncated_xorshift64star   ... bench:       1,720 ns/iter (+/- 7) = 2325 MB/s
test gen_u32_xoroshiro128plus           ... bench:       1,083 ns/iter (+/- 5) = 3693 MB/s
test gen_u32_xorshift128                ... bench:       1,000 ns/iter (+/- 4) = 4000 MB/s
test gen_u32_xorshift128plus            ... bench:       1,110 ns/iter (+/- 6) = 3603 MB/s

test gen_u64_chacha            ... bench:      21,445 ns/iter (+/- 95) = 373 MB/s
test gen_u64_isaac             ... bench:       8,123 ns/iter (+/- 56) = 984 MB/s
test gen_u64_isaac64           ... bench:       4,229 ns/iter (+/- 13) = 1891 MB/s
test gen_u64_pcg               ... bench:       3,544 ns/iter (+/- 19) = 2257 MB/s
test gen_u64_pcg64             ... bench:       1,942 ns/iter (+/- 10) = 4119 MB/s
test gen_u64_xorshift          ... bench:       2,639 ns/iter (+/- 5) = 3031 MB/s
test gen_u64_xorshiftmult      ... bench:       1,313 ns/iter (+/- 4) = 6092 MB/s
test gen_u64_xorshiftmult32    ... bench:       3,415 ns/iter (+/- 4) = 2342 MB/s
test gen_u64_xorshiftmult64_32 ... bench:       4,385 ns/iter (+/- 18) = 1824 MB/s
test gen_u64_truncated_xorshift64star   ... bench:       4,522 ns/iter (+/- 18) = 1769 MB/s
test gen_u64_xoroshiro128plus           ... bench:       1,083 ns/iter (+/- 4) = 7386 MB/s
test gen_u64_xorshift128                ... bench:       1,000 ns/iter (+/- 4) = 8000 MB/s
test gen_u64_xorshift128plus            ... bench:       1,111 ns/iter (+/- 3) = 7200 MB/s


2017-10-15 8:30 x86
test gen_u32_chacha            ... bench:      17,217 ns/iter (+/- 59) = 232 MB/s
test gen_u32_isaac             ... bench:       4,238 ns/iter (+/- 26) = 943 MB/s
test gen_u32_isaac64           ... bench:       5,825 ns/iter (+/- 32) = 686 MB/s
test gen_u32_pcg               ... bench:       3,034 ns/iter (+/- 4) = 1318 MB/s
test gen_u32_pcg64             ... bench:      13,564 ns/iter (+/- 162) = 294 MB/s
test gen_u32_xorshift          ... bench:       1,470 ns/iter (+/- 8) = 2721 MB/s
test gen_u32_xorshiftmult      ... bench:       2,923 ns/iter (+/- 9) = 1368 MB/s
test gen_u32_xorshiftmult32    ... bench:       1,729 ns/iter (+/- 2) = 2313 MB/s
test gen_u32_xorshiftmult64_32 ... bench:       2,392 ns/iter (+/- 3) = 1672 MB/s
test gen_u32_truncated_xorshift64star ... bench:       2,715 ns/iter (+/- 11) = 1473 MB/s
test gen_u32_xoroshiro128plus         ... bench:       1,955 ns/iter (+/- 9) = 2046 MB/s
test gen_u32_xorshift128              ... bench:       2,303 ns/iter (+/- 12) = 1736 MB/s
test gen_u32_xorshift128plus          ... bench:       2,434 ns/iter (+/- 8) = 1643 MB/s

test gen_u64_chacha            ... bench:      35,559 ns/iter (+/- 131) = 224 MB/s
test gen_u64_isaac             ... bench:       8,924 ns/iter (+/- 51) = 896 MB/s
test gen_u64_isaac64           ... bench:       5,961 ns/iter (+/- 126) = 1342 MB/s
test gen_u64_pcg               ... bench:       5,926 ns/iter (+/- 504) = 1349 MB/s
test gen_u64_pcg64             ... bench:      14,957 ns/iter (+/- 20,628) = 534 MB/s
test gen_u64_xorshift          ... bench:       4,590 ns/iter (+/- 120) = 1742 MB/s
test gen_u64_xorshiftmult      ... bench:      11,678 ns/iter (+/- 702) = 685 MB/s
test gen_u64_xorshiftmult32    ... bench:       3,983 ns/iter (+/- 49) = 2008 MB/s
test gen_u64_xorshiftmult64_32 ... bench:       5,882 ns/iter (+/- 82) = 1360 MB/s
test gen_u64_truncated_xorshift64star ... bench:       6,250 ns/iter (+/- 53) = 1280 MB/s
test gen_u64_xoroshiro128plus         ... bench:       2,436 ns/iter (+/- 3) = 3284 MB/s
test gen_u64_xorshift128              ... bench:       2,512 ns/iter (+/- 18) = 3184 MB/s
test gen_u64_xorshift128plus          ... bench:       2,932 ns/iter (+/- 11) = 2728 MB/s

[pitdicker]

The Xorshift variants in table form:

algorithm	native	result	u32	u64	quality	notes
xorshift128/32	32-bit	u32	3693 MB/s	3034 MB/s	bad	current implementation
xorshift64/32*_truncated	32-bit	u32	3561 MB/s	2339 MB/s	excellent	(-3,6%, -22,9%)
xorshift128/32*_truncated	32-bit	u32	3270 MB/s	2536 MB/s	excellent	(-11,4%, -16,4%)
xorshift128/64*_truncated	64-bit	u64	3125 MB/s	6309 MB/s	excellent	needs 128-bit support
xorshift128/64	64-bit	u64	4000 MB/s	8016 MB/s	bad
xorshift64*	64-bit	u64	2415 MB/s	4828 MB/s	good
xorshift64*_truncated	64-bit	u32	2324 MB/s	1772 MB/s	excellent
xorshift128+	64-bit	u64	3603 MB/s	7207 MB/s	passable
xoroshiro128+	64-bit	u64	3690 MB/s	7380 MB/s	passable

[pitdicker]

As @vks says the period of SplitMix is much to small to be used as a general PRNG. Unless we also use streams, that come with their own set of problems.

[vks]

I'm not sure xoroshiro's failures of the binary rank test qualify as a weakness in practice, see this discussion.

[pitdicker]

I saw it after my post 😄.

This is from memory, but I ran Xoroshiro+ through test, and disabled the binary rank tests. There were other ones it failed also. I also tested it by reversing the bits, but don't remember the results.

Simply put, it doesn't mix (avalance) its bits enough. Xorshift (or plain Xoroshiro, if that were a thing) have patterns. A simple addition reduces those patterns, but is not enough to remove them. Something like a multiply should be used instead. Using a large state also helps masking those patterns.

Not to say that I don't think Xoroshiro+ can have it's uses. Xorshift has it use too. Especially when converted to floating point, weaker least significant digits should just about never be interesting. But any user of it should be careful.

@dhardy already raised good points. Do you know the impact of the weaker bits on: (1) generating booleans, (2) the ziggurat table lookup, (3) sampling from a range, (4) our custom, high precision conversions to double? And that are just a few uses in rand. Now it may be useful to handle weaker RNG's nicely anyway in the case of rand.

For general use, I think there are better PRNG's we can go with. Then we can have a simple guideline: if you need a good RNG but don't need to worry about predictability (e.g. no adversaries), use Xorshift* or PCG. If you need unpredictability, use a cryptographic RNG.

Of course performance is a thing. But I consider anything that is on average close to / better than our current Xorshift extremely fast and good enough.

[vks]

Xorshift (or plain Xoroshiro, if that were a thing) have patterns.

What kind of patterns? If I understand correctly, all linear generators have patterns, the question is whether they are observable.

Something like a multiply should be used instead.

Why? (Are you basing this on O'Neill's blog post?) It's not clear that this is better. I recently had an email exchange with Sebastiano Vigna about the merits of xoroshiro* compared to xoroshiro+. He did some experiments, showing that xoroshiro+ has some Hamming dependencies after a lot of values, in this regard xoroshiro* is slightly better. But the lowest two bits of xoroshiro* are the same LSFR, while for xoroshiro+ the second lowest bit is a perturbed LSFR, so in that regard xoroshiro+ is slightly better.

Using a large state also helps masking those patterns.

I'm not sure which patterns you mean, but the linear dependencies don't go away by using a larger state. Large states also have trouble to recover from lots of zeros in the initial state and require more careful seeding.

Do you know the impact of the weaker bits

Well, empirically there seems to be no practical impact whatsoever. All popular RNGs (that is the Mersenne Twister for most programming languages and xorshift for browsers and the current rand crate) are an LSFR in all bits. AFAIK, the only known impact is on the calculation of the rank of random binary matrices. You are saying users should be careful about the linear dependencies. Why?

if you need a good RNG but don't need to worry about predictability (e.g. no adversaries), use Xorshift* or PCG.

Xorshift* linear dependencies in the lowest two bits as well. I don't see a reason why to use it over xoroshiro+, unless you are talking about xorshift1024* vs. xoroshiro128+.

Of course performance is a thing. But I consider anything that is on average close to / better than our current Xorshift extremely fast and good enough.

On the other hand, performance is the only reason to use such a generator over a cryptographic one.

[pitdicker]

What kind of patterns? If I understand correctly, all linear generators have patterns, the question is whether they are observable.

Completely agree. And if they are observable depends on how the random numbers are used.

From the first paper by Marsaglia it was noted that is was best to use Xorshift as a base generator, and apply some output function or combine it with a second generator of a different type. All the variants over the years, like XORWOW, XSadd, xorgens, RanQ1, Xorshift*, truncated Xorshift*, Xorshift+ and Xoroshiro+ differ in their choice of output function.

Xoroshiro+ just trades quality for a little bit of performance.

But the lowest two bits of xoroshiro* are the same LSFR, while for xoroshiro+ the second lowest bit is a perturbed LSFR, so in that regard xoroshiro+ is slightly better.

Ah, yes. I was imprecise. It is true that just multiplying effects the last two bits about as little as addition does. I once made a table of the avalancing effect of a single multiply. What makes a good output function is a multiply, and truncating the result to only the high bits.

AFAIK, the only known impact is on the calculation of the rank of random binary matrices. You are saying users should be careful about the linear dependencies. Why?

I think we have listed a couple of the problematic cases already. Can you have a look at them?

On the other hand, performance is the only reason to use such a generator over a cryptographic one.

The performance is so good already, that the difference between two PRNG algorithms is not much more than the difference caused by using one more register, or having one instruction that can not be run in parallel with another on the processor. There are only 8 or 9 instructions used per new random number (and a couple of mov's), several of which run in parallel.

At such a point it seems to me almost any use of the random number wil take quite a bit longer than generating one. Of course there may be uses where that last cycle can be the difference, and quality is less important. Then Xoroshiro128+ is great!

Note: I will be the last to say good performance is not a good quality. Optimising RNG's is fun ;-)

[pitdicker]

@vks I (we) are guilty of derailing this issue 😄. If you want to reply, could you open a new issue or something and mention my name?