wrong results with parallel for?

Fri, 12 Jun 2009 20:00:53 Z

Hi,

I was just trying the new Parallel extension with .NET 4.0 Beta in C#.
Actually I want to compare time results between sequential and parallel for-loops but then I found something strange:
When running a simple code which sums up array values I got wrong results with parallel execution. This seems to happen with iterations > about 10 000.

Here is the source Code:

using System;
using System.Collections.Generic;
using System.Threading;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] numbers = Enumerable.Range(0, 1000000).ToArray();
            long total = 0;
            Stopwatch clock = new Stopwatch();

            Console.WriteLine("With Parallelization:");
            clock.Start();
            Parallel.For(0, numbers.Length, i =>
            {
                total += numbers[i];
            }
              );
            clock.Stop();
            Console.WriteLine("Result: " + total);
            Console.WriteLine("Time: " + clock.ElapsedMilliseconds);
            total = 0;
            clock.Reset();

            Console.WriteLine("Without Parallelization:");
            clock.Start();
            for (int i = 0; i < numbers.Length; i++)
            {
                total += numbers[i];
            }
            clock.Stop();
            Console.WriteLine("Result: " + total);
            Console.WriteLine("Time: " + clock.ElapsedMilliseconds);
            clock.Reset();
            Console.ReadLine();
        }

    }
}

And here are the results:

With Parallelization:
Result: 224897535827
Time: 48
Without Parallelization:
Result: 499999500000
Time: 6

The strange thing is that the results of parallel execution seems to differ for each run:

With Parallelization:
Result: 209604538631
Time: 60
Without Parallelization:
Result: 499999500000
Time: 6

Am I doing something wrong? Or is this a bug?

Regards,
Alex

wrong results with parallel for?

Fri, 12 Jun 2009 20:16:39 Z

Hi Alex,

Your parallel for is wrong because your aren't protecting the total against concurrent access - total += numbers[i] is called from withing multiple threads at the same time and this operation isn't thread safe.
Here is a correct version using subtotals (each thread calculates its subtotal and all subtotals are safely added together by Interlocked.Add operation:

Parallel.For<long>(0, numbers.Length,
                // init subtotal
                () => 0,  
                (i, loop, subtotal)  =>
                  {
                    subtotal += numbers[i];
                    return subtotal;
                  },
                // add subtotal to total value
                (subtotal) => Interlocked.Add(ref total, subtotal)
              );

Miha Markic [MVP C#] http://blog.rthand.com

wrong results with parallel for?

Fri, 12 Jun 2009 20:30:06 Z

Thanks a lot Miha.