5 ms·

For many kinds of Monte Carlo algorithms, CSPRNGs are stupidly slow. The author compares two handpicked examples of a fast CSPRNG and a very slow PRNG, arriving

For many kinds of Monte Carlo algorithms, CSPRNGs are stupidly slow. The author compares two handpicked examples of a fast CSPRNG and a very slow PRNG, arriving at a factor of 4. In practice, e.g. comparing to very simple stuff like multiply-add RNGs, it is more like a factor of 4000. Only to then claim that "But that would only be true if generating random bits was the hot spot, the bottleneck of your program. It never is in practice." E.g. for the usual example of Monte Carlo integration, you pick a point randomly, usually by running your RNG for both coordinates. Then you evaluate your characteristic function with that point as an input. Very often, the function will have a runtime that is in the range of a few hundred FPU instructions or less. Comparable to the evaluation of your CSPRNG. So in the end, you usually get a 40 to 50% faster runtime by just using a slow PRNG instead of a CSPRNG. Not to mention the few extra percent you will gain with a fast PRNG. And it doesn't stop there. CSPRNG libraries are often optimized to be side-channel free and cryptographically safe. Even if you were to use a CSPRNG, you are leaving performance on the table by using stuff with security properties you will never ever need, that can easily be optimized out for a 30% gain in the CSPRNG parts. And yes, for simulations a few percent points are relevant. Thoses "few" percents are maybe days in runtime, thousands of currency units in power and hardware cost and tons of CO2 in pollution.

tczajka 3y ago
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.
KolenCh 3y ago
For Monte Carlo and if you need for speed, consider Quasi Monte Carlo. For the right kind of problems the speed up in convergence is huge (ie given same accuracy it will be faster.)

tczajka 3y ago

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.

KolenCh 3y ago

For Monte Carlo and if you need for speed, consider Quasi Monte Carlo. For the right kind of problems the speed up in convergence is huge (ie given same accuracy it will be faster.)