Comment by isilofi | Hacker News Reader

Comment by isilofi | Hacker News Reader

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.

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.

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

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

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.

This is a very informative repo and associated blog posts.

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

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.

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 , 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.

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.

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/random123sc...

Upon a closer look, do not trust the numbers on 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.

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). 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-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.

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

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

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.)

Reply on news.ycombinator.com