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);

see also http://stackoverflow.com/questions/3679209/why-doesnt-this-code-demonstrate-the-non-atomicity-of-reads-writes it may not be luck. It may be because your cpu delivers atomic double operations even though c# does not guarantee it. — hatchet - done with SOverflow, Feb 06 '12 at 20:00
There's a possibility that fixing this bug will introduce enough lock contention that it will be slower than just calculating the square roots on one thread. A better solution would be to have each CPU calculate many square roots, keeping track of their own minimums, and finding the global minimum when every CPU is done. You'll still have contention, but the contention will only apply while comparing thread-specific local minimums, rather than for every single square root. — Brian, Feb 06 '12 at 20:46

score 13 · Accepted Answer · answered Feb 06 '12 at 19:49

13

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.

answered Feb 06 '12 at 19:49

Eric Lippert

647,829
179
1,238
2,067

1

@user1193134: In general, locks or (extremely careful) atomic operations. In your particular case, PLINQ `Aggregate()` or just `Min()`. – SLaks Feb 06 '12 at 19:55
could you give me a hand in solving this problem? – user1193134 Feb 06 '12 at 20:14
3

@user1193134: I think I already did help you. Parallel ForEach does not magically make your code threadsafe. If you want it to be threadsafe, *make it threadsafe*. How you choose to do that is up to you; I don't know what your requirements are. – Eric Lippert Feb 06 '12 at 20:36

SLaks · Answer 2 · 2012-02-06T19:51:55.203

5

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.

edited Feb 06 '12 at 19:51

answered Feb 06 '12 at 19:46

SLaks

868,454
176
1,908
1,964

that is what i thought! But i've never get to this point! Even by trying very hard and quite a lot of times > 10^9 – user1193134 Feb 06 '12 at 19:52
@user1193134: The size of the array doesn't really matter (unless you have hundreds of cores). Using dasblinkenlight's modification, I get consistent failures. – SLaks Feb 06 '12 at 19:57
you seem very familiar with the Interlocked.CompareExchange thing. May you give me a hand with the problem? – user1193134 Feb 06 '12 at 19:59
Unfortunately, I don't have time now; sorry. – SLaks Feb 06 '12 at 20:27

score 4 · Answer 3 · answered Feb 06 '12 at 20:51

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())

score 3 · Answer 4 · answered Feb 06 '12 at 19:55

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.

score 2 · Answer 5 · answered Feb 06 '12 at 20:06

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.

parallel.foreach works, but why?

5 Answers5