.Net Parallel.For strange behavior

Question

I brute-forced summing of all primes under 2000000. After that, just for fun I tried to parallel my for, but I was a little bit surprised when I saw that Parallel.For gives me an incorrect sum!

Here's my code : (C#)

static class Problem
{
    public static long Solution()
    {
        long sum = 0;
        //Correct result is 142913828922
        //Parallel.For(2, 2000000, i =>
        //                             {
        //                                 if (IsPrime(i)) sum += i;
        //                             });
        for (int i = 2; i < 2000000; i++)
        {
            if (IsPrime(i)) sum += i;
        }
        return sum;
    }
    private static bool IsPrime(int value)
    {
        for (int i = 2; i <= (int)Math.Sqrt(value); i++)
        {
            if (value % i == 0) return false;
        }
        return true;
    }
}

I know that brute-force is pretty bad solution here but that is not a question about that. I think I've made some very stupid mistake, but I just can't locate it. So, for is calculating correctly, but Parallel.For is not.

possible duplicate of [Parallel.For(): Update variable outside of loop](http://stackoverflow.com/questions/2774170/parallel-for-update-variable-outside-of-loop) — Mark Byers, Jul 31 '10 at 12:14
And exact duplicate of [Different summation results with Parallel.ForEach](http://stackoverflow.com/questions/3367293/different-summation-results-with-parallel-foreach/3367311#3367311) — H H, Jul 31 '10 at 13:34

Mark Byers · Accepted Answer · 2010-07-31T13:28:20.427

4

You are accessing the variable sum from multiple threads without locking it, so it is possible that the read / write operations become overlapped.

Adding a lock will correct the result (but you will be effectively serializing the computation, losing the benefit you were aiming for).

You should instead calculate a subtotal on each thread and add the sub-totals at the end. See the article How to: Write a Parallel.For Loop That Has Thread-Local Variables on MSDN for more details.

long total = 0;

// Use type parameter to make subtotal a long, not an int
Parallel.For<long>(0, nums.Length, () => 0, (j, loop, subtotal) =>
{
    subtotal += nums[j];
    return subtotal;
},
    (x) => Interlocked.Add(ref total, x)
);

edited Jul 31 '10 at 13:28

answered Jul 31 '10 at 12:12

Mark Byers

811,555
193
1,581
1,452

But I thought Parallel.For is doing all the job for synchronizing threads and locking variables... – illegal-immigrant Jul 31 '10 at 12:14
2

@tars.roshko: What does being a value type have to do with whether or not you should lock? The two concepts are totally unrelated. – Mark Byers Jul 31 '10 at 13:34

score 0 · Answer 2 · answered Jul 31 '10 at 12:23

0

Many thanks to all of you for your quick answers i changed

sum += i; to Interlocked.Add(ref sum,i);

and now it works great.

answered Jul 31 '10 at 12:23

illegal-immigrant

8,089
9
51
84

3

It will give the correct result but now you've lost the benefit of parallelizing as you are effectively serializing the calculation. – Mark Byers Jul 31 '10 at 13:30

.Net Parallel.For strange behavior

2 Answers2