[Haskell-beginners] Performance of parallel mergesort
tom.davie at gmail.com
Thu Dec 24 04:09:41 EST 2009
The mergesort example given here has a rather nasty problem – it creates
sparks for mergeing the two lists at the same time as it creates the lists,
so there's always at least one task blocking waiting for it's producers.
This variation on a theme goes roughly twice as fast for me with -N1, and
*does* get a speedup from -N<somethinghigher>:
mergesort  = 
mergesort [x] = [x]
mergesort [x,y] = if x < y then [x,y] else [y,x]
mergesort xs = (forceList sleft) `par`
(forceList sright) `pseq`
merge sleft sright
(left,right) = split (length xs `div` 2) xs
sleft = mergesort left
sright = mergesort right
Note the `pseq` not `par` before the merge. I also added one more
short-circuit case – we want to avoid spawning threads for tiny tasks like
sorting 1 element lists.
Here's my results on a dual core running OS X:
LappyBob:~ tatd2$ time ./test +RTS -N1
LappyBob:~ tatd2$ time ./test +RTS -N2
LappyBob:~ tatd2$ time ./test +RTS -N3
The last result is still off the wall, but it's a lot better.
On Thu, Dec 24, 2009 at 2:24 AM, Jon Harrop <jon at ffconsultancy.com> wrote:
> For some reason all traffic from this beginners list stopped reaching me
> the 13th of December.
> Thanks for the response, Antoine. I've tried to install more recent
> of GHC (6.10 and 6.12) but I cannot get either of them to work at all.
> GHC 6.8 generates code that segfaults and the GHC 6.10 from Debian testing
> cannot compile anything for me. So I thought I'd try GHC 6.12. That isn't
> any repo so I decided to build it from source. I uninstalled all other GHCs
> to give it a fresh start. The GHC page says "Stop, install the Haskell
> Platform" but the Haskell Platform says you must install GHC first, so I've
> got a nice circular dependency right from the start!
> So I tried installing GHC 6.12 from source but that requires GHC to be
> installed. So I installed GHC 6.8 (the one that segfaults) using apt again
> from Debian. That seems to have built a GHC 6.12 that I can run from the
> command line but it cannot compile that program because it doesn't have
> parallel stuff. So I thought I'd install the Haskell Platform.
> Unfortunately, the Haskell Platform configure script gives the nonsensical
> error that I must "upgrade" from GHC 6.12 down to GHC 6.10. I was getting
> pretty run down by this point so I just told it to sod off using
> the --enable-unsupported-ghc-version command line option. The Haskell
> Platform's configure script then completed but building it failed with:
> [21 of 21] Compiling Graphics.UI.GLUT ( Graphics/UI/GLUT.hs,
> dist/build/Graphics/UI/GLUT.p_o )
> Registering GLUT-22.214.171.124...
> Setup: GLUT-126.96.36.199: dependency
> "OpenGL-188.8.131.52-182b091280ce0de861295bc592bae77c" doesn't exist (use
> to override)
> Building the GLUT-184.108.40.206 package failed
> make: *** [build.stamp] Error 2
> I have glut and use it all the time from OCaml without a hitch so I've no
> what the problem is here.
> Oh well, I just discovered that installing GHC 6.12 has at least fixed GHC
> 6.10 so it can now compile and run that mergesort. Oh FFS, spoke too soon:
> $ time ./mergesort +RTS -N8
> Stack space overflow: current size 8388608 bytes.
> Use `+RTS -Ksize' to increase it.
> real 0m38.801s
> user 4m0.851s
> sys 0m1.308s
> Dr Jon Harrop, Flying Frog Consultancy Ltd.
> Beginners mailing list
> Beginners at haskell.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Beginners