.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.

Answer 1

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

Answer 2

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.