Parallelizing method with foreach loop C#

Question

Hello.

So I am currently working on a project and now I feel the need to try and speed up the execution. I have a method with a foreach loop in it that I wish to parallelize as efficiently as possible.

This is how it looks now:

public void Simulate()
{
List<Coordinate> Locations = retrieveLocations();

int min = int.MaxValue;
int bestX = -1, bestY = -1;

foreach (Coordinate currPos in Locations)
{
string[,] tempMap = new string[globalMap.GetLength(0), globalMap.GetLength(1)];
matrixCopy(globalMap, tempMap);

int result = processData(currPos, tempMap);

if (result < min)
{
min = result;
bestX = currPos.X;
bestY = currPos.Y;
}
}

MessageBox.Show(bestX + " " + bestY + " " + min);
}

I would like to change the foreach loop to use Parallel.ForEach or perhaps use PLINQ. My concerns are how I can find the minimal value with as little locking as possible. Also I want to preserve some other values than just the minimum.

Another issue is the globalMap, is it good to copy it like I do now? All threads can't work on the original at the same time because they change the data. But perhaps I should do the copy in my processData()-method? Any thoughts?

Vulpes · Answer

To avoid locking within the Parallel.Foreach you could use a System.Collections.Concurrent.ConcurrentBag to store a tuple of the result and its associated Coordinate. You could then work out min bestX and bestY in a separate non-parallel foreach loop which should require relatively little processing. The code would be something like this: public void Simulate() { List Locations = retrieveLocations(); int min = int.MaxValue; int bestX = -1 bestY = -1; var bag = new ConcurrentBag >(); Parallel.ForEach(Locations currPos => { string[] tempMap = new string[globalMap.GetLength(0) globalMap.GetLength(1)]; matrixCopy(globalMap tempMap); int result = processData(currPos tempMap); bag.Add(Tuple.Create(currPos result)); } ); foreach(var t in bag) { Coordinate currPos = t.Item1; int result = t.Item2; if (result { min = result; bestX = currPos.X; bestY = currPos.Y; } } MessageBox.Show(bestX +   + bestY +   + min); } As you say the globalMap will need to be copied but I doubt whether it will make much difference where you do it. You could try it both ways and see if there's any difference in performance.

Vulpes · Answer

Well you could use a nested query: Tuple minTuple = bag.AsParallel().Where(t => t.Item2 == bag.AsParallel().Min(t => t.Item2)).First(); but for me that's not as clear as having two queries and it certainly won't be any quicker. As 'min' is inevitably a number I can't see how else you can do it using the extension methods at our disposal. If anyone has a better solution which is at least as efficient as mine then I'd be interested to know what it is.

Vulpes · Answer

Yes you could replace the final foreach with the following PLINQ queries though with only 1000 objects I'd be surprised if it was appreciably quicker: min = bag.AsParallel().Min(t => t.Item2); Tuple minTuple = bag.AsParallel().Where(t => t.Item2 == min).First(); bestX = minTuple.Item1.X; bestY = minTuple.Item1.Y; MessageBox.Show(bestX +   + bestY +   + min); You could also do it by sorting though I think that would definitely be slower: Tuple minTuple = bag.AsParallel().OrderBy(t => t.Item2).First(); min = minTuple.Item2; bestX = minTuple.Item1.X; bestY = minTuple.Item1.Y; MessageBox.Show(bestX +   + bestY +   + min); Notice that if there were more than one minimum result then these approaches might not necessarily return the same Coordinate object as the foreach loop.

Shand Ramzi · Answer

Alright that looks good. But can't you change these two lines min = bag.AsParallel().Min(t => t.Item2); Tuple minTuple = bag.AsParallel().Where(t => t.Item2 == min).First(); To only be one statement? Can't I have min = bag.AsParallel().Min(t => t.Item2); return a tuple right away? I mean it feels like I should be able to do it with one statement instead of in practice looping through the bag twice. Can't I traverse the bag looking for the min value of Item2 and have it return the full tuple right away instead of only the int part?

Shand Ramzi · Answer

Thanks that looks like a nice way to do it. I knew about ConcurrentBag before but I was too caught up in more complicated solutions. My list of locations will only be around 1000 objects so I think your way will work great. I'm currently trying to learn (P)LINQ also. Would there be a way to go through the bag and find the minimum object (according to some criteria) with (P)LINQ? I mean replacing the final foreach with a (P)LINQ statement. Could be good to learn.