同一个列表上的嵌套Parallel.ForEach循环？

Question

我需要并行化一个方法，对列表中的元素进行穷尽的成对比较。串行实现很直接：

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

在这种情况下，foo 不会改变 element1 或 element2 的状态。我知道简单地使用嵌套的 Parallel.ForEach 语句是不安全的。

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

使用并行任务库，最理想的实现方式是什么？

- Wesley Tansey

Answer 1

至少在执行代码的机器上，核心数至少是列表项数的两倍，我不确定嵌套使用Parallel.ForEach是一个好主意。

换句话说，如果你的目标是四核心，并且列表有一千个项目，只需并行化父循环即可。同时并行化两个循环不会加快代码运行速度，反而会使代码运行慢得多，因为并行任务需要付出性能代价。

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

在每次迭代中，Parallel.ForEach将损失几毫秒来确定下一个迭代要执行的线程。假设你有一组7个项目。如果你并行化了父循环，这些毫秒将会损失7次。如果你并行化两个循环，这些毫秒将会损失49次。集合越大，过热现象越严重。

- Arseni Mourzenko

---

不要假设 PFX 会为每个并行任务创建等同于线程数的线程数量，它比这更智能。 - Jon Skeet

当然不是。默认情况下，它会创建与核心数相同的线程。但问题在于，在每次迭代之后，它会花费时间尝试找到哪个线程必须执行下一个迭代。 - Arseni Mourzenko

我认为他并不是在说会有那么多线程，只是每次函数调用都排队一个任务比每个外部循环调用PFX引擎的开销要大得多。 - Gabe

谢谢MainMa。值得注意的是，与Parallel.ForEach调用的成本相比，foo可能需要很长时间。我确实赞赏只并行化一个循环的一般论点。 - Wesley Tansey

Answer 2

你能不能只使用一个并行循环和一个正常循环呢？因此，可以选择

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

或者选择

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

这样应该也能加速。因为本来每个循环都不需要一个线程，所以这种方法可能与嵌套的并行循环一样快或稍微慢一点。

- Jouke van der Maas

Answer 3

两个嵌套循环的本质是要对列表与其自身的笛卡尔积进行foo操作。您可以通过首先创建一个临时列表来并行化整个操作，然后使用Parallel.ForEach在该列表上进行迭代。

编辑：不必创建所有组合的列表，可以使用一个迭代器返回包含组合的2元组。Parallel.ForEach仍然会并行处理这些元组。

以下示例打印出当前迭代步骤，以显示结果无序返回，这在并行处理期间是可以预期的：

 const int SIZE = 10;
    static void Main(string[] args)
    {
        List<int> list = new List<int>(SIZE);
        for(int i=0;i<SIZE;i++)
        {
            list.Add(i);
        }


        Parallel.ForEach(GetCombinations(list),(t,state,l)=>
            Console.WriteLine("{0},{1},{2}",l,t.Item1,t.Item2));

    }

    static IEnumerable<Tuple<int,int>> GetCombinations(List<int> list)
    {
        for(int i=0;i<list.Count;i++)
            for(int j=0;j<list.Count;j++)
                yield return Tuple.Create(list[i],list[j]);
    }

- Panagiotis Kanavos

---

你可能不知道Enumerable.Range()这个函数，它非常方便！但是在代码中，你运行了3个循环（而不是2个），其中有2个根本不是并行的。这取决于Foo()函数的操作（在你的答案中是Console.WriteLine），但这可能比不添加任何并行性并正常循环两次要慢。 - Jouke van der Maas