parallel.foreach works, but why?

Question

Can anyone explain, why this program is returning 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 by sheer luck. Sometimes when you run it you are lucky that the non-atomic reads and writes to the double are not resulting in "torn" values. Sometimes you are lucky that the non-atomic tests and sets just happen to be setting the correct value when that race happens. There is no guarantee that this program produces any particular result.

Answer 2

Your code is not safe; it only works by coincidence.

If two threads run the if simultaneously, one of the minimums will be overwritten:

• sqrt_min = 6
• Thread A: sqrt = 5
• Thread B: sqrt = 4
• Thread A enters the if
• Thread B enters the if
• Thread B assigns sqrt_min = 4
• Thread A assigns sqrt_min = 5

On 32-bit systems, you're also vulnerable to read/write tearing.

It would be possible to make this safe using Interlocked.CompareExchange in a loop.

Answer 3

For why your original code is broken check the other answers, I won't repeat that.

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

You can rewrite your code to:

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

In your specific problem it's faster to swap around the Min and the Sqrt operation, which is possible because Sqrt is monotonically increasing.

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

Answer 4

Your code does not really work: I ran it in a loop 100,000 times, and it failed once on my 8-core computer, producing this output:

minimum: 1

I shortened the runs to make the error appear 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, considering the lack of synchronization around the reading and writing of a shared variable.

Answer 5

As others have said, this only works based on shear luck. Both the OP and other posters have had trouble actually creating the race condition though. That is fairly easily explained. The code generates lots of race conditions, but the vast majority of them (99.9999% to be exact) are irrelevant. All that matters at the end of the day is the fact that 0 should be the min result. If your code thinks that root 5 is greater than root 6, or that root 234 is greater than root 235 it still won't break. There needs to be a race condition specifically with the iteration generating 0. The odds that one of the iterations has a race condition with another is very, very high. The odds that the iteration processing the last item has a race condition is really quite low.