CODEWITHSUNDEEP
c++performanceoptimizationrandommt19937
Josh
Josh

Reputation: 313

How computationally expensive is generating a random number in C++?

The method that I am considering is from an answer to Generating random integer from a range.

#include <random>

std::random_device rd;     // only used once to initialise (seed) engine
std::mt19937 rng(rd());    // random-number engine used (Mersenne-Twister in this case)
std::uniform_int_distribution<int> uni(min,max); // guaranteed unbiased

auto random_integer = uni(rng);

I'm also willing to use the rand() approach with srand(time(NULL)).

How expensive are these approaches? Is one much faster than the other?

Upvotes: 5

Views: 4344

Answers (2)

user31264
user31264

Reputation: 6727

I could write that the performance depends on both implementation and hardware, but it would be as correct as useless. One example of performance would be more useful.

Dell Latitude E7240 laptop (2013), Linux, g++ 4.8.4, and the -O3 flag:

#include <cstdlib>
#include <iostream>

int main(int argc, const char** argv) {
    const bool bPlain = (argv[1][0] == '-');
    if (bPlain)
        argv++;
    int n = atoi(argv[1]);
    int sum = 0;
    if (bPlain)
        for (int i=0; i<n; i++)
            sum |= i;
    else
        for (int i=0; i<n; i++)
            sum |= rand();
    // To prevent the compiler from optimizing away the loop
    if (sum == 0)
        std::cout << sum << std::endl;
}

[~/CPP] time ./randbm 1000000000
9.049u 0.000s 0:09.05 99.8%    0+0k 0+0io 0pf+0w
[~/CPP] time ./randbm 1000000000
9.059u 0.000s 0:09.06 99.8%    0+0k 0+0io 0pf+0w
[~/CPP] time ./randbm 1000000000
9.040u 0.008s 0:09.05 99.8%    0+0k 0+0io 0pf+0w
[~/CPP] time ./randbm - 1000000000
0.192u 0.000s 0:00.20 95.0%    0+0k 0+0io 0pf+0w
[~/CPP] time ./randbm - 1000000000
0.172u 0.000s 0:00.18 94.4%    0+0k 0+0io 0pf+0w
[~/CPP] time ./randbm - 1000000000
0.185u 0.004s 0:00.20 90.0%    0+0k 0+0io 0pf+0w

So, in this particular case, one call to rand() takes roughly 9 nanoseconds, while one loop iteration takes roughly 0.2 nanoseconds.

Using random is slower. Adding #include <random> and replacing the relevant part of the code by:

std::random_device rd;     // only used once to initialise (seed) engine
std::mt19937 rng(rd());    // random-number engine used (Mersenne-Twister in this case)
std::uniform_int_distribution<int> uni(0, 1048575);

if (bPlain)
    for (int i=0; i<n; i++)
        sum |= i;
else
    for (int i=0; i<n; i++)
        sum |= uni(rng);

we get (notice we do 108 runs, not 109):

[~/CPP] time ./randbm2 100000000
2.478u 0.003s 0:02.49 99.1%    0+0k 0+0io 0pf+0w
[~/CPP] time ./randbm2 100000000
2.471u 0.004s 0:02.47 100.0%    0+0k 0+0io 0pf+0w
[~/CPP] time ./randbm2 100000000
2.445u 0.007s 0:02.48 98.3%    0+0k 0+0io 0pf+0w
[~/CPP] time ./randbm2 100000000
2.497u 0.004s 0:02.50 99.6%    0+0k 0+0io 0pf+0w
[~/CPP] time ./randbm2 100000000
2.482u 0.011s 0:02.49 100.0%    0+0k 0+0io 0pf+0w

Producing a random number this way takes roughly 25 nanoseconds. However, uni, unlike rand(), also inserts the number into the interval.

Is that extra work important? No. If, for example, you do

sum |= (rand() % 1048576);

the time increases from 9 to 9.5 nanoseconds. If the number is not a power of 2, e. g.

sum |= (rand() % 1000000);

It takes 10 nanoseconds. Other reasonable methods of inserting the number into the interval take roughly the same time.

So, for one particular configuration, rand() itself takes roughly 9 nanoseconds; together with inserting the random number into the interval, it takes roughly 9.5-10 nanoseconds; std::mt19937 with uniform_int_distribution<int> takes roughly 25 nanoseconds.

I hope you are not one of those who confuse nanoseconds with microseconds!

Upvotes: 3

Jesper Juhl
Jesper Juhl

Reputation: 31447

Performance depends greatly on the generator you use (which in turn depends greatly on the quality of the numbers you need).

For example, std::mt19937 is much faster than std::random_device, but it produces pseudo random numbers. This is fine for most purposes, if you don't need cryptographically safe random numbers. But even if you do, random_device can produce raw entropy at a rate of about 50 MB/sec on my machine—how much randomness do you really need? (mt19937 generates about orders of magnitudes more than that if needed).

Avoid rand(). It just has very poor properties and a very low period.

See also Rand Considered Harmful.

Upvotes: 5

Related Questions