This discussion definitely does not belong on the Haskell-Beginners list. Besides not being a topic for beginners, being there is keeping it under the radar of many or most of the people who work on these things in Haskell.
I am moving the discussion to the GHC users list, as suggested by Antoine. For those joining us in progress, the first part of the thread starts here: http://www.haskell.org/pipermail/beginners/2009-December/003045.html On Mon, Dec 28, 2009 at 5:19 AM, Jon Harrop wrote: > On Sunday 27 December 2009 20:56:51 Stephen Blackheath wrote: >> Jon Harrop wrote: >> > This is something that concerns me. Lots of discussions of parallelism, >> > including the Haskell literature I have read, neglect this critical >> > problem >> > of making sure that more time is spent doing useful work than spawning >> > tasks >> > (sparks). How is this solved in Haskell? Do you just put magic numbers in >> > that work on the machine you're currently using? >> >> It is simply not true that Haskell literature neglects the question of >> spark granularity - this is very basic and is always covered. Read >> "Real World Haskell" (available free online). There's no 'magic >> number'. You must explicitly write your code to give the right granule >> size. > > There is no "right granule" size. That's the whole point: the optimum is a > function of the machine. If you hardcode the granularity then your code isn't > future proof and isn't portable. > > From chapter 24 of Real World Haskell on sorting: > > "At this fine granularity, the cost of using par outweighs any possible > usefulness. To reduce this effect, we switch to our non-parallel sort after > passing some threshold." > > From the Sorting.hs file, parSort2 accepts a threshold "d": > > parSort2 :: (Ord a) => Int -> [a] -> [a] > parSort2 d list@(x:xs) > | d <= 0 = sort list > | otherwise = force greater `par` (force lesser `pseq` > (lesser ++ x:greater)) > where lesser = parSort2 d' [y | y <- xs, y < x] > greater = parSort2 d' [y | y <- xs, y >= x] > d' = d - 1 > parSort2 _ _ = [] > > From the SortMain.hs file, it is always invoked with the magic number "2": > > testFunction = parSort2 2 > > Moreover, their approach of subdividing a fixed number of times is suboptimal > because it inhibits load balancing. > > Later, about parallelized IO, they give the code: > > chunkedReadWith :: (NFData a) => > ([LB.ByteString] -> a) -> FilePath -> IO a > chunkedReadWith func path = > withChunks (lineChunks (numCapabilities * 4)) func path > > where "4" is one magic number that gets multiplied by the magic number the > user supplied via the +RTS -N<n> command-line option. > > They make no attempt to adapt the granularity to the machine at all and rely > entirely upon magic numbers. Consequently, their parallel sort that got a 25% > speedup on two cores achieves a 30% slowdown on my 8 core. > >> I don't know the exact cost of sparking, but in my experience it >> is quite small - so - as long as your granule is doing *some* real work, >> it should speed up. > > Can you quantify it, e.g. How many FLOPS? > >> Jon Harrop wrote: >> > The parallelism is obviously not obtaining any real speedup so something >> > is wrong. But can anyone fix it? >> >> I've spent a bit of time measuring parallel speedup on real commercial >> projects, and this is what I've found: >> >> 1. ghc-6.12 performs significantly better than ghc-6.10, and has now >> been released, therefore don't use ghc-6.10. > > Ok. > >> 2. The defaults generally work better than giving huge heap sizes. Your >> -K100000000 - maximum heap size per thread - will either do nothing or >> cause an artificial slowdown (I have observed this with the minimum heap >> size option). Don't use it, unless experimentation proves it makes >> things better. > > On the contrary, the Haskell program dies without it: > > $ time ./mergesort +RTS -N8 > Stack space overflow: current size 8388608 bytes. > Use `+RTS -Ksize' to increase it. > [1]+ Done kwrite mergesort.hs > > real 0m33.320s > user 3m29.397s > sys 0m0.592s > > I had to add that -K command line option just to get the program to run to > completion. > >> 3. +RTS -s is well worth using. It breaks the time down into MUT >> (mutator) and GC (garbage collector). > > Its says 78.5% GC time (with GHC 6.10). > >> 4. MUT parallelization is excellent, but the parallel GC is not so good. >> If your code is GC-heavy it can spend around half of its time garbage >> collecting, which doesn't parallelize so well, and this eats into the >> speedup. > > Ok. > >> 5. There seems to be a scalability problem with the parallel gc for >> larger numbers of cores (namely 8). I am guessing somewhat, but my >> experiments tend to confirm the issue raised in Simon Marlow's (the >> implementor of GHC parallelization) recent paper that it's to do with >> "stopping the world" for gc. > > Do you mean this bug: > > http://hackage.haskell.org/trac/ghc/ticket/3553 > >> If GHC's lack of perfection at this point in time makes Haskell "look >> bad" I don't mind. I am not selling anything, so the reader at least >> knows they're getting the truth. I see this as one of the great >> advantages of open source. > > I'm sure we'd all rather see speedups. :-) > >> Progress on GHC has been very rapid in the last couple of years, and so >> I know we'll continue to see the speed of GHC's parallelism improving in >> leaps and bounds. It's actually still quite a new area, considering the >> difficulty of some of the technical issues and how recent it is that >> multicores are widely available on consumer hardware. > > My original intent was to test a claim someone made: that mergesort in Haskell > is competitively performant and trivially parallelized. > >> I know you OCaml/F# guys are making great progress too. > > F# is production ready but OCaml is dead in the water when it comes to > multicore. I'm working on an OCaml replacement called HLVM but it is early > days yet. > > -- > Dr Jon Harrop, Flying Frog Consultancy Ltd. > http://www.ffconsultancy.com/?e > _______________________________________________ > Beginners mailing list > beginn...@haskell.org > http://www.haskell.org/mailman/listinfo/beginners > _______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users