Parallel.foreach works, but why?

Question

Can someone explain why this program returns the correct value for sqrt_min?

int n = 1000000; double[] myArr = new double[n]; for(int i = n-1 ; i>= 0; i--){ myArr[i] = (double)i;} // sqrt_min contains minimal sqrt-value double sqrt_min = double.MaxValue; Parallel.ForEach(myArr, num => { double sqrt = Math.Sqrt(num); // some time consuming calculation that should be parallized if(sqrt < sqrt_min){ sqrt_min = sqrt;} }); Console.WriteLine("minimum: "+sqrt_min); 

Answer 1

It works out of luck. Sometimes, when you run it, you are lucky that non-atomic reads and writes in double do not lead to a "gap" of values. Sometimes you are lucky that non-nuclear tests and kits just set the right value when this race takes place. There is no guarantee that this program will produce any specific result.

Answer 2

Your code is unsafe; It works only by coincidence.

If two threads start if at the same time, one of the minima will be overwritten:

• sqrt_min = 6
• Topic A: sqrt = 5
• Topic B: sqrt = 4
• Topic A is included in if
• Thread B is included in if
• Thread B assigns sqrt_min = 4
• Topic A assigns sqrt_min = 5

On 32-bit systems, you are also vulnerable to read / write breaks.

One could make this safe using Interlocked.CompareExchange in a loop.

Answer 3

Why is your source code broken, check other answers, I will not repeat this.

Multithreading is easiest when there is no write access to the general state. Fortunately, your code can be written that way. Parallel linq can be nice in such situations, but sometimes there is too much overhead.

You can rewrite your code on:

 double sqrt_min = myArr.AsParallel().Select(x=>Math.Sqrt(x)).Min(); 

In your specific task, it is faster to exchange Min and Sqrt , which is possible because Sqrt monotonically increasing.

 double sqrt_min = Math.Sqrt(myArr.AsParallel().Min()) 

Answer 4

Your code actually doesn't work: I ran it in a loop 100,000 times, and it failed once on my 8-core computer, issuing this output:

 minimum: 1 

I shortened the runs so that the error appears faster.

Here are my modifications:

 static void Run() { int n = 10; double[] myArr = new double[n]; for (int i = n - 1; i >= 0; i--) { myArr[i] = (double)i*i; } // sqrt_min contains minimal sqrt-value double sqrt_min = double.MaxValue; Parallel.ForEach(myArr, num => { double sqrt = Math.Sqrt(num); // some time consuming calculation that should be parallized if (sqrt < sqrt_min) { sqrt_min = sqrt; } }); if (sqrt_min > 0) { Console.WriteLine("minimum: " + sqrt_min); } } static void Main() { for (int i = 0; i != 100000; i++ ) { Run(); } } 

This is not a coincidence, given the lack of synchronization around the reading and writing of a shared variable.

Answer 5

As others have said, this only works on the basis of shear luck. However, both the OP and other posters had problems creating the race condition. This is pretty easy to explain. The code generates many race conditions, but the vast majority of them (99.9999%, to be precise) do not matter. All that matters at the end of the day is the fact that 0 should be a minimal result. If your code believes that root 5 is larger than root 6, or that root 234 is larger than root 235, it still won't break. There must be a race condition, in particular with an iteration generating 0. The probability that one of the iterations has a race state with another is very, very high. The chances that the iteration processing the last element has a race state are really quite low.