3 ms·

Random Number Generators for C++ Performance Tested (2019)

35 points by optimalsolver 5y ago

iandinwoodie 5y ago
With no intent to be pedantic: wouldn't benchmarked or profiled, instead of performance tested, be a more accurate description of the performance evaluation performed by the author?
_448 5y ago
Reading the title I thought the comparison was between standard library random generators :) How does this compare to the standard library, for e.g. MT? Edit: Okay, spoke too soon! In the article base means the standard library.
0-_-0 5y ago
In which algorithms is the random number generation the bottleneck?
- berkut 5y ago
  Monte Carlo simulations - i.e. pathtracing... Generating well distributed random numbers with low overhead is quire important for that. It's not the bottleneck, but it is very important.
  - 0-_-0 5y ago
    In path tracing you don't want random numbers but low discrepancy sequences
    - berkut 5y ago
      And some of the ways (ignoring things like Sobol and Halton) of generating those are using random numbers :)
- fanf2 5y ago
  I was recently doing some randomised testing, and for some reason the software I was working with chose to use the getrandom() system call for every random number. This completely swamped the performance measurement I was trying to make, more than half the time wasted on random numbers. I switched to PCG with Lemire’s nearly divisionless modular reduction, and the performance numbers were sensible again.
- jeffbee 5y ago
  It can be significant if you are using a PRNG to make sampling decisions in a large data stream for example. I don't know about "the bottleneck" but if you can make a thing handle 1% more HTTP requests per second by doubling the speed of your PRNG, why wouldn't you?
- spacechild1 5y ago
  Noise generation in audio applications. At a sample rate of 44.1 kHz, a single noise generator has to produce 44100 random numbers per second. Now imagine you have dozens or hundreds of them. Luckily, you can get away with very cheap and simple algorithms.
Koffiepoeder 5y ago
If I'm not mistaken some bit-hacking optimization could be done for the LCG variant. `X % 2^Y` can be re-written as `X & (2^Y-1)` . It seems GCC does not benefit from this optimization (it uses 32-bit truncation), but Clang does.
rurban 5y ago
He misses quite a lot of PRNG's. My ranking is more update: https://rurban.github.io/dieharder/QUALITY.html https://rurban.github.io/dieharder/QUALITY.html with wyrand in the lead

35 points by optimalsolver 5y ago

With no intent to be pedantic: wouldn't benchmarked or profiled, instead of performance tested, be a more accurate description of the performance evaluation performed by the author?

_448 5y ago

Reading the title I thought the comparison was between standard library random generators :) How does this compare to the standard library, for e.g. MT? Edit: Okay, spoke too soon! In the article base means the standard library.

0-_-0 5y ago

In which algorithms is the random number generation the bottleneck?

berkut 5y ago
Monte Carlo simulations - i.e. pathtracing... Generating well distributed random numbers with low overhead is quire important for that. It's not the bottleneck, but it is very important.
- 0-_-0 5y ago
  In path tracing you don't want random numbers but low discrepancy sequences
  - berkut 5y ago
    And some of the ways (ignoring things like Sobol and Halton) of generating those are using random numbers :)
fanf2 5y ago
I was recently doing some randomised testing, and for some reason the software I was working with chose to use the getrandom() system call for every random number. This completely swamped the performance measurement I was trying to make, more than half the time wasted on random numbers. I switched to PCG with Lemire’s nearly divisionless modular reduction, and the performance numbers were sensible again.
jeffbee 5y ago
It can be significant if you are using a PRNG to make sampling decisions in a large data stream for example. I don't know about "the bottleneck" but if you can make a thing handle 1% more HTTP requests per second by doubling the speed of your PRNG, why wouldn't you?
spacechild1 5y ago
Noise generation in audio applications. At a sample rate of 44.1 kHz, a single noise generator has to produce 44100 random numbers per second. Now imagine you have dozens or hundreds of them. Luckily, you can get away with very cheap and simple algorithms.

Koffiepoeder 5y ago

If I'm not mistaken some bit-hacking optimization could be done for the LCG variant. `X % 2^Y` can be re-written as `X & (2^Y-1)` . It seems GCC does not benefit from this optimization (it uses 32-bit truncation), but Clang does.

rurban 5y ago

He misses quite a lot of PRNG's. My ranking is more update: https://rurban.github.io/dieharder/QUALITY.html https://rurban.github.io/dieharder/QUALITY.html with wyrand in the lead