[Haskell-beginners] Performance of parallel mergesort

[Tom Davie]

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
               where
                 (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
-0.117109518058233

real 0m4.608s
user 0m4.400s
sys 0m0.189s
LappyBob:~ tatd2$ time ./test +RTS -N2
-0.117109518058233

real 0m3.648s
user 0m6.360s
sys 0m0.220s
LappyBob:~ tatd2$ time ./test +RTS -N3
-0.117109518058233

real 0m50.679s
user 1m24.235s
sys 0m0.620s

The last result is still off the wall, but it's a lot better.

Bob

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
> after
> the 13th of December.
>
> Thanks for the response, Antoine. I've tried to install more recent
> versions
> 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
> in
> 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-2.1.1.2...
> Setup: GLUT-2.1.1.2: dependency
> "OpenGL-2.2.1.1-182b091280ce0de861295bc592bae77c" doesn't exist (use
> --force
> to override)
>
> Error:
> Building the GLUT-2.1.1.2 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
> idea
> 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.
> http://www.ffconsultancy.com/?e
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20091224/29363886/attachment.html