Different summation results with Parallel.ForEach

Question

I have a foreach loop that I am parallelizing and I noticed something odd. The code looks like

double sum = 0.0;

Parallel.ForEach(myCollection, arg =>
{
     sum += ComplicatedFunction(arg);
});

// Use sum variable below

When I use a regular foreach loop I get different results. There may be something deeper down inside the ComplicatedFunction but it is possible that the sum variable is being unexpectantly affected by the parallelization?

Answer 1

You don't protect access to the sum variable. So you have a race-condition and the result is unpredictable. A variable int sum would have been atomic but a double sum is not. And the addition sum += ... is never thread-safe.

You could use something like:

double sum = myCollection.AsParallel().Sum(arg => ComplicatedFunction(arg));

Answer 2

If you think about that sum += ComplicatedFunctionas being actually composed of a bunch of operations, say:

r1 <- Load current value of sum
r2 <- ComplicatedFunction(...)
r1 <- r1 + r2

So now we randomly interleave two (or more) parallel instances of this. One thread may be holding a stale "old value" of sum which it uses to perform its computation, the result of which it writes back over top of some modified version of sum. It's a classic race condition, because some results are getting lost in a nondeterministic way based on how the interleaving is done.

Answer 3

Like the others answers mentioned, updating the sum variable from multiple threads (which is what Parallel.ForEach does) is not a thread-safe operation. The trivial fix of acquiring a lock before doing the update will fix that problem.

double sum = 0.0;
Parallel.ForEach(myCollection, arg => 
{ 
  lock (myCollection)
  {
    sum += ComplicatedFunction(arg);
  }
});

However, that introduces yet another problem. Since the lock is acquired on each iteration then that means the execution of each iteration will be effectively serialized. In other words, it would have been better to just use a plain old foreach loop.

Now, the trick in getting this right is to partition the problem in separate and independent chucks. Fortunately that is super easy to do when all you want to do is sum the result of the iterations because the sum operation is commutative and associative and because the intermediate results of the iterations are independent.

So here is how you do it.

double sum = 0.0;
Parallel.ForEach(myCollection,
    () => // Initializer
    {
        return 0D;
    },
    (item, state, subtotal) => // Loop body
    {
        return subtotal += ComplicatedFunction(item);
    },
    (subtotal) => // Accumulator
    {
        lock (myCollection)
        {
          sum += subtotal;
        }
    });