Concurrent random number generation in Java

Question

On a web server, many threads are serving the content to the clients. A/B tests are performed on the web site, so we need a PRNG to choose a variant for each session and test. Obviously when using a single instance of a PRNG, it is accessed concurrently, so proper locking or other mechanisms might be required.

Initially we used java.util.Random(juR), but since it has the flaws mentioned e.g. How good is java.util.Random, we tried to use MersenneTwister instead. However we saw a major drop in performance due to the fact that Mersenne-Twister relies on an internal state, so it access to nextInt() needs to be synchronized. An alternative might be an XOR shift PRNG, but it has the same problem as Mersenne Twister. You can find an explanation e.g. here: http://xorshift.di.unimi.it/

Random uses a compareAndSet operation, which seems to be much faster as it does not require locking, but according to the class Javadoc it is still not thread-safe. Instead it is suggested to use ThreadLocalRandom instead, which would basically result in a pool of PRNG's. Upon a request, a random available thread handles the HTTPS request, so a random PRNG is chosen from a set of available PRNG's. Obviously this is quite fast.

Are produced random numbers from such a pool are as good as the ones from a single PRNG instance?

Another approach would be to use a single PRNG instance to pre-generate a stream of values from it e.g. by using ArrayBlockingQueue.

Which solution would work better in terms of performance?

For this application (choosing if A or B is shown to the user) the quality of the random numbers really doesn't matter as long as they are uniformly distributed. — Henry, Jan 02 '16 at 15:17
You are pre-optimizing hard. Random is documented as thread-safe, and calling nextBoolean() every time you start a session is completely negligible in terms of performance compared to all the IO needed for the web application (database queries, HTTP requests, etc.). — JB Nizet, Jan 02 '16 at 15:18
The idea was trying to come up with something better than java.util.Random in terms of random number quality. We actually have more than just two variants, so we draw integers. @Henry As far as I've read, the probabilty for the bits in Random is not equally distributed. — user3001, Jan 02 '16 at 15:20
Even then, Random is more than good enough for that. But if you want a perfect distribution, you don't even need a Random here. Just use an AtomicInteger and increment it at each session start. Then compute the modulo of the number of variants. All you need is a good distribution, not a good randomness. — JB Nizet, Jan 02 '16 at 15:21
Still my question is unanswered. Is a pool of PRNG's as good as a single PRNG? — user3001, Jan 02 '16 at 15:22
@JBNizet I like the simplicity of your idea. However this only works if you do 1/N splits. If I wanted to have a 60/40 percent split for two variants, it does not work I guess. — user3001, Jan 02 '16 at 15:30
Well, if the modulo 5 is 0, 1 or 2, choose version A. If it's 3 or 4, choose version B. — JB Nizet, Jan 02 '16 at 15:32
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/99533/discussion-between-user3001-and-jb-nizet). — user3001, Jan 02 '16 at 15:35

score 3 · Accepted Answer · answered Jan 04 '16 at 13:13

You can make any random number generator thread safe by passing the results through a BlockingQueue.

class SafeRandom implements Runnable {

    Random r = new Random();
    BlockingQueue<Double> q = new ArrayBlockingQueue<>(10);

    double get() throws InterruptedException {
        return q.take();
    }

    @Override
    public void run() {
        try {
            while (true) {
                q.put(r.nextDouble());
            }
        } catch (InterruptedException ie) {
        }
    }

}

score 2 · Answer 2 · answered Jan 02 '16 at 16:26

To avoid synchronisation problems have one RNG for each thread. To avoid the thread-specific RNGs giving the same output, have a master RNG generate a series of initial seeds for the thread-specific RNGs. This may need an extra seed parameter passed into your code to generate a new thread.

You will need to test for yourself how fast different options for the RNG run on your kit. It would be possible to use different RNG engines for the master RNG and the thread-specific RNGs if required. In general pick an RNG with a fast set-up time for the thread specific RNGs. That is not as important for the master RNG since that is only set up once.

Concurrent random number generation in Java

2 Answers2