Optimizing the use of the C++11 random generator

Question

I'm coding a physics simulation heavily using random numbers, I just profiled my code for the first time so I may be in wrong in reading the output but I see this line coming first:

   %   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name  
 90.09     21.88    21.88   265536     0.08     0.08  std::mersenne_twister_engine<unsigned long, 32ul, 624ul, 397ul, 31ul, 2567483615ul, 11ul, 4294967295ul, 7ul, 2636928640ul, 15ul, 4022730752ul, 18ul, 1812433253ul>::operator()()

It seems to mean that generating number generator takes 90% of the time. I had already written a previous post asking if not constructing the random probability distributions at each loop could save me time but after trying and timing it didn't help (Is defining a probability distribution costly? ). Are there common options for optimizing random number generation?

Thank you in advance, my simulations (in its current state) runs for days so reducing on 90% of this computation time would be a significant progress.

Answer 1

There is always a trade-off between the efficiency, i.e. speed and size (number of bytes of the state), on the one hand and "randomness" of any RNG on the other. The Mersenne twister has quite good randomness (provided you use a high-entropy seed, such as provided by std::random_device), but slow and has large state. std::minstd_rand or std::knuth_b (linear congruential) are faster and ranlux48 (Fibbonacci) yet faster, but are less random (pass fewer test for randomness, i.e. have some non-random spectral properties). Just experiment and test if you're happy with the randomness provided (i.e. have no unsuspected correlations in the random data).

---

edit: 1 All these RNG are not truly random, of course, and are also not random enough for cryptography. If you need that, use std::random_device, but don't complain about speed. 2 In parallel (which you should consider), use thread_local RNGs, each initialised with another seed.

Answer 2

If your code spends most of its time generating random numbers, you may want to take some time to choose the best algorithm for your application and implement it yourself. The Mersenne Twister is a pretty fast algorithm, and has good randomness, but you can always trade off some quality of the random numbers generated for more speed. It will depend on what your simulation requires and on the type of numbers you are generating (ints or floats). If you absolutely need good randomness, Mersenne Twister is probably already one of your best options. Otherwise, you may want to implement a simple linear congruential generator in your code.

Another thing to watch out for is if your code is parallel, you should be using a reentrant version of the random number generator and make sure that different threads use their own internal state variables for their generators. Otherwise, mutexes to avoid overwriting internal state variables of the generator will slow down your code a lot. Many library generators are not reentrant, mind you. If your code is not parallel, you should probably parallelize it and use a separate thread to populate a list of random numbers for your simulation to consume. Another option is to use the GPU to generate random numbers in parallel.

Here are some links comparing the performance of diferent generators: http://www.boost.org/doc/libs/1_38_0/libs/random/random-performance.html https://www.gnu.org/software/gsl/manual/html_node/Random-Number-Generator-Performance.html