Parallel Partition Algorithm in C#: How to Maximize Parallelism

Question

I've written a parallel algorithm in C# to partition an array into two lists, one that contains elements which satisfies a given predicate and the other list contains the elements that fails to satisfy the predicate. It is an order preserving algorithm.

I have written it as follows, but I want to know how to maximize the opportunity to profit from hardware concurrency.

    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);
    }

Answer 1

If your lists are very long you will not get much parallelism out of it (2x). Instead, I'd recommend using a Parallel.For and use a thread-local Tuple<List<int>, List<int>> as the parallel loop state. The Parallel.For API allows you to do this easily. You can merge the individual sublists at the end.

This version is embarrassingly parallel and causes almost no coherency traffic on the CPU-bus because there is no synchronization.

Edit: I want to emphasize that you cannot just use two List's shared by all threads because that is going to cause synchronization overhead like crazy. You need to use thread-local lists. Not even a ConcurrentQueue is suitable for this scenario because it uses Interlocked operations which cause CPU coherency traffic which is limited.