Getting random numbers in a thread-safe way

Getting random numbers in a thread-safe way

Rate This
  • Comments 30

It’s very common in a parallel application to need random numbers for this or that operation.  For situations where random numbers don’t need to be cryptographically-strong, the System.Random class is typically a fast-enough mechanism for generating values that are good-enough.  However, effectively utilizing Random in a parallel app can be challenging in a high-performance manner.

There are several common mistakes I’ve seen developers make.  The first is to assume that Random is thread-safe and is ok to be used concurrently from multiple threads.  This is a bad idea, and can have some drastic consequences on the quality of the random numbers (degrading them well below the “good enough” bar).  For an example of this, consider the following program:

using System;
using System.Threading;

class Program
{
    static void Main(string[] args)
    {
        Random rand = new Random();

        Parallel.For(0, 1000000, (i, loop) =>
        {
            if (rand.Next() == 0) loop.Stop();
        });

        while (true)
        {
            Console.WriteLine(rand.Next());
            Console.ReadLine();
        }
    }
}

While it won’t happen every time you run the app, on a multi-core machine it’s likely that once the Parallel.For in this example exits, rand.Next() will always return 0.  Not very random, is it?  This is due to an implementation detail of Random that does not tolerate multithreaded access (it wasn’t designed for it, and the docs explicitly call out that Random should not be used from multiple threads, as they do for most types in the .NET Framework).

Another common mistake is to fix a problem like that in the previous example by instantiating a new Random instance each time a random number is needed.  This can also affect the quality of the random numbers.  When a seed isn’t explicitly provided to Random through its constructor, it internally uses Environment.TickCount (at least in the current release) as the seed.  TickCount returns a value that’s heavily influenced by the resolution of the system timer, and thus multiple calls to TickCount in a row are likely to yield the same value (on the system on which I’m writing this post, TickCount changes in value approximately once every 15 milliseconds).  This means that Random will suffer a similar fate, as is exemplified in the following program:

using System;

class Program
{
    static void Main(string[] args)
    {
        int lastNumber = 0, count = 0;
        while (true)
        {
            // Get the next number
            int curNumber = new Random().Next();

            // If it's the same as the previous number, 
            //
note the increased count
            if (curNumber == lastNumber) count++;

            // Otherwise, we have a different number than
            // the previous. Write out the previous number
            // and its count, then start
            // over with the new number.
            else
            {
                if (count > 0)
                    Console.WriteLine(
                        count + ": " + lastNumber);
                lastNumber = curNumber;
                count = 1;
            }
        }
    }
}

This program continually creates new Random instances and gets a random value from each, counting the number of “random” values in a row that are the same.  When I run this app, I consistently see each number showing up thousands of times before the number changes; again, not very random.  The point of this example is that, in a multithreaded context, you may be creating a Random instance for each iteration, but many iterations across threads are likely to end up with the same value.

There are several approaches then one could take in using Random from multiple threads to avoid these kinds of issues.

One approach is to use a lock.  A shared Random instance is created, and every access to the Random instance is protected by a lock, e.g.

public static class RandomGen1
{
    private static Random _inst = new Random();

    public static int Next()
    {
        lock (_inst) return _inst.Next();
    }
}

This has the benefit of being easy to write, simple to explain, and obviously does the right thing.  Unfortunately, there’s an expensive lock on every access, and the more threads that want random numbers, the more contention there will be for this lock.  Sharing hurts.

Another approach is to use one Random instance per thread, rather than one per AppDomain (as is the case with the RandomGen1 approach shown above).  Here’s one way that might be implemented:

public static class RandomGen2
{
    private static Random _global = new Random();
    [ThreadStatic]
    private static Random _local;

    public static int Next()
    {
        Random inst = _local;
        if (inst == null)
        {
            int seed;
            lock (_global) seed = _global.Next();
            _local = inst = new Random(seed);
        }
        return inst.Next();
    }
}

An AppDomain-wide Random instance is maintained in order to provide seeds for new Random instances created for any new threads that come along wanting random numbers.  Each thread maintains its own Random instance in a ThreadStatic field, such that once initialized, calls to Next need only retrieve the ThreadStatic Random instance and use its Next method; no locks are necessary, and sharing is minimized.  I tested this in a loop like the following:

Stopwatch sw;
const int NUM = 1000000;

while (true)
{
    sw = Stopwatch.StartNew();
    Parallel.For(0, NUM, i =>
    {
        RandomGen1.Next();
    });
    Console.WriteLine(sw.Elapsed);

    sw = Stopwatch.StartNew();
    Parallel.For(0, NUM, i =>
    {
        RandomGen2.Next();
    });
    Console.WriteLine(sw.Elapsed);

    Console.ReadLine();
}

On my dual-core laptop using .NET 3.5 and the June 2008 CTP of Parallel Extensions, the ThreadStatic approach ended up running twice as fast as the lock-based version.  Moreover, as the number of cores increases, so too will the amount of contention on the lock in the lock-based approach, thus increasing the gap between the two approaches.  Additionally, a lot of work has been done in .NET 4.0 to improve the performance of things such as accessing [ThreadStatic].  When I run this same code on current builds of .NET 4.0 (again on a dual-core), I see the ThreadStatic version running more than four times faster than the lock-based version.  Even when there’s no contention on the lock in the RandomGen1 solution (simulated by switching the parallel loops to sequential loops), the ThreadStatic version in .NET 4.0 still runs significantly faster than the lock-based version.

Of course, if you really care about the quality of the random numbers, you should be using RNGCryptoServiceProvider, which generates cryptographically-strong random numbers (Addendum: davidacoder makes a good point in his comments on this post that while Random has certain statistical properties, using multiple Random instances as part of the same algorithm may change the statistical properties in unknown or undesirable ways).  For a look at how to get a Random-based facade for RNGCryptoServiceProvider, see .NET Matters: Tales from the CryptoRandom in the September 2007 issue of MSDN Magazine.  You could also settle on an intermediate solution, such as using an RNGCryptoServiceProvider to provide the seed values for the ThreadStatic Random instances in a solution like that in RandomGen2 (which would help to avoid another issue here, that of two threads starting with the same seed value due to accessing the global Random instance in the same time quantum):

public static class RandomGen3
{
    private static RNGCryptoServiceProvider _global =
        new RNGCryptoServiceProvider();
    [ThreadStatic]
    private static Random _local;

    public static int Next()
    {
        Random inst = _local;
        if (inst == null)
        {
            byte[] buffer = new byte[4];
            _global.GetBytes(buffer);
            _local = inst = new Random(
                BitConverter.ToInt32(buffer, 0));
        }
        return inst.Next();
    }
}

Leave a Comment
  • Please add 1 and 4 and type the answer here:
  • Post
  • PingBack from http://weakbladder.info/story.php?id=2518

  • PingBack from http://workfromhomecareer.info/story.php?id=16966

  • PingBack from http://gardendecordesign.info/story.php?id=5654

  • This is remakrably complex, but I was looking for something very different.  Hmm...maybe something to learn though here.

  • RandomGen2 works well in my genetic algorithm, but RandomGen1 does not. Guessing RandomGen1 is not random enough when it is shared.

  • You've got a lock bug in RandomGen2 :

    In Next() instead of:

           if (inst == null)

           {

               int seed;

               lock (_global) seed = _global.Next();

               _local = inst = new Random(seed);

           }

    you should write:

           if (inst == null)

           {

               lock(_global)

               {

                  if( inst == null )

                  {

                   int seed;

                   seed = _global.Next();

                   _local = inst = new Random(seed);

                  }

               }

           }

  • Hi Softlion-

    The code is actually ok as is, but thanks for taking the time to report a possible issue.  This isn't a typical double-checked locking scheme.  Rather, the lock is simply being used to protect access to the global seed generator.  inst is a local, and _local is a ThreadStatic, which means that every thread has its own copy of the static, and thus the only thread that can be using this thread's instance of it is this thread.

  • What about using a global counter for Random Seeds, that is incremented using Interlocked.Increment() ?

  • You mean something like this?

    public static class RandomGen4

    {

       private static int _counter = 0;

       public static int Next()

       {

           return new Random(Interlocked.Increment(ref _counter)).Next();

       }

    }

    This is actually significantly more expensive than RandomGen2 or RandomGen3 shown earlier... the cost of the interlocked operation dwarfs the cost of computing the next random value.

  • Hello,

    I love your post on the Parallel.For.

    Implemented as a test on a project I'm developing on a Windows Services.

    I'm having some problems because the service scans a SQL database table and returns aproximadamento some 2 million records, then it performs some actions and finally it writes the result of operation fied in a text file.

    Looking at the text file I realized that it works well but some records are compromised because some threads try to write the file while the value of the record is wrong.

    How can I do to allow a result to be written on the bench only after a thread may have finished writing?

    It is worth observing that I'm using a server with 16 processing cores.

    Part code:

    //Cria arquivo de log

    FileStream fs = new FileStream("C:\\Logs\\001_log.txt", FileMode.OpenOrCreate, FileAccess.Write, FileShare.Read);

    StreamWriter fp = new StreamWriter(fs);

    Parallel.For(0, table.Rows.Count, (k) =>

    {

    try

    {

    Int32 iReturn = ProcRegister((Int32)table.Rows[0][0]);

    fp.WriteLine(iReturn);

    fp.Flush();

    }

    catch{}

    finally{}

    });

    fp.Close();

    fp.Dispose();

    fs.Dispose();

    fs.Close();

    Part of the log file with problem:

    ...

    985217

    991848

    985680

    988684

    989989

    983342

    7367  983342 <---

    7367  983342 <---

    7367         <---

    984540

    986244

    986016

    984964

    991237

    ...

  • Rogerio, a StreamWriter instance is not safe to be used from multiple threads concurrently.  Try replacing:

    fp.WriteLine(iReturn);

    fp.Flush();

    with

    lock(fp) fp.WriteLine(iReturn);

    and see if that addresses the improper data.

  • RandomGen2 won't work for multiple threads as _local will not be initialized except for the first thread.

  • @has: No, that's not true.... on each invocation of Next, RandomGen2 checks to see whether _local is null (for that thread), and if it is, initializes it (for that thread).

  • Hi. Nice post, thought IMO this part in randomgen2:

    if (inst == null)

      int seed;

      lock (_global) seed = _global.Next();

      _local = inst = new Random(seed);

    }

    is unacceptable and it makes it run slower, than Randomgen1.

    It's supposed to contain only this line:

    return _local.Next();

    while _local would be initialized this way:

    private static Random _local = new Random(SeedInitializer());

    where

    private static int SeedInitializer()

    {

    lock (_global) return _global.Next();

    }

    Cheers :)

  • @Tarec: Thanks, though I'm not understanding your concern: that 'if' block is only executed the first time each thread accesses this function; all other invocations will see the instance as non-null and will fall through.  Have you actually measured a performance problem here?  Further, your proposed code is broken.  Your static variable is not marked as ThreadStatic, so multiple threads will all be sharing the same Random instance, which is not safe.  And if you mark it as ThreadStatic, then only one thread will actually run the cctor, and the other threads will all see their instance as null.

Page 2 of 2 (30 items) 12