Efficient random number generation with C++11 <random>

Question

I am trying to understand how the C++11 random number generation features are meant to be used. My concern is performance.

Suppose that we need to generate a series of random integers between 0..k, but k changes at every step. What is the best way to proceed?

Example:

for (int i=0; i < n; ++i) {
    int k = i; // of course this is more complicated in practice
    std::uniform_int_distribution<> dist(0, k);
    int random_number = dist(engine);
    // do something with random number
}

The distributions that the <random> header provides are very convenient. But they are opaque to the user, so I cannot easily predict how they will perform. It is not clear for example how much (if any) runtime overhead will be caused by the construction of dist above.

Instead I could have used something like

std::uniform_real_distribution<> dist(0.0, 1.0);
for (int i=0; i < n; ++i) {
    int k = i; // of course this is more complicated in practice
    int random_number = std::floor( (k+1)*dist(engine) );
    // do something with random number
}

which avoids constructing a new object in each iteration.

Random numbers are often used in numerical simulations where performance is important. What is the best way to use <random> in these situations?

---

Please do no answer "profile it". Profiling is part of effective optimization, but so is a good understanding of how a library is meant to be used and the performance characteristics of that library. If the answer is that it depends on the standard library implementation, or that the only way to know is to profile it, then I would rather not use the distributions from <random> at all. Instead I can use my own implementation which will be transparent to me and much easier to optimize if/when necessary.

Answer 1

One thing you can do is to have a permanent distribution object so that you only create the param_type object each time like this:

template<typename Integral>
Integral randint(Integral min, Integral max)
{
    using param_type =
        typename std::uniform_int_distribution<Integral>::param_type;

    // only create these once (per thread)
    thread_local static std::mt19937 eng {std::random_device{}()};
    thread_local static std::uniform_int_distribution<Integral> dist;

    // presumably a param_type is cheaper than a uniform_int_distribution
    return dist(eng, param_type{min, max});
}

Answer 2

For maximizing performance, first of all consider different PRNG, such as xorshift128+. It has been reported being more than twice as fast as mt19937 for 64-bit random numbers; see http://xorshift.di.unimi.it/. And it can be implemented with a few lines of code.

Moreover, if you don't need "perfectly balanced" uniform distribution and your k is much less than 2^64 (which likely is), I would suggest to write simply something as:

uint64_t temp = engine_64(); // generates 0 <= temp < 2^64
int random_number = temp % (k + 1); // crop temp to 0,...,k

Note, however, that integer division/modulo operations are not cheap. For example, on an Intel Haswell processor, they take 39-103 processor cycles for 64-bit numbers, which is likely much longer than calling an MT19937 or xorshift+ engine.