Generate random numbers in advance in another thread in c++11

Question

For some numerical simulations in c++ I need to generate many random number with exponential distribution (all with the same predetermined distribution). Currently, my program works well, but more than 50% of the CPU time is spent generating these random numbers.

What I would like to do is generate these random numbers in a way that does not block the main loop of the simulation. More precisely, I would like to have a thread whose job is to always keep a random number "ready in advance", and immediately generate a new one when somebody reads this random number.

Does anybody know of a nice way of doing this?

Currently, my sequential code looks like this:

#include <stdio.h>
#include <iostream>
#include <random>

using namespace std;

// exponential random variable with parameter lambda
class EXPGenerator{
    exponential_distribution<> expo;
    mt19937 engine; //mersene twister
public:
    EXPGenerator(double lambda){
        expo = exponential_distribution<>(lambda);
        engine = mt19937(time(NULL));
    }

    double step(){  
        return expo(engine);
    }
};

int main(int argc, char *argv[])
{
    EXPGenerator expgen(2.0);
    for(int i=0; i<100000; i++) {
        double randv(expgen.step());
        std::cout << randv << endl;
        // do something complicated
    }
    return 0;
}

I compile it using clang++ -O2 --std=c++11 --stdlib=libc++ test.cpp -o test

[EDIT: added -O2 above]

Answer 1

Use a bounded queue and have one thread pushing random numbers into this queue and let that thread block on the queue, when the queue is full. To get a random number, pull a number out of this queue and let the consumer thread block on the queue, when the queue is empty.

This simple design will let the producer produce random numbers, when there is room in the queue and cpu time available.

Optimization: Use a queue with lists of random numbers. In this case, the producer will produce a complete list with random numbers. The consumer will keep a cache (probably inside of EXPGenerator) with a list out of the queue. Once the cache is empty, the cache will be filled with a new list from the queue. This will reduce the context switch overhead and should (of cause) only applied, when measuring shows, that this makes sense.

The queue should basically be some std::deque with T being a random number, or std::vector (a list of random numbers). Use a mutex to synchronize the access to that std:queue and use two condition variables. One, to signal that there is room to insert more random numbers again. And one to signal, that there is already at least one element in the queue. Let the consumer wait for the second condition, when the queue is empty and let the producer wait for the first condition, when the queue is full.

Answer 2

The first thing you should try is to enable optimizations. Try adding a -O2 option to the clang command line.

Answer 3

When you work with optimizations (as others suggest) you can create a bunch of random numbers in an other thread store them in a vector and use a message queue to transport it to your main thread. There you can wrap it into your EXPGenerator.