The simulation gives an excellent result with the normal for the Vs Parallel For loop

Question

I am a little surprised by the different results for one of my simple modeling samples when I tried with a normal loop (which is the correct result) Vs Parallel For. Please help me find the reason. I noticed that concurrent execution compares so quickly with regular execution.

using System; using System.Collections.Generic; using System.Threading.Tasks; namespace Simulation { class Program { static void Main(string[] args) { ParalelSimulation(); // result is .757056 NormalSimulation(); // result is .508021 which is correct Console.ReadLine(); } static void ParalelSimulation() { DateTime startTime = DateTime.Now; int trails = 1000000; int numberofpeople = 23; Random rnd = new Random(); int matches = 0; Parallel.For(0, trails, i => { var taken = new List<int>(); for (int k = 0; k < numberofpeople; k++) { var day = rnd.Next(1, 365); if (taken.Contains(day)) { matches += 1; break; } taken.Add(day); } } ); Console.WriteLine((Convert.ToDouble(matches) / trails).ToString()); TimeSpan ts = DateTime.Now.Subtract(startTime); Console.WriteLine("Paralel Time Elapsed: {0} Seconds:MilliSeconds", ts.Seconds + ":" + ts.Milliseconds); } static void NormalSimulation() { DateTime startTime = DateTime.Now; int trails = 1000000; int numberofpeople = 23; Random rnd = new Random(); int matches = 0; for (int j = 0; j < trails; j++) { var taken = new List<int>(); for (int i = 0; i < numberofpeople; i++) { var day = rnd.Next(1, 365); if (taken.Contains(day)) { matches += 1; break; } taken.Add(day); } } Console.WriteLine((Convert.ToDouble(matches) / trails).ToString()); TimeSpan ts = DateTime.Now.Subtract(startTime); Console.WriteLine(" Time Elapsed: {0} Seconds:MilliSeconds", ts.Seconds + ":" + ts.Milliseconds); } } 

}

Thanks at Advance

Answer 1

The code contains the race data updates matches . If two threads do this at the same time, both can read the same value (for example, 10), then both increase it (to 11) and write the new value back. As a result, there will be fewer registered matches (in my example 11 instead of 12). The solution is to use System.Threading.Interlocked for this variable.

Other questions I see:
- your serial loop includes an iteration for j equal to trails , while a parallel loop is not (the final index is exceptional in Parallel.For );
- class Random may not be stream safe.

---

Update: I think you will not get the result you want with the Drew Marsh code, because it does not provide sufficient randomization. Each 1M experiment starts with exactly the same random number, because you initiate all local instances of Random with a default value. Essentially, you are repeating the same experiment 1M times, so the result is still distorted. To fix this, you need to take each randomizer with a new value each time. Update: I was not quite right here, since initialization uses the system clock for seed by default; however, MSDN warns that

since the clock has finite resolution, using a constructor without parameters to create different random objects with a close sequence creates random number generators that produce identical sequences of random numbers.

Thus, this can be the reason for insufficient randomization, and with explicit seeds you can get better results. For example, initializing with the iteration number of the outer loop gave me a good answer:

 Parallel.For(0, trails + 1, j => { Random rnd = new Random(j); // initialized with different seed each time /* ... */ }); 

However, I noticed that after the initialization of Random was transferred to the loop, all the acceleration was lost (on my Intel Core i5 laptop). Since I'm not a C # specialist, I don't know why; but I believe that the Random class may have some data shared by all instances with access synchronization.

---

Update 2: using ThreadLocal to store one instance of Random for a thread, I have good accuracy and reasonable speedup:

 ThreadLocal<Random> ThreadRnd = new ThreadLocal<Random>(() => { return new Random(Thread.CurrentThread.GetHashCode()); }); Parallel.For(0, trails + 1, j => { Random rnd = ThreadRnd.Value; /* ... */ }); 

Notice how the randomizers in the thread are initialized with a hash code for the current executable instance of Thread .

Answer 2

A few things:

• The Random class is not thread safe. You will need a new instance of Random for each workflow.
• You increment the matches variable in an unsafe way. You would like to use Interlocked.Increment(ref matches) to guarantee thread safety when the variable is incremented.
• Your for loop and your Parallel :: For do not execute exactly the same number of times, because you do a <= in your for loop and Parallel :: For for the second parameter, so you need to add 1 to the paths in this case to make them equivalent .

Try the following:

 static void ParalelSimulationNEW() { DateTime startTime = DateTime.Now; int trails = 1000000; int numberofpeople = 23; int matches = 0; Parallel.For(0, trails + 1, _ => { Random rnd = new Random(); var taken = new List<int>(); for(int k = 0; k < numberofpeople; k++) { var day = rnd.Next(1, 365); if(taken.Contains(day)) { Interlocked.Increment(ref matches); break; } taken.Add(day); } }); Console.WriteLine((Convert.ToDouble(matches) / trails).ToString()); TimeSpan ts = DateTime.Now.Subtract(startTime); Console.WriteLine("Paralel Time Elapsed: {0} Seconds:MilliSeconds", ts.Seconds + ":" + ts.Milliseconds); }