C#中的并行分区算法：如何最大化并行性

Question

我用C#编写了一个并行算法，将一个数组分成两个列表，一个包含满足给定谓词的元素，另一个列表包含未满足谓词的元素。这是一个保序算法。

我已经按照以下方式编写了它，但我想知道如何最大化硬件并发性能的机会。

    static void TestPLinqPartition(int cnt = 1000000)
    {
        Console.WriteLine("PLINQ Partition");
        var a = RandomSequenceOfValuesLessThan100(cnt).ToArray();
        var sw = new Stopwatch();
        sw.Start();
        var ap = a.AsParallel();
        List<int> partA = null;
        List<int> partB = null;
        Action actionA = () => { partA = (from x in ap where x < 25 select x).ToList(); };
        Action actionB = () => { partB = (from x in ap where !(x < 25) select x).ToList(); };
        Parallel.Invoke(actionA, actionB);
        sw.Stop();

        Console.WriteLine("Partion sizes = {0} and {1}", partA.Count, partB.Count);
        Console.WriteLine("Time elapsed = {0} msec", sw.ElapsedMilliseconds);
    }

- cdiggins

---

你最好在这里询问：http://codereview.stackexchange.com/ - asawyer

我希望Beta在一场烈火车祸中死亡。 - cdiggins

把它转化成更像是一个问题，这样它就不像是一个代码审查了。 - cdiggins

你好，你的算法基本上是复制数据并计算谓词。并行计算只有在足够重时才有意义，以弥补将数据拆分进行并行处理后重新合并时发生的同步开销。问题是，在实际程序中，谓词是否比<25更复杂且耗时？否则，最有效的方法是扫描并枚举初始数组中的元素。您真的需要最终两个列表还是可枚举的就足够了？ - George Mamaladze

Answer 1

如果你的列表非常长，你将无法从中得到太多并行性（2倍）。相反，我建议使用Parallel.For，并使用线程本地元组, List>>作为并行循环状态。 Parallel.For API允许您轻松完成此操作。你可以在最后合并各个子列表。

这个版本是典型的 embarrassingly parallel，因为没有同步，所以几乎没有CPU总线上的一致性流量。

编辑：我想强调的是，你不能只使用两个共享给所有线程的List，因为那会导致疯狂的同步开销。你需要使用线程本地列表。 即使是ConcurrentQueue在这种情况下也不适用，因为它使用Interlocked操作，这会导致受限的CPU一致性流量。

- usr

---

嵌入在并行LINQ查询中的x.AsParallel().Where()不是被部分并行化了吗？ - cdiggins

它是完全并行的，但您需要收集两个列表。一个用于匹配，另一个用于不匹配的项目。 - usr

好的答案，但我最终使用了另一个解决方案。 - cdiggins

Answer 2

我会将数据分成小段（例如使用 Partitioner 类），并为每个分区分配一个与其位置相关的索引。对于每个编号的分区，我会创建一个Task来将该分区分成两组：一个符合谓词条件，另一个不符合，并且将这两个组以及它们的来源分区的索引作为任务的返回值返回。然后，等待所有任务完成，再使用 .Concat()（以防止浪费时间在实际合并数据上）按照它们的索引连接匹配的组和不匹配的组。通过这种方式，您应该能够同时实现任意程度的并行性，同时保持相对项目顺序。

- Allon Guralnek

---

我选择了这个答案，因为这是我解决问题的方法。 - cdiggins