[Haskell-beginners] Performance of parallel mergesort

Jon Harrop jon at ffconsultancy.com
Sat Dec 26 14:56:11 EST 2009

On Saturday 26 December 2009 18:00:49 Tommy M. McGuire wrote:
> Antoine Latter wrote:
> >> Here's a paste-bin link for the code in question:
> >
> > http://hpaste.org/fastcgi/hpaste.fcgi/view?id=14871#a14871
> I am not familiar with Control.Parallel at all, so someone please correct
> me if I'm wrong....
> ...but that parallel mergesort looks very wrong to me.
> In the first place, the split is using the length of the list, which is
> going to force the spine of the list, leaving a bazillion thunks unless the
> runtime will evaluate the numerical value at each element.
> More importantly, it seems to be running the forcelist in parallel with the
> merge; forcelist is not going to do anything useful after the first pass
> over each element, and the merge has a data dependency on the split
> sub-lists, which is going to limit parallelism quite a bit.
> Am I wrong here?

The parallelism is obviously not obtaining any real speedup so something is 
wrong. But can anyone fix it?

Dr Jon Harrop, Flying Frog Consultancy Ltd.

More information about the Beginners mailing list