4 ms·

It's not true that I cherry-picked a slow PRNG for my 7 GB/s number. In fact I selected the second-fastest PRNG on that page (because it's popular)! The fastest

It's not true that I cherry-picked a slow PRNG for my 7 GB/s number. In fact I selected the second-fastest PRNG on that page (because it's popular)! The fastest one is 8 GB/s. PCG32 is 3 GB/s. 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! "A few hundred FPU instructions" in your Monte Carlo is not comparable to generating a number with ChaCha20. If you need a few hundred FPU instructions per number, you will be running a lot slower than 2 GB/s. ChaCha only requires a few cycles per byte. I agree that you can optimize out the side-channel free part for non-crypto-purposes. That's a good thing! I recommend doing that.

josephg 3y ago
I was curious. The rust rand library has implementations for a lot of rngs - prngs and csrngs. All with high quality implementations as far as I can tell. They agree with your numbers: their fast, high quality prng implementations are about 8gb/sec and chacha is about 2gb/sec: https://rust-random.github.io/book/guide-rngs.html https://rust-random.github.io/book/guide-rngs.html
- espadrine 3y ago
  There are ways to make much faster PRNGs; I designed one that reaches 53 GB/s[0] (0.06 cycles per byte) with better quality than those listed in the article. But I agree with tczajka: good engineering practice ought to be to start with a CSPRNG. First make it work, then make it fast. With truly random data, you know your algorithm works, and can then check if there is a quality loss when switching away. The performance of CSPRNG is so optimized that it is seldom the bottleneck anyway. [0]: https://github.com/espadrine/shishua#comparison https://github.com/espadrine/shishua#comparison
  - josephg 3y ago
    Cool! I wonder if the rand crate would be interested in adding this. I love all their sampling functions - shuffle, choose, uniform, etc. But it looks like shishua is way faster than any of their rngs.
  - ykonstant 3y ago
    This is a very informative repo and associated blog posts.
pclmulqdq 3y ago
The state of the art in super-fast PRNGs is about 0.3 cycles per byte at the moment. I believe this is done with SIMD versions of the xoroshiro algorithms right now. 0.3 cycles per byte compared to "a few" cycles per byte is an order of magnitude difference in throughput. Here's the comparison from the maintainers of Julia: https://prng.di.unimi.it/#shootout https://prng.di.unimi.it/#shootout Still, most crypto libraries are designed with extreme performance in mind, and very few PRNG libraries are. You can do a lot better than 0.3 cycles/byte and still beat the NIST test if you try for speed.
- hdevalence 3y ago
  I haven't paid close attention recently but that doesn't seem that far off of performance available via (hardware accelerated) AES? Looking at https://eprint.iacr.org/2018/392.pdf https://eprint.iacr.org/2018/392.pdf , it seems like: - Intel CPUs can use AESNI to do AES at 0.64 cpb - AMD Zen cores have two AESNI cores and can achieve 0.31 cpb - Vectorized AES instructions (supposed to ship in Ice Lake five years ago, but maybe a casualty of Intel's AVX512 mishaps) were expected to bring it down to 0.16 cpb In some sense this isn't a "fair" comparison in that it's fast because there's hardware acceleration, but that doesn't really matter, the hardware is there so it might as well be used.
  - pclmulqdq 3y ago
    Yeah, chacha was an odd choice because AES is a lot faster on CPUs with acceleration. Just doing a few AES rounds would be a pretty fast, good PRNG.
    - dpwm 3y ago
      For those interested in using AES with reduced rounds as a PRNG, it is covered in the paper "Parallel Random Numbers: As Easy as 1, 2, 3" by John Salmon et al. https://www.thesalmons.org/john/random123/papers/random123sc11.pdf https://www.thesalmons.org/john/random123/papers/random123sc...
isilofi 3y ago
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.
camel-cdr 3y ago
You can get close to 10x faster [1] than chacha8 with SIMD PRNG implementations, that are way higher quality than the usual LCG and don't fail any statistical test in the test suites (testu01 & PractRand). They are obviously not cryptographically secure, but it's very hard to run into problems with bias in simulations, when test suites designed to find such bias can't find it. [0] https://github.com/espadrine/shishua https://github.com/espadrine/shishua

josephg 3y ago

I was curious. The rust rand library has implementations for a lot of rngs - prngs and csrngs. All with high quality implementations as far as I can tell. They agree with your numbers: their fast, high quality prng implementations are about 8gb/sec and chacha is about 2gb/sec: https://rust-random.github.io/book/guide-rngs.html https://rust-random.github.io/book/guide-rngs.html

espadrine 3y ago
There are ways to make much faster PRNGs; I designed one that reaches 53 GB/s[0] (0.06 cycles per byte) with better quality than those listed in the article. But I agree with tczajka: good engineering practice ought to be to start with a CSPRNG. First make it work, then make it fast. With truly random data, you know your algorithm works, and can then check if there is a quality loss when switching away. The performance of CSPRNG is so optimized that it is seldom the bottleneck anyway. [0]: https://github.com/espadrine/shishua#comparison https://github.com/espadrine/shishua#comparison
- josephg 3y ago
  Cool! I wonder if the rand crate would be interested in adding this. I love all their sampling functions - shuffle, choose, uniform, etc. But it looks like shishua is way faster than any of their rngs.
- ykonstant 3y ago
  This is a very informative repo and associated blog posts.

pclmulqdq 3y ago

The state of the art in super-fast PRNGs is about 0.3 cycles per byte at the moment. I believe this is done with SIMD versions of the xoroshiro algorithms right now. 0.3 cycles per byte compared to "a few" cycles per byte is an order of magnitude difference in throughput. Here's the comparison from the maintainers of Julia: https://prng.di.unimi.it/#shootout https://prng.di.unimi.it/#shootout Still, most crypto libraries are designed with extreme performance in mind, and very few PRNG libraries are. You can do a lot better than 0.3 cycles/byte and still beat the NIST test if you try for speed.

hdevalence 3y ago
I haven't paid close attention recently but that doesn't seem that far off of performance available via (hardware accelerated) AES? Looking at https://eprint.iacr.org/2018/392.pdf https://eprint.iacr.org/2018/392.pdf , it seems like: - Intel CPUs can use AESNI to do AES at 0.64 cpb - AMD Zen cores have two AESNI cores and can achieve 0.31 cpb - Vectorized AES instructions (supposed to ship in Ice Lake five years ago, but maybe a casualty of Intel's AVX512 mishaps) were expected to bring it down to 0.16 cpb In some sense this isn't a "fair" comparison in that it's fast because there's hardware acceleration, but that doesn't really matter, the hardware is there so it might as well be used.
- pclmulqdq 3y ago
  Yeah, chacha was an odd choice because AES is a lot faster on CPUs with acceleration. Just doing a few AES rounds would be a pretty fast, good PRNG.
  - dpwm 3y ago
    For those interested in using AES with reduced rounds as a PRNG, it is covered in the paper "Parallel Random Numbers: As Easy as 1, 2, 3" by John Salmon et al. https://www.thesalmons.org/john/random123/papers/random123sc11.pdf https://www.thesalmons.org/john/random123/papers/random123sc...

isilofi 3y ago

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.

camel-cdr 3y ago

You can get close to 10x faster [1] than chacha8 with SIMD PRNG implementations, that are way higher quality than the usual LCG and don't fail any statistical test in the test suites (testu01 & PractRand). They are obviously not cryptographically secure, but it's very hard to run into problems with bias in simulations, when test suites designed to find such bias can't find it. [0] https://github.com/espadrine/shishua https://github.com/espadrine/shishua