Getting random numbers in a thread-safe way

Getting random numbers in a thread-safe way

Rate This
  • Comments 32

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 4 and 7 and type the answer here:
  • Post
  • Are you sure that a sequence of random numbers that is generated by n different instances of Random, where each instance gets its seed from a sequence of n numbers generated by a further instance of Random, has the same statistical properties of randomness that you get if you had generated the sequence just with one instance of Random?

  • It almost certainly does not.  But then again, I was going for "good enough" ;)  If I really cared about the quality of the numbers, I would use RNGCryptoServieProvider.  I'm just trying to escape the hazards of getting back all 0s, or having all of the threads seeing the exact same numbers.  This is a fair compromise if the statistical properties beyond that aren't that important.

  • Well, one interesting question would be whether it is at least as good as one instance of Random, and if not how much worse. After all, there are lots of cases where Random is just fine, but the multi instance with seeds from one central Random instance would not. Maybe a warning in the text of this post a la "using this you will get random numbers that are in an unknown way less random than the non parallel version" would be good.

    Also, this would be a nice addition to the framework, to have better rng creation, both with parallel support and also maybe things like Mersenne Twister. It is the kind of thing that really should be implemented in the platform and then be tested properly.

  • Thanks, David.  I was hoping that point was clear in my post, but apparently it wasn't; I've added an addendum to be more explicit about it.  Folks can of course also read your comments.

    If you have a specific example where the "multi instance with seeds would not" be fine, I'm sure readers would appreciate seeing it.  It'd also be interesting to then see if that example suffers from the same problem when RNGCryptoServieProvider is used as the seed generator instead of Random, as is done at the end of the post.

  • Interesting - I've had a "static random" class for a long time (http://pobox.com/~skeet/csharp/miscutil/usage/staticrandom.html)

    My original implementation was to use ThreadStatic, but when I performance-tested that (can't remember the number of cores, I'm afraid - but back in .NET 2.0) it was a lot slower than using a lock (which is my current implementation). Sounds like I should change the implementation back to using ThreadStatic...

  • Just remember the other thing I should have said: It's annoying that System.Random doesn't implement an interface. Otherwise we could plug in alternative thread-safe implementations really easily...

  • Hi Jon-

    re: ThreadStatic

    Yeah, in the past it hasn't been the fastest thing in the world.  But it's getting better. :)

    re: Random doesn't implement an interface

    It doesn't, but its public methods are all virtual, so you can achieve a very similar thing with a derived type:

    public sealed class ThreadSafeRandom : Random

    {

       private object _lock = new object();

       public override int Next()

       {

           lock(_lock) return base.Next();

       }

       public override int Next(int maxValue)

       {

           lock(_lock) return base.Next(maxValue);

       }

       public override int Next(int minValue, int maxValue)

       {

           lock(_lock) return base.Next(minValue, maxValue);

       }

       public override void NextBytes(byte[] buffer)

       {

           lock(_lock) base.NextBytes(buffer);

       }

       public override double NextDouble()

       {

           lock(_lock) return base.NextDouble();

       }

    }

    ...

    Random r = new ThreadSafeRandom();

  • Yes, I'm not sure why I hadn't noticed the virtual aspect before. It's a shame that the inheritance side is a little bit complicated (as described in the main docs for Random). It would be nice to have the stateless parts, and then *just* the call to Sample which would be (potentially) mutating. That way we'd only need to worry about locking Sample. It looks like that would have worked in .NET 1.0/1.1, but not .NET 2.0.

    One nice thing about using Random is that we can easily allow the caller to ask for the right kind of thread safety based on their requirements:

    public class ThreadSafeRandom

    {

       // LockedRandom would be a private nested class of

       // ThreadSafeRandom, implemented as per your

       // comment

       private static Random singleton = new LockedRandom();

       public static Random LockedInstance

       {

           get { return singleton; }

       }

       [ThreadStatic]

       private static Random perThreadInstance;

       public static Random PerThreadInstance

       {

           get

           {

               if (perThreadInstance == null)

               {

                   perThreadInstance = new Random();

               }

               return perThreadInstance;

           }

       }

    }

    Something like that, anyway.

  • I will make a bugreport concerning Parallel.For syntax. If it's for, then it should be for, prefixed by 'parallel' to denote its different nature:

    parallel for (;;) {

    }

    Parallel.For is a weird construct which doesn't fit in with for. Pretty Pascalish, isn't it?

  • Thanks for the suggestion, chojrak11.  While that syntax may some day be something we look to do (remembering that there are plenty of other .NET languages besides C#), it's not possible today without language support, whereas everything we've done for this release is library-based.  Parallel.For is a method call, rather than a keyword.

  • Thanks for greate article. A minor suggestion. I think your latest class RandomGen3 has a concurrency issue. I'd change

    _global.GetBytes(buffer);

    to

    lock(_global) _global.GetBytes(buffer);

    that's because for the RNGCryptoServiceProvider class we are said: Any public static (Shared in Visual Basic) members of this type are thread safe. Any instance members are not guaranteed to be thread safe.

  • Thanks, holoduke.  As it happens, instances of RNGCryptoServiceProvider created with the default parameters actually are thread-safe for this usage, but since the documentation doesn't call that out, it's an implementation detail that could change in the future, and thus I'm taking a bit of a risk by relying on it.  Regardless, glad you enjoyed the post.

  • PingBack from http://blogs.techrepublic.com.com/programming-and-development/?p=917

  • Thanks for the post.  Here's a VB.NET version that inherits the Random class so you have all of the functionality of the built in Random class without it's shortcomings discussed above.  The Sample() function is used by the rest of the Random class to generate a random number between 0 and 1 and then use it to get the requested range from all of the overloaded Next() calls.

       Public Class TSLRandom

           Inherits Random

           Private Shared _global As New Random()

           <ThreadStatic()> _

           Private Shared _local As Random

           Protected Overrides Function Sample() As Double

               Dim inst As Random = _local

               Dim seed As Integer

               If inst Is Nothing Then

                   SyncLock _global

                       seed = _global.Next()

                       _local = New Random(seed)

                       inst = _local

                   End SyncLock

               End If

               Return inst.NextDouble()

           End Function

       End Class

  • PingBack from http://portablegreenhousesite.info/story.php?id=15439

Page 1 of 3 (32 items) 123