A little while ago, I wrote about my silly project to test Parallel LINQ – a Mandelbrot generator. In the last week, two things have happened to make this more of a reality. Firstly, the December CTP of Parallel FX has been released. Secondly, my old laptop died, “forcing” me to get a new laptop, which just happens to have a dual core processor.
So, it should just be a case of running it, right? Well, not quite. First let’s have a look at the query expression again, in its serial form:
var query = from row in Enumerable.Range(0, ImageHeight)
from col in Enumerable.Range(0, ImageWidth)
select ComputeMandelbrotIndex(row, col);
And here’s what should be generated.
That’s the result of running without any parallelism, in other words. Now, I realised from the start that we would need ordering, but my first experiment was just to call AsParallel() to see what would happen:
var query = from row in Enumerable.Range(0, ImageHeight).AsParallel()
from col in Enumerable.Range(0, ImageWidth)
select ComputeMandelbrotIndex(row, col);
As expected, that didn’t produce quite the result we wanted:
Well, that’s okay. I wanted to prove that ordering was necessary, and indeed that’s fairly obvious from the result. There are horizontal blocks, returned out of order. Easily fixable, right? After all, I posted what I thought would be the solution with the original post. We just need to give the appropriate option as a method parameter:
var query = from row in Enumerable.Range(0, ImageHeight).AsParallel(ParallelQueryOptions.PreserveOrdering)
from col in Enumerable.Range(0, ImageWidth)
select ComputeMandelbrotIndex(row, col);
Not so fast. It certainly changed things, but not quite as hoped:
I haven’t yet analysed quite why we now have the rows in order but the columns out of order. However, I haven’t quite managed to fix it with the code in its original form. I have managed to fix it by reducing it from two (implicit) loops to one:
var query =
from row
in Enumerable.Range(0, ImageHeight).AsParallel(ParallelQueryOptions.PreserveOrdering)
select ComputeMandelbrotRow(row);
byte[] data = new byte[ImageHeight * ImageWidth];
int rowStart = 0;
foreach (byte[] row in query)
{
Array.Copy(row, 0, data, rowStart, ImageWidth);
rowStart += ImageWidth;
}
Instead of getting all the results in one go (with a call to ToArray()) we now have to reassemble all the data into a block. Still, it achieves the desired result. I should point out that PFX has better ways of doing this, Parallel.For being an obvious starting point from the little I know of it. At some point I’ll get round to reading about them, but at the moment life’s too short. I should also say that I don’t expect that any of the pictures indicate a bug in Parallel LINQ, merely my understanding of it.
Update: Explanation and a workaround
Having asked about this on the Connect forum for PFX, Igor Ostrovsky has explained that this is by design – currently only outer ordering is preserved when requested. The issue is still open, however – it’s possible that it will change before release.
In the meantime, Nicholas Palladinos has come up with an alternative solution which I rather like. I’ve refactored it a bit, but the basic idea is to turn the two sequences into one before parallelisation:
var points =
from row
in Enumerable.Range(0, ImageHeight)
from col
in Enumerable.Range(0, ImageWidth)
select new { row, col };
var query = from point in points.AsParallel(ParallelQueryOptions.PreserveOrdering)
select ComputeMandelbrotIndex(point.row, point.col);
That works really well – in fact, more than twice as fast as the serial version, on my 2-core box!
Jon Skeet's coding blog 