A strategy for maintaining sequence in parallel processing in .Net 4.0

Most of us are aware how the offerings of parallel processing introduced in .Net 4.0 (actually with .Net 3.5 as well, but the integration was not as seamless) can bring significant performance benefits while processing CPU intensive tasks. In terms of practical usage, recently for one of my projects I was looking to take advantage of parallel processing while trying to split the image of a 8.5 x 11 inch page into multiple slices, and then process individual slices using GDI+ (some very CPU intensive processing as you can guess).

But there was a slight catch – while it was perfectly OK to process each slice in any CPU in any order, but before I returned the individual image back, I had to put the slices back in order so that the page image could be reconstituted from the individual slices that would be put back in the original sequence. Kind of goes like this:

Unfortunately, that’s when the issue started. When I looked up the info online, there were many wild guesses and some bits and pieces of info here and there using PLINQ’s AsOrdered() approach, but nothing concrete that showed a clean implementation. So I ended up writing my own class implementation to take care of this.

So, starting from scratch, here is the original non-parallel implementation:

//Main CPU intensive function that runs in sequential loop

public List<RealObject> PerformSequential()

{

    List<RealObject> myObjectArray = new List<RealObject>();

    for(int i=0; i< 100; i++)

    {

        myObjectArray.Add(GetMyRealObject());

    }

    return myObjectArray;

}

First step was to make the for-loop parallel:

//Main CPU intensive function that runs in parallel loop

public List<RealObject> PerformParallel()

{

    List<RealObject> myObjectArray = new List<RealObject>();

    Parallel.For(0, 100, i =>

    {

        myObjectArray.Add(GetMyRealObject());

    });

    return myObjectArray;

}

So obviously due to the parallel nature of the way work is performed, the list myObjectArray will have randomly positioned items e.g. i=2, followed by i=0, then 3 and then 1 etc. The intention is to be able to return the myObjectArray list after re-sorting the individual objects within it so that they correspond to i=0, 1, 2, 3 etc.

For doing this we would add a new class, which will hold the individual RealObject objects, and another variable that will hold the location pointer. This object will implement the IComparable interface and we will overload the CompareTo implementation so that later when we sort the objects, we can regain the original sequence of objects that they were intended to be received as:

//The intermediate object that will hold the true object and implement sorting

public class SortableRealObject : IComparable

{

    public int locationPointer;

    public RealObject realObject;

    public int CompareTo(object obj)

    {

        SortableRealObject thisObject = (SortableRealObject)obj;

        return this.locationPointer.CompareTo(thisObject.locationPointer);

    }

}

Then all we will need to do is populate this locationPointer within the loop, do a sort on the array, and finally repopulate the true object to be returned. So the modified code will look like this:

//Main CPU intensive function that runs in parallel loop

public List<RealObject> PerformParallel()

{

    List<RealObject> myObjectArray = new List<RealObject>();

    List<SortableRealObject> mySortableObjectArray = new List<SortableRealObject>();

    Parallel.For(0, 100, i =>

    {

        mySortableObjectArray.Add(new SortableRealObject(){locationPointer = i, realObject = GetMyRealObject()});

    });

    mySortableObjectArray.Sort();

    foreach(SortableRealObject mySortableObject in mySortableObjectArray)

    {

        myObjectArray.Add(mySortableObject. realObject;

    }

    return myObjectArray;

}

That’s it, we now have GetMyRealObject() that was performed parallel on multiple CPU cores, while the returned myObjectArray is perfectly sorted in the way they would have been if the for loop was performed sequentially in a regular for loop!