Parallel.ForEach while retaining order of the results

Question

I have a List<byte[]> and I like to deserialize each byte[] into Foo. The List is ordered and I like to write a parallel loop in which the resulting List<Foo> contains all Foo in the same order as the original byte[]. The list is significantly large to make parallel operation worthwhile. Is there a built-in way to accomplish this?

If not, any ideas how to achieve a speedup over running this all synchronously?

Answer 1

From the info you've given, I understand you want to have an output array of Foo with size equal to the input array of bytes? Is this correct?

If so, yes the operation is simple. Don't bother with locking or synchronized constructs, these will erode all the speed up that parallelization gives you.

Instead, if you obey this simple rule any algorithm can be parallelized without locking or synchronization:

For each input element X[i] processed, you may read from any input element X[j], but only write to output element Y[i]

Look up Scatter/Gather, this type of operation is called a gather as only one output element is written to.

If you can use the above principle then you want to create your output array Foo[] up front, and use Parallel.For not ForEach on the input array.

E.g.

        List<byte[]> inputArray = new List<byte[]>();
        int[] outputArray = new int[inputArray.Count];

        var waitHandle = new ManualResetEvent(false);
        int counter = 0;

        Parallel.For(0, inputArray.Count, index =>
            {
                // Pass index to for loop, do long running operation 
                // on input items
                // writing to only a single output item
                outputArray[index] = DoOperation(inputArray[index]);

                if(Interlocked.Increment(ref counter) == inputArray.Count -1)
                {
                    waitHandle.Set();
                }
            });

        waitHandler.WaitOne();

        // Optional conversion back to list if you wanted this
        var outputList = outputArray.ToList();