3 ms·

Upon a closer look, do not trust the numbers on https://rust-random.github.io/book/guide-rngs.html https://rust-random.github.io/book/guide-rngs.html in any way

Upon a closer look, do not trust the numbers on https://rust-random.github.io/book/guide-rngs.html https://rust-random.github.io/book/guide-rngs.html in any way, they are clearly bogus and implausible. Their figure for their "StepRNG" which is just a counter is 51GB/s. Their XorShift RNG at 5GB/s, which is just a XOR and a shift is slower than Xorshiro at 7GB/s, which is a xor, shift and rotate, 1 op more. Both XorShift and Xorshiro should actually be of comparable performance to a counter of the same width because with modern CPUs, all those trivial bit operations like shift, rotate and XOR are sub-cycle microops. And all three of those should either be memory-bound and therefore of the same performance, or quite a bit faster than memory-bound if they just measure the in-register performance. > Your 4000x factor speed up for a linear-congruential generator is just a completely false number. > Yes I did pick ChaCha20 for its speed -- it's designed for speed! 1 Chacha20 block takes 20 rounds, each of which consists of 4 QR (quarter round) operations. A QR is 4 additions, 4 XORs and 4 ROTLs, so 12 instructions on 32bit values. Multiply that together and you arrive at 960 operations per block (actually a handful more for the counter, maybe the round loop and stuff like that, but not a lot), each block gives you 16 uint32 values. So 60 instructions per uint32 or 15 instructions per byte. A multiply-add generator takes only 2 instructions (you could use fused-multiply-add if available, but i'll leave that out as I left out sub-microop-rotate before, just to not overcomplicate things) per uint32 or half an instruction per byte. Yes, that is not yet a hyperbolic factor of 4000. But then you'll have to use your random values. Since your Chacha20 random number stream only comes in blocks, on many CPU architectures, you will have all your registers full with your resulting block. Meaning that for the subsequent calculation, you have to store those random numbers somewhere or throw them away, do your other calc, then load the randomness again, etc. So you will always pay a penalty for cache and memory accesses and you will always have unnecessary register pressure. Even a L1 cache access will cost you about 4 cycles of access latency, other cache levels are far worse. Which means that it probably won't be 4000 yet, but a lot more. Now we'll arrive at "yes, but somebody said ChaCha20 is roughly 1 cycle per byte!". Which isn't wrong, but you have to read carefully: 1 _cycle_, not 1 _instruction_. That benchmark relies on calculating multiple ChaCha20 blocks in parallel, because a modern CPU has multiple execution units and thus can execute multiple independent instructions within one cycle. There is also SIMD, where one instruction can operate on multiple pieces of data. But to be fair, we also need to do this with our multiply-add-RNG. And where I can have 16 registers of 32bits calculating one ChaCha20 block, I can also have 16 of the same 32bit registers calculating 16 multiply-add random numbers in parallel. Thus giving us 60 cycles per ChaCha20 uint32 vs. 0.125 cycles (2/16) per multiply-add uint32. That is a factor of 480, not taking possible memory or cache penalties into account, because that really depends on the computation between the randomness steps. Still not 4k, I admit, that was hyperbole.

nneonneo 3y ago
You’re just spouting theoretical numbers here, not actual real-world numbers. First, ChaCha20 can easily be around 1-3 cpb, which translates into around 4-12 c/u32 (source: AVX2 perf of Go ChaCha20 package: https://pkg.go.dev/github.com/aead/chacha20#section-readme https://pkg.go.dev/github.com/aead/chacha20#section-readme). So that’s already a lot better than your theoretical claim of 60 c/u32. Second, a multiply-add PRNG is going to have abysmally poor statistical properties. Those are the kinds of statistical failures that show up real quick if you generate a billion numbers. If you care that little about random quality in your application, why not just increment a counter and be done with it? A more realistic assessment is that it will cost you around 0.3 cpb for a decent quality generator that passes statistical tests. Yes, you want that, at the very least: you don’t want spurious correlations screwing up your billions of Monte Carlo iterations. There’s a plausible claim that you can get down to ~0.1 cpb with AVX (cf https://espadrine.github.io/blog/posts/shishua-the-fastest-prng-in-the-world.html https://espadrine.github.io/blog/posts/shishua-the-fastest-p...). In any case, the best case here is that a CSPRNG is ~5-20x as slow as a decent-quality PRNG. Sure, a crappy RNG is 10x faster than this, but the tradeoff is that sometimes your “randomized” algorithms produce nonsense, and the last thing that you want to debug is stochastic failures in your stochastic algorithms. ChaCha20 implementations don’t usually need to have special handling for side-channel security because they don’t perform data-dependent lookups or branches. Indeed, as the article points out, a lot of these decent PRNGs kinda look like ChaCha-style ARX ciphers with a lot fewer rounds.
- camel-cdr 3y ago
  PRNGs like the romu family are faster than multiply add LCGs and way higher quality (they don't fail statistical tests from testu01 and PractRand). This ia possible due to using more state and exploiting ILP. [0] In LCGs the add dependa on the multiply, so both need to be executed sequentually, romu prngs use a multiply and fit a.bunch of mixing operations into the other exexution ports while the multiply executes. [0] https://www.romu-random.org https://www.romu-random.org

nneonneo 3y ago

You’re just spouting theoretical numbers here, not actual real-world numbers. First, ChaCha20 can easily be around 1-3 cpb, which translates into around 4-12 c/u32 (source: AVX2 perf of Go ChaCha20 package: https://pkg.go.dev/github.com/aead/chacha20#section-readme https://pkg.go.dev/github.com/aead/chacha20#section-readme). So that’s already a lot better than your theoretical claim of 60 c/u32. Second, a multiply-add PRNG is going to have abysmally poor statistical properties. Those are the kinds of statistical failures that show up real quick if you generate a billion numbers. If you care that little about random quality in your application, why not just increment a counter and be done with it? A more realistic assessment is that it will cost you around 0.3 cpb for a decent quality generator that passes statistical tests. Yes, you want that, at the very least: you don’t want spurious correlations screwing up your billions of Monte Carlo iterations. There’s a plausible claim that you can get down to ~0.1 cpb with AVX (cf https://espadrine.github.io/blog/posts/shishua-the-fastest-prng-in-the-world.html https://espadrine.github.io/blog/posts/shishua-the-fastest-p...). In any case, the best case here is that a CSPRNG is ~5-20x as slow as a decent-quality PRNG. Sure, a crappy RNG is 10x faster than this, but the tradeoff is that sometimes your “randomized” algorithms produce nonsense, and the last thing that you want to debug is stochastic failures in your stochastic algorithms. ChaCha20 implementations don’t usually need to have special handling for side-channel security because they don’t perform data-dependent lookups or branches. Indeed, as the article points out, a lot of these decent PRNGs kinda look like ChaCha-style ARX ciphers with a lot fewer rounds.

camel-cdr 3y ago
PRNGs like the romu family are faster than multiply add LCGs and way higher quality (they don't fail statistical tests from testu01 and PractRand). This ia possible due to using more state and exploiting ILP. [0] In LCGs the add dependa on the multiply, so both need to be executed sequentually, romu prngs use a multiply and fit a.bunch of mixing operations into the other exexution ports while the multiply executes. [0] https://www.romu-random.org https://www.romu-random.org