Nested Parallel.ForEach Loops on the same list?

Question

I need to parallelize a method that does an exhaustive pairwise comparison on elements in a list. The serial implementation is straight-forward:

foreach (var element1 in list)
    foreach (var element2 in list)
        foo(element1, element2);

In this case, foo won't alter the state of element1 or element2. I know it's not safe to simply do nested Parallel.ForEach statements:

Parallel.ForEach(list, delegate(A element1)
{
    Parallel.ForEach(list, delegate(A element2)
    {
        foo(element1, element2);
    });
});

What would be the ideal way to implement this using the parallel tasks library?

Answer 1

At least if you are executing the code on a machine where the number of cores is at least twice the number of items in the list, I'm not sure it is a good idea to do embedded Parallel.ForEachs.

In other words, if you target a quad-core, and the list has one thousand items, just parallelize the parent loop. Parallelizing both loops would not make the code faster, but rather much, much slower, since parallel tasks have performance cost.

alt text http://www.freeimagehosting.net/uploads/ca97f403f8.png

At each iteration, a few milliseconds will be lost by Parallel.ForEach to determine which thread must execute the next iteration. Let's say you have a set of 7 items. If you parallelize the parent loop, those milliseconds will be lost 7 times. If you parallelize both loops, they will be lost 7×7=49 times instead. Larger is the set, bigger is the overheat.

Answer 2

Couldn't you just have one Parallel and one normal loop? So either

Parallel.ForEach(list, delegate(A element1)
{
  foreach(A element2 in list)
    foo(element1, element2)
});

or

foreach(A element1 in list)
{
  Parallel.ForEach(list, delegate(A element2)
  {
    foo(element1, element2);
  });
}

Should speed it up as well. There was never going to be a thread per cycle anyway, so this would probably be just as fast or slightly slower than nested parallel loops.