Random generates number 1 more than 90% of times in parallel [duplicate]

Question

Consider the following program:

public class Program
{
     private static Random _rnd = new Random();
     private static readonly int ITERATIONS = 5000000;
     private static readonly int RANDOM_MAX = 101;

     public static void Main(string[] args)
     {
          ConcurrentDictionary<int,int> dic = new ConcurrentDictionary<int,int>();

          Parallel.For(0, ITERATIONS, _ => dic.AddOrUpdate(_rnd.Next(1, RANDOM_MAX), 1, (k, v) => v + 1));

          foreach(var kv in dic)
             Console.WriteLine("{0} -> {1:0.00}%", kv.Key, ((double)kv.Value / ITERATIONS) * 100);
     }
}

This will print the following output:

(Note that the output will vary on each execution)

> 1 -> 97,38%
> 2 -> 0,03%
> 3 -> 0,03%
> 4 -> 0,03%
...
> 99 -> 0,03%
> 100 -> 0,03%

Why is the number 1 generated with such frequency?

Answer 1

Random is not thread safe.

Next does nothing special at all to ensure thread safety.

Don't use Random like this. And don't consider using thread local storage duration either, else you will mess up the generator's statistical properties: You must only use one Random instance. One approach will be to use lock(_global) and draw a number in that locked region.

I think what's happening here is that the first thread to reach the generator gets its random numbers generated correctly, and all subsequent threads receive 0 for each drawing. With a "parallelisation" thread pool of 32 threads, the ratios you cite above are approximately attainted; assuming that the results for the 31 threads are placed in the first bucket.

Answer 2

Going one step further from the thread local storage solution, and trying to avoid the statistical issue, I suggest to use a random seed generated from RNGCryptoServiceProvider:

using System;
using System.Collections.Concurrent;
using System.Threading;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class Program
    {

        private static readonly int ITERATIONS = 5000000;
        private static readonly int RANDOM_MAX = 101;

        private static int GetCriptoRandom()
        {
            using (var rng = new System.Security.Cryptography.RNGCryptoServiceProvider())
            {
                byte[] bytes = new byte[4];
                rng.GetBytes(bytes);
                return BitConverter.ToInt32(bytes, 0);
            }
        }

        private static ThreadLocal<Random> m_rnd = new ThreadLocal<Random>(() => new Random(GetCryptoRandom()));

        private static Random _rnd
        {
            get
            {
                return m_rnd.Value;
            }
        }

        static void Main(string[] args)
        {
            ConcurrentDictionary<int, int> dic = new ConcurrentDictionary<int, int>();
            Parallel.For(1, ITERATIONS, _ => dic.AddOrUpdate(_rnd.Next(1, RANDOM_MAX), 1, (k, v) => v + 1));
            foreach (var kv in dic)
                Console.WriteLine("{0} -> {1:0.00}%", kv.Key, ((double)kv.Value / ITERATIONS) * 100);

        }
    }
}

It seems statistically correct, results range from 0.99% to 1.01%.