4 ms·

In many Monte-Carlo algorithms random number generation is responsible for a significant chunk of total runtime. Modern PRNGs like Xoshiro256+ implemented with

by pps43 7y ago

In many Monte-Carlo algorithms random number generation is responsible for a significant chunk of total runtime. Modern PRNGs like Xoshiro256+ implemented with AVX are much faster than any CSPRNG.

seanhunter 7y ago
Yes indeed. In fact people often use things like Sobol Sequences https://en.wikipedia.org/wiki/Sobol_sequence https://en.wikipedia.org/wiki/Sobol_sequence
- pps43 7y ago
  Not so much because they are fast, though, but because they produce more evenly distributed (less clumpy) numbers.
  - seanhunter 7y ago
    Yes but this (sometimes/often) means you actually need less paths in your MC simulation and therefore makes it faster overall. Obviously depending on what you're trying to simulate and what the underlying stochastic processes are etc. I guess my point was there are often legitimate uses for things that are random-like but far from crypto random.
blattimwind 7y ago
I found a figure of 0.4 cpb for xoshiro256++. AES-128-CTR using AES-NI runs at over 10 GB/s per core on a 3900X. That's approximately the same throughput. Of course, performance embedded in a real simulation may differ wildly, I expect xoshiro is much, much friendlier to frequent invocations generating a block each than AES, so to reach that throughput with AES you'd likely need a not-so-small buffer, which eats into L1 and L2 cache budgets.
- pps43 7y ago
  I suspect that cpb is without using vector operations. AVX-512 lets you run 8 generators in parallel, and you can do even better with CUDA.
  - justincormack 7y ago
    There are parallel AES ops on new CPUs too though. Not sure if that figure is already using those.
  - zokier 7y ago
    .25 cpb (1cycle/32bit) for xorshift and pcg with avx512 in here: https://lemire.me/blog/2018/06/07/vectorizing-random-number-generators-for-greater-speed-pcg-and-xorshift128-avx-512-edition/ https://lemire.me/blog/2018/06/07/vectorizing-random-number-...

by pps43 7y ago

In many Monte-Carlo algorithms random number generation is responsible for a significant chunk of total runtime. Modern PRNGs like Xoshiro256+ implemented with AVX are much faster than any CSPRNG.

seanhunter 7y ago

Yes indeed. In fact people often use things like Sobol Sequences https://en.wikipedia.org/wiki/Sobol_sequence https://en.wikipedia.org/wiki/Sobol_sequence

pps43 7y ago
Not so much because they are fast, though, but because they produce more evenly distributed (less clumpy) numbers.
- seanhunter 7y ago
  Yes but this (sometimes/often) means you actually need less paths in your MC simulation and therefore makes it faster overall. Obviously depending on what you're trying to simulate and what the underlying stochastic processes are etc. I guess my point was there are often legitimate uses for things that are random-like but far from crypto random.

blattimwind 7y ago

I found a figure of 0.4 cpb for xoshiro256++. AES-128-CTR using AES-NI runs at over 10 GB/s per core on a 3900X. That's approximately the same throughput. Of course, performance embedded in a real simulation may differ wildly, I expect xoshiro is much, much friendlier to frequent invocations generating a block each than AES, so to reach that throughput with AES you'd likely need a not-so-small buffer, which eats into L1 and L2 cache budgets.

pps43 7y ago
I suspect that cpb is without using vector operations. AVX-512 lets you run 8 generators in parallel, and you can do even better with CUDA.
- justincormack 7y ago
  There are parallel AES ops on new CPUs too though. Not sure if that figure is already using those.
- zokier 7y ago
  .25 cpb (1cycle/32bit) for xorshift and pcg with avx512 in here: https://lemire.me/blog/2018/06/07/vectorizing-random-number-generators-for-greater-speed-pcg-and-xorshift128-avx-512-edition/ https://lemire.me/blog/2018/06/07/vectorizing-random-number-...