Random numbers and thread local storage

Question

The accepted answer to this question, and a similar discussion at work today got me to wondering about something.

The question was about how to safely generate random numbers in a multi-threaded program. The accepted answer advocates using thread local storage, effectively creating one random number generator per thread. I wonder if that's really such a good idea.

Let's say we have two threads start up at the same time (quite possible on a multi-core system) and both call the default Random constructor to create and initialize a random number generator in thread local storage. Since they didn't pass a seed parameter, Random uses the system time as the seed. So both random number generators have been initialized with the same seed. They will both generaete the same sequence of random numbers.

Since these threads are allocated from the thread pool, there's no way you can associate a particular object with a particular thread. Or, in the case of the above-referenced question, you can't guarantee which pool thread will execute the next request. So imagine that the following happens:

At startup, two requests come in simultaneously.
Two threads are created, each initializing a random number generator with the same seed.

Each thread generates three random numbers.  They will be identical in both threads.

Next request comes in.  It's assigned to thread #1.
It generates a random number and exits.

Some period of time elapses.

Next request comes in.  It's assigned to thread #2.
It generates the same random number that thread #1 did just a while ago.

This could continue indefinitely, although I doubt it would be ping-ponging quite that badly. The point is that both threads have the same PRNG and the likelihood of repeating a sequence is very high. I understand that the P in PRNG stands for "pseudo", but this is a bit much.

I think it's quite possible for multiple threads to initialize a Random instance with the same seed value. If that happens, then the "randomness" of at least some things in the application is going to suffer. The implications of that, of course, are application dependent.

What I don't know is, if the PRNGs are initialized with different seeds, does that make the sequence seen by a client more random, less random, or about the same? That is, if I were to write:

var rnd1 = new Random(123);
var rnd2 = new Random(654);
for (int i = 0; i < OneMillion; ++i)
{
    numbers.Add(rnd1.Next());
 numbers.Add(rnd2.Next());
}

Would the sequence of numbers I generate be more or less random than if I were to just generate two million from either of the PRNGs?

Answer 1

The numbers generated are only as random as the seed you provided. If two threads end up with the same seed, they will have the exact same "random" number sequence.

To prevent this use synchronization to make sure each TLS-stored random number generator is given a unique seed.

private static object _sync = new object();
[ThreadStatic]
private static Random _rand;

...

if (_rand == null) {
    lock(_sync) {
        _rand = new Random(DateTime.Now.Ticks);
        Thread.Sleep(_rand.Next(0,3));
    }
}

There are other ways to ensure the seeds are unique, without sleeping, but this is one simple way useful for demonstration.

Another option, in my opinion a better option, is to just use one random number generator and synchronize calls to it. Everyone is worried about synchronization causing performance differences but unless your generating hundreds of random number generators a millisecond the synchronization would not add any noticeable performance degredation (on my laptop I can obtain and release a lock 17,000 times a millisecond).

Answer 2

The level of randomness should be approximately the same, since both series are generated by the same algorithm.

How do you define randomness? Whether one series appears more random or not may well depend on the user, and what the app does with the series of numbers.

If you're worried about the same seed being used for multiple random number generators, you could always seed all your random number generators from the sequence generated by another, single generator. That way, at least your initial starting point is somewhat arbitrary.