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&#39;s always at least one task blocking waiting for it&#39;s producers.<div>
<br></div><div>This variation on a theme goes roughly twice as fast for me with -N1, and *does* get a speedup from -N&lt;somethinghigher&gt;:</div><div><br></div><div><div>mergesort [] = []</div><div>mergesort [x] = [x]</div>
<div>mergesort [x,y] = if x &lt; y then [x,y] else [y,x]</div><div>mergesort xs = (forceList sleft) `par`</div><div>       (forceList sright) `pseq`</div><div>       merge sleft sright</div><div>       where</div>
<div>        (left,right) = split (length xs `div` 2) xs</div><div>        sleft = mergesort left</div><div>        sright = mergesort right</div><div><br></div><div>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.</div>
<div><br></div><div>Here&#39;s my results on a dual core running OS X:</div><div><br></div><div><div>LappyBob:~ tatd2$ time ./test +RTS -N1</div><div>-0.117109518058233</div><div><br></div><div>real<span class="Apple-tab-span" style="white-space:pre">        </span>0m4.608s</div>
<div>user<span class="Apple-tab-span" style="white-space:pre">        </span>0m4.400s</div><div>sys<span class="Apple-tab-span" style="white-space:pre">        </span>0m0.189s</div><div><div>LappyBob:~ tatd2$ time ./test +RTS -N2</div>
<div>-0.117109518058233</div><div><br></div><div>real<span class="Apple-tab-span" style="white-space:pre">        </span>0m3.648s</div><div>user<span class="Apple-tab-span" style="white-space:pre">        </span>0m6.360s</div><div>sys<span class="Apple-tab-span" style="white-space:pre">        </span>0m0.220s</div>
<div><div>LappyBob:~ tatd2$ time ./test +RTS -N3</div><div>-0.117109518058233</div><div><br></div><div>real<span class="Apple-tab-span" style="white-space:pre">        </span>0m50.679s</div><div>user<span class="Apple-tab-span" style="white-space:pre">        </span>1m24.235s</div>
<div>sys<span class="Apple-tab-span" style="white-space:pre">        </span>0m0.620s</div><div><br></div><div>The last result is still off the wall, but it&#39;s a lot better.</div><div><br></div><div>Bob</div></div></div></div>
</div><div><br><div class="gmail_quote">On Thu, Dec 24, 2009 at 2:24 AM, Jon Harrop <span dir="ltr">&lt;<a href="mailto:jon@ffconsultancy.com">jon@ffconsultancy.com</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<br>
For some reason all traffic from this beginners list stopped reaching me after<br>
the 13th of December.<br>
<br>
Thanks for the response, Antoine. I&#39;ve tried to install more recent versions<br>
of GHC (6.10 and 6.12) but I cannot get either of them to work at all.<br>
<br>
GHC 6.8 generates code that segfaults and the GHC 6.10 from Debian testing<br>
cannot compile anything for me. So I thought I&#39;d try GHC 6.12. That isn&#39;t in<br>
any repo so I decided to build it from source. I uninstalled all other GHCs<br>
to give it a fresh start. The GHC page says &quot;Stop, install the Haskell<br>
Platform&quot; but the Haskell Platform says you must install GHC first, so I&#39;ve<br>
got a nice circular dependency right from the start!<br>
<br>
So I tried installing GHC 6.12 from source but that requires GHC to be<br>
installed. So I installed GHC 6.8 (the one that segfaults) using apt again<br>
from Debian. That seems to have built a GHC 6.12 that I can run from the<br>
command line but it cannot compile that program because it doesn&#39;t have<br>
parallel stuff. So I thought I&#39;d install the Haskell Platform.<br>
<br>
Unfortunately, the Haskell Platform configure script gives the nonsensical<br>
error that I must &quot;upgrade&quot; from GHC 6.12 down to GHC 6.10. I was getting<br>
pretty run down by this point so I just told it to sod off using<br>
the --enable-unsupported-ghc-version command line option. The Haskell<br>
Platform&#39;s configure script then completed but building it failed with:<br>
<br>
[21 of 21] Compiling Graphics.UI.GLUT ( Graphics/UI/GLUT.hs,<br>
dist/build/Graphics/UI/GLUT.p_o )<br>
Registering GLUT-2.1.1.2...<br>
Setup: GLUT-2.1.1.2: dependency<br>
&quot;OpenGL-2.2.1.1-182b091280ce0de861295bc592bae77c&quot; doesn&#39;t exist (use --force<br>
to override)<br>
<br>
Error:<br>
Building the GLUT-2.1.1.2 package failed<br>
make: *** [build.stamp] Error 2<br>
<br>
I have glut and use it all the time from OCaml without a hitch so I&#39;ve no idea<br>
what the problem is here.<br>
<br>
Oh well, I just discovered that installing GHC 6.12 has at least fixed GHC<br>
6.10 so it can now compile and run that mergesort. Oh FFS, spoke too soon:<br>
<br>
$ time ./mergesort +RTS -N8<br>
Stack space overflow: current size 8388608 bytes.<br>
Use `+RTS -Ksize&#39; to increase it.<br>
<br>
real  0m38.801s<br>
user  4m0.851s<br>
sys   0m1.308s<br>
<font color="#888888"><br>
--<br>
Dr Jon Harrop, Flying Frog Consultancy Ltd.<br>
<a href="http://www.ffconsultancy.com/?e" target="_blank">http://www.ffconsultancy.com/?e</a><br>
_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org">Beginners@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/beginners" target="_blank">http://www.haskell.org/mailman/listinfo/beginners</a><br>
</font></blockquote></div><br></div>