Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Parallel.ForEach while retaining order

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 than 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?

Thanks

like image 899
Matt Avatar asked Jun 20 '12 07:06

Matt


Video Answer


1 Answers

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]

enter image description here

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();
like image 141
Dr. Andrew Burnett-Thompson Avatar answered Sep 28 '22 01:09

Dr. Andrew Burnett-Thompson