The correct way to do Parallel.For to calculate data from an array

Question

want: sum x and sum x * x. Where x = string [i]. Since more than one thread wants to read / write "sumAll" and "sumAllQ", I need to block its access. The problem is that the lock function disables the serialization of things here. I would need to break this operation down into # "Environment.ProcessorCount" for loops, each of which sums one part of the array and finally summarizes their results. But how can I do this programmatically?

Code example:

//line is a float[] Parallel.For(0, line.Length, new ParallelOptions { MaxDegreeOfParallelism = Environment.ProcessorCount }, i => { x = (double)line[i]; lock (sumLocker) { sumAll += x; sumAllQ += x * x; } }); 

EDIT 1: Matthew Watson meets test results

At home. CPU Core 2 Quad Q9550 @ 2.83 GHz:

 Result via Linq: SumAll=49999950000, SumAllQ=3,33332833333439E+15 Result via loop: SumAll=49999950000, SumAllQ=3,33332833333439E+15 Result via partition: SumAll=49999950000, SumAllQ=3,333328333335E+15 Via Linq took: 00:00:02.6983044 Via Loop took: 00:00:00.4811901 Via Partition took: 00:00:00.1595113 

At work. CPU i7 930 2.8 GHz:

 Result via Linq: SumAll=49999950000, SumAllQ=3,33332833333439E+15 Result via loop: SumAll=49999950000, SumAllQ=3,33332833333439E+15 Result via partition: SumAll=49999950000, SumAllQ=3,333328333335E+15 Via Linq took: 00:00:01.5728736 Via Loop took: 00:00:00.3436929 Via Partition took: 00:00:00.0934209 

Answer 1

As pointed out in the comments, you can use Aggregate to accomplish this using AsParallel in LINQ. For instance:

 using System.Linq; //A class to hold the results. //This can be improved by making it immutable and using a constructor. public class Result { public double SumAll { get; set; } public double SumAllQ { get; set; } } 

And you can use LINQ like this:

 var result = line.AsParallel().Aggregate(new Result(), (input, value) => new Result {SumAll = input.SumAll+value, SumAllQ = input.SumAllQ+value*value}); 

Or even better:

 var pline = line.AsParallel().WithDegreeOfParallelism(Environment.ProcessorCount); var result = new Result { SumAll = pline.Sum(), SumAllQ = pline.Sum(x => x * x) }; 

AsParallel does not allow you to specify parameters directly, but you can use .WithDegreeOfParallelism() , .WithExecutionMode() or .WithMergeOptions() to give you more control. You may need to use WithDegreeOfParallelism to even run it with multiple threads.

Answer 2

vcjones wondered if you really see acceleration. Good answer: perhaps it depends on how many kernels you have. PLinq is slower than a simple loop on my home PC (it's a quad-core processor).

I came up with an alternative approach that Partitioner uses to split the list of numbers into several sections so that you can add each separately. There is also more information on using Partitioner here .

Using the Partitioner approach seems a little faster, at least on my home PC.

Here is my test program. Note that you must run release builds outside of any debugger in order to get the correct timings.

An important method in this code is ViaPartition() :

 Result ViaPartition(double[] numbers) { var result = new Result(); var rangePartitioner = Partitioner.Create(0, numbers.Length); Parallel.ForEach(rangePartitioner, (range, loopState) => { var subtotal = new Result(); for (int i = range.Item1; i < range.Item2; i++) { double n = numbers[i]; subtotal.SumAll += n; subtotal.SumAllQ += n*n; } lock (result) { result.SumAll += subtotal.SumAll; result.SumAllQ += subtotal.SumAllQ; } }); return result; } 

My results when running the full test program (shown below these results):

 Result via Linq: SumAll=49999950000, SumAllQ=3.33332833333439E+15 Result via loop: SumAll=49999950000, SumAllQ=3.33332833333439E+15 Result via partition: SumAll=49999950000, SumAllQ=3.333328333335E+15 Via Linq took: 00:00:01.1994524 Via Loop took: 00:00:00.2357107 Via Partition took: 00:00:00.0756707 

(Note the slight differences due to rounding errors.)

It would be interesting to see the results of other systems.

Here's the full test program:

 using System; using System.Collections.Concurrent; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Threading.Tasks; namespace Demo { public class Result { public double SumAll; public double SumAllQ; public override string ToString() { return string.Format("SumAll={0}, SumAllQ={1}", SumAll, SumAllQ); } } class Program { void run() { var numbers = Enumerable.Range(0, 1000000).Select(n => n/10.0).ToArray(); // Prove that the calculation is correct. Console.WriteLine("Result via Linq: " + ViaLinq(numbers)); Console.WriteLine("Result via loop: " + ViaLoop(numbers)); Console.WriteLine("Result via partition: " + ViaPartition(numbers)); int count = 100; TimeViaLinq(numbers, count); TimeViaLoop(numbers, count); TimeViaPartition(numbers, count); } void TimeViaLinq(double[] numbers, int count) { var sw = Stopwatch.StartNew(); for (int i = 0; i < count; ++i) ViaLinq(numbers); Console.WriteLine("Via Linq took: " + sw.Elapsed); } void TimeViaLoop(double[] numbers, int count) { var sw = Stopwatch.StartNew(); for (int i = 0; i < count; ++i) ViaLoop(numbers); Console.WriteLine("Via Loop took: " + sw.Elapsed); } void TimeViaPartition(double[] numbers, int count) { var sw = Stopwatch.StartNew(); for (int i = 0; i < count; ++i) ViaPartition(numbers); Console.WriteLine("Via Partition took: " + sw.Elapsed); } Result ViaLinq(double[] numbers) { return numbers.AsParallel().Aggregate(new Result(), (input, value) => new Result { SumAll = input.SumAll+value, SumAllQ = input.SumAllQ+value*value }); } Result ViaLoop(double[] numbers) { var result = new Result(); for (int i = 0; i < numbers.Length; ++i) { double n = numbers[i]; result.SumAll += n; result.SumAllQ += n*n; } return result; } Result ViaPartition(double[] numbers) { var result = new Result(); var rangePartitioner = Partitioner.Create(0, numbers.Length); Parallel.ForEach(rangePartitioner, (range, loopState) => { var subtotal = new Result(); for (int i = range.Item1; i < range.Item2; i++) { double n = numbers[i]; subtotal.SumAll += n; subtotal.SumAllQ += n*n; } lock (result) { result.SumAll += subtotal.SumAll; result.SumAllQ += subtotal.SumAllQ; } }); return result; } static void Main() { new Program().run(); } } }