- Glasgow-haskell-users

Re: [Haskell-beginners] Performance of parallel mergesort
by Yitzchak Gale 30 Dec '09

30 Dec '09

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 > Beginners(a)haskell.org > http://www.haskell.org/mailman/listinfo/beginners >

4 4

hsc2hs and base
by Bryan O'Sullivan 29 Dec '09

29 Dec '09

Hi, Simon — Is it licit to have source files in base depend on preprocessing by hsc2hs? My suspicion is "no", but I want to be sure. Thanks, Bryan.

3 3

Qualified names in import lists
by Niklas Broberg 28 Dec '09

28 Dec '09

Hi all, I have a bug report [1] for haskell-src-exts pertaining to the use of qualified names in import specifications, e.g. module Main where import Foo (Bar.bar) GHC apparently accepts this code, but I can find no mention of such a feature in the GHC docs. Personally I don't see why this should be allowed at all, as it breaks the abstraction layer w.r.t. re-exporting names from other, possibly internal, modules. If there's some reasonable use for it, it should at the very least be tied to a documented and registered extension. I've submitted a ticket for GHC [2] to either remove this feature, or properly document it. I'd be curious to hear what the reasoning behind it is, if any. Cheers, /Niklas ps. Why is there no "GHC accepts invalid program" option for "Type of failure"? Too few cases? I set this ticket to Other. [1] http://trac.haskell.org/haskell-src-exts/ticket/57 [2] http://hackage.haskell.org/trac/ghc/ticket/3792

2 2

Poor array behaviour
by Herk, Robert van 23 Dec '09

23 Dec '09

Hi all, I stumbled upon something odd with respect to arrays. I know about GHC not doing card marking and traversing whole arrays one each GC for each array with alterations, but still I don't understand the behaviour. The situation is like this. I am building a compiler. This compiler manipulates a large graph (for optimizations, etc.). This graph is in memory. As the graph is vast, we did a lot of effort to optimize access to it. The nodes in the graph are IORefs to some data structure, and this data structure contains its edges. Each node stores its edges in buckets. This is because edges have different types (some are control flow links, others are other types of dependencies). Most of the graph manipulations only traverse over one type of edge, so we figured it would be faster to store the edges in buckets to support such queries. Inside the buckets, there are Data.Maps containing the actual edges for that bucket. The keys in this map are the target nodes of that edges, which are IORefsOrds, which are pairs of a unique integers and a IORef, such that they can be ordered and used as keys in a Map. The values are lists of edges to that target. The weird thing is in the buckets. Per node, all buckets are stored in an array. We gave each edge type an integer key. And we use that key as array index to determine the bucket. I've tried implementing this array in two ways: 1) Each node contains a immutable array with IORefs. The IORefs contain the actual Data.Maps for the buckets. So, for instance, initializing a node looks something like import Data.Array uBucket = 8 //There are 8 buckets because there are 8 types of edges. emptyEdges = do buckets <- sequence ( take uBucket $ repeat (newIORef Map.empty) ) let myArray = listArray (0, 7) buckets return myArray So in this solution we have an extra layer of indirection, namely the IORefs, but the array is immutable. Because when the edges change for a particular node, we can write directly into the IORef and leave the array untouched. 2) Each node contains a mutable array that contains the Data.Maps directly. So, for instance, initializing a node looks something like: import Data.Array.IO emptyEdges = do myArray <- newArray (0, 7) Map.empty return $! myArray Of course, one expect 2 to be quickest. However, it turns out that for 2, the application is spending much more time in GC, and __even without GC__ the application is still slower! I find both things rather weird: I know that for huge arrays I am expected to suffer from the missing card-marking "bug", but my array sizes are only 8. Yet the difference I get in GC time are huge: Solution 1 ------------- 13,476,008,560 bytes allocated in the heap 1,714,767,712 bytes copied during GC 151,518,528 bytes maximum residency (23 sample(s)) 1,743,176 bytes maximum slop 325 MB total memory in use (2 MB lost due to fragmentation) Generation 0: 25689 collections, 0 parallel, 2.43s, 2.53s elapsed Generation 1: 23 collections, 0 parallel, 1.89s, 2.05s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 20.58s ( 20.80s elapsed) GC time 4.32s ( 4.58s elapsed) RP time 0.00s ( 0.00s elapsed) PROF time 0.00s ( 0.00s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 24.90s ( 25.38s elapsed) %GC time 17.4% (18.0% elapsed) Alloc rate 654,751,131 bytes per MUT second Productivity 82.6% of total user, 81.1% of total elapsed Solution 2 ------------ 15,901,133,296 bytes allocated in the heap 9,083,063,848 bytes copied during GC 117,501,208 bytes maximum residency (23 sample(s)) 1,902,568 bytes maximum slop 265 MB total memory in use (2 MB lost due to fragmentation) Generation 0: 30315 collections, 0 parallel, 44.73s, 44.89s elapsed Generation 1: 23 collections, 0 parallel, 1.78s, 1.91s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 25.93s ( 26.31s elapsed) GC time 46.51s ( 46.80s elapsed) RP time 0.00s ( 0.00s elapsed) PROF time 0.00s ( 0.00s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 72.43s ( 73.11s elapsed) %GC time 64.2% (64.0% elapsed) Alloc rate 613,325,569 bytes per MUT second Productivity 35.8% of total user, 35.5% of total elapsed Is the behaviour I am seeing to be expected? And if so, wouldn't it make more sense to implement Data.Array.IO internally such that it contains an immutable array of IORefs? I also saw that in the next GHC, card marking will be done per 128 array items. Yet this behaviour seems to point out that at least for my application problems can already occur with array size 8. And is it expected that solution 1), that has an extra layer of indirection, still outperforms solution 2) even with GC times substracted? Regards, Robert The information contained in this message may be confidential and legally protected under applicable law. The message is intended solely for the addressee(s). If you are not the intended recipient, you are hereby notified that any use, forwarding, dissemination, or reproduction of this message is strictly prohibited and may be unlawful. If you are not the intended recipient, please contact the sender by return e-mail and destroy all copies of the original message.

2 1

Weird warnings when using ViewPatterns
by Bas van Dijk 23 Dec '09

23 Dec '09

Hello, In my usb-safe[1] library I make extensive use of the ViewPatterns[2] language extension. However I get strange warnings when using them. See for example the following function: resetDevice ∷ (pr `ParentOf` cr, MonadIO cr) ⇒ RegionalDeviceHandle pr → cr () resetDevice (internalHandle → DeviceHandle { internalDevHndl , configAlreadySetMVar }) = ... where: type RegionalDeviceHandle r = RegionalHandle USB.Device r internalHandle ∷ RegionalHandle resource r → Handle resource and: 'Handle' is an associated data type with the following definition: data Handle USB.Device = DeviceHandle { internalDevHndl ∷ USB.DeviceHandle , configAlreadySetMVar ∷ MVar Bool } Note that I also use the NamedFieldPuns[3] language extension. When compiling the module I get lots of warnings like this: System/USB/Safe.hs:372:0: Warning: Pattern match(es) are overlapped In the definition of `resetDevice': resetDevice ((internalHandle -> (DeviceHandle {internalDevHndl, configAlreadySetMVar}))) = ... System/USB/Safe.hs:372:0: Warning: Pattern match(es) are non-exhaustive In the definition of `resetDevice': Patterns not matched: I don't understand which patterns are overlapped or which patterns are not matched. Is this a GHC bug? Note that I'm using ghc-6.10.4 so it's possible that it's fixed in 6.12.1. regards, Bas [1] usb-safe: http://hackage.haskell.org/package/usb-safe-0.4 or darcs get http://code.haskell.org/~basvandijk/code/usb-safe [2] http://www.haskell.org/ghc/docs/latest/html/users_guide/syntax-extns.html#v… [3] http://www.haskell.org/ghc/docs/latest/html/users_guide/syntax-extns.html#r…

2 3

x64 linux, x86 program and libgmp shared library
by Bulat Ziganshin 22 Dec '09

22 Dec '09

Hello glasgow-haskell-users, i compile my program for linux using ghc 6.6.1 (32-bit) user of my program asks: "any plans of making a static build for linux? that one does not work under x86-64 due to dependencies, missing libgmp which it seems is not available under 64bit. i could be wrong tho." how this may be resolved? should libgmp be available in x64 linux, or i should change compile options? -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

3 4

Re: cabal-install-0.8 final testing
by Duncan Coutts 22 Dec '09

22 Dec '09

On Fri, 2009-12-18 at 19:44 -0800, Dave Bayer wrote: > Hi Duncan, > > Installation was easy (I typed "cabal-install HTTP zlib > cabal-install" ;-). Thanks for testing it. I've uploaded it to hackage. > Overall, seems to work fine. I couldn't build darcs, but I couldn't do > that by hand either; I used their binary installer. I don't think they > build yet under GHC 6.12.1. > > One oddity, I tried to use cabal install to install mmap, and it > failed because the HUnit package was missing. I then installed HUnit > without incident, went back and installed mmap without incident. No > idea why this didn't work in one pass, but I have "sandbox" systems if > you'd like me to see if I can reliably reproduce this. Mm. This is a worse bug than I thought. It's not trivial to fix. I'll have to think about it. The problem is mmap uses: Executable mmaptest Main-is: tests/mmaptest.hs if flag(mmaptest) Buildable: True else Buildable: False Build-depends: base<5, bytestring, HUnit, directory Now the question is what does this mean exactly. The previous version of Cabal said essentially "well the executable needs HUnit thus the package needs HUnit". This despite the fact that we're not going to actually built this test executable! The current Cabal code takes a slightly different approach. It says at the end "oh this exe isn't buildable, so its deps do not contribute to the deps of the package". The problem is what it was doing before that. It sees the dependency on HUnit and checks that it can be satisfied. It's only at the end that it ends up discarding it. So if it was not actually available then it fails earlier. The reason it's then inconsistent between configuring a package and what the cabal install planner is doing is that the planner assumes all the packages on hackage are available (sort of) while when we get to actually configuring a package to install it, only the other installed packages are available. So that's why the same solver gives us different answers, because we're making different assumptions about the available packages. So the issue is we need to treat "Buildable: False" specially in the solver because if we end up picking a configuration with "Buildable: False" for a component then have to have not already required the dependencies for that component. Essentially we want to reinterpret it as something like: if flag(test) Buildable: True Build-depends: base<5, bytestring, HUnit, directory else Buildable: False So that the dependencies themselves are conditional on the component being buildable. Then the solver would do the right thing. In general I guess the transformation would look like: if A1 Buildable: False if A2 Buildable: False ... if B1 Build-depends: blah if B2 Build-depends: blah where A1,A2,... and B1,B2,... are arbitrary conditions (including none) then this becomes: if A1 Buildable: False if A2 Buildable: False ... if B1 && ! (A1 || A2 || ...) Build-depends: blah if B2 && ! (A1 || A2 || ...) Build-depends: blah ... I don't especially like this though. It makes the meaning of buildable rather magic. In the short term I may have to revert the change in behaviour so that these dependencies become unconditional again, even though they're not used. Sigh. Duncan

3 4

Static linking and linker search paths
by Duncan Coutts 22 Dec '09

22 Dec '09

All, Conor's problems on OSX with libiconv reminds me of something I've been thinking about for a little while. So the problem is that the semantics of static linking does not at all match what we really want. We can easily accidentally "interpose" a wrong library in place of the one we wanted. In the iconv case people have hit recently we've got this situation: libHSbase-4.2.0.0.a contains references to _iconv_open, _iconv, _iconv_close ${system}/libiconv.a ${macports}/libiconv.a When the code for libHSbase was built, it was against the header files for the standard system version of iconv on OSX. Thus it is intended that we link against the system version of iconv. No suppose by default that the system is set up such that only the system iconv is found by default. So I am assuming there is no LD_LIBRARY_PATH or similar set. Then when we link something then we correctly resolve the references in base to the system iconv lib. When we call gcc to link we're doing something like: -L${ghclibdir} -lHSbase-4.2.0.0.a -liconv Now suppose we build some FFI package (libHSfoo-1.0.a) that provides a binding to a C lib installed via macports (libfoo.a). When we link a program that depends indirectly on this FFI package then the gcc linker line is like: -L${ghclibdir} -L/opt/local/lib -lHSfoo-1.0.a -lfoo -lHSbase-4.2.0.0.a -liconv and now it all breaks. We're asking the linker to look in /opt/local/lib first for *all the remaining libraries* and that includes iconv, so we pick up the wrong iconv. Our intention was just to look for -lfoo using /opt/local/lib, but we cannot express that to the linker. The problem is that our notion of library dependencies is hierarchical but for the system linker it is linear. We know that package foo-1.0 needs the C library libfoo.a and that it should be found by looking in /opt/local/lib. But we end up asking the linker to look there first for all other libs too, including for the -liconv needed by the base package. The registration for the base package never mentioned /opt/local/lib of course. What we'd really like to say is something like: link HSfoo-1.0.a push search path /opt/local/lib link foo pop search path If we think we know enough about the behaviour of the system linker and its search path then we could do just: -L${ghclibdir} -lHSfoo-1.0.a /opt/local/lib/libfoo.a -lHSbase-4.2.0.0.a -liconv that is, specify the .a file exactly by fully resolved path and not add anything to the linker search path. (Actually we'd do it for the libHS*.a ones too since we know precisely where they live) The possible danger is that how we search for the library and how the system linker searches for it might not match exactly and we could end up sowing confusion. Worth thinking about anyway. Note that some of this is different for shared libs. Duncan

1 0

Haskell @ USENIX HotPar?
by Don Stewart 21 Dec '09

21 Dec '09

Hey Haskellers, Looks like a great opportunity to talk about parallel Haskell to other communities: Second USENIX Workshop on Hot Topics in Parallelism http://gpgpu.org/2009/12/20/cfp-hotpar-2010 Following the tremendous success of HotPar ‘09, the Second USENIX Workshop on Hot Topics in Parallelism (HotPar ‘10) will once again bring together researchers and practitioners doing innovative work in the area of parallel computing. Anyone planning on submitting a position paper? It would be a real shame not to show our faces. -- Don

1 0

parList implementation question
by Marcus D. Gabriel 21 Dec '09

21 Dec '09

Hello, In Control.Parallel.Strategies, parList is defined as parList strat [] = () parList strat (x:xs) = strat x `par` (parList strat xs) with parMap strat f xs = map f xs `using` parList strat. I have recently found that if I define forceParMap strat f xs = map f xs `using` forceParList strat where forceParList strat = foldl (\done -> (done>||) . strat) () then to date, forceParList via forceParMap gives faster results than parList via parMap. For example, in one experiment, parMap with parList run at 0.81 the time of the serial solution whereas forceParMap with forceParList run at 0.58 the time of the serial solution. This is to say, forceParList completed in 0.72 the time of parList. So, 1. Why is forceParList faster than parList? 2. Is this generic to the ghc runtime model or a particularity of the ghc implementation? Thanks in advance for the clarification, - Marcus

3 6