Parallelizing method with foreach loop C#

Shand Ramzi

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

5 Replies

Know the answer? Post it — somebody with the same question will find it here.

Vulpes15y ago
Accepted 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)
{
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.
Vulpes15y ago
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.
Shand Ramzi15y ago
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?
Vulpes15y ago
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 Ramzi15y ago
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.