December 2009 - Glasgow-haskell-users

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 22 Dec '09

22 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

How does forkIO and par interact?
by Marcus D. Gabriel 21 Dec '09

21 Dec '09

Hello, How does forkIO (forkOS) and par interact with one another? Here is why I ask. I have a GUI application that has something like this: th <- forkIO (guiCode + longRunningPureSerialCode) Later, a user interaction invokes killThread th and the guiCode plus the longRunningPureSerialCode suspends quite nicely. Now I have th <- forkIO (guiCode + longRunningPureParallelCode) Later a user interaction invokes killThread th again but I have observed under 6.10.4 that not all is suspended. From what I have observed, I believe that if longRunningPureParallelCode = ... 1stPart `par` 2ndPart ... the 2ndPart is suspended by killThread th along with the guiCode, and the 1stPart happily continues calcualting. (I believe this is correct but it could be the other way around.) For my little application, having everything suspend would have been nice, but that's my app. So, under ghc, how is forkIO (forkOS) and par supposed to operationally interact with one another? Cheers, - Marcus

3 3

openFd under -threaded gets interrupted
by Mitar 21 Dec '09

21 Dec '09

Hi! I have written about this to Haskell cafe and they advised me to write it here. I have a problem that I cannot open /dev/rfcomm0 device if I compile my program with -threaded option. Like: fd <- openFd "/dev/rfcomm0" ReadWrite Nothing OpenFileFlags { append = False, noctty = True, exclusive = False, nonBlock = True, trunc = False } If I compile my program with -threaded option I always get such error: interrupted (Interrupted system call) But without -threaded it works flawlessly. I am using Linux 2.6.30 amd64, GHC 6.10.4. It was the same with 6.8. And I have tested it also on 6.12.1. After some testing I have discovered that the problem is only with /dev/rfcomm0 as a device, that is with Bluetooth serial connection. The problem is that rfcomm Linux kernel code contains: if (signal_pending(current)) { err = -EINTR; break; } So if during open call some signal comes it returns EINTR. As it has to open a connection to a Bluetooth device opening a /dev/rfcomm0 file requires some time and during that time obviously there is some signal sent by GHC with -threaded option which is not sent without it. So please tell me what is the difference between open with and without -threaded option in GHC as I would like to make a simple C test case. I am not really sure if this is a feature or a bug in Linux Bluetooth kernel implementation. But in combination with threaded GHC it makes not working. Also is there any workaround possible in Haskell/GHC? For example making time while openFd is in progress without interrupts? I have found very similar bug reported here: https://bugzilla.redhat.com/show_bug.cgi?id=161314 but code from the patch does not seem to be included in official kernel source code (but it is also a long time ago so many things have probably changed). But the workaround mentioned there is working also here. If I open /dev/rfcomm0 with some other program (so that Bluetooth connection is made) before I run Haskell program then it works in both cases, with or without -threaded option. Of course this is not really useful workaround in my case, I would like to make a stand-alone Haskell program. So if it is similar to that bug then maybe it is a bug in Linux kernel. So please help me solve this problem. Mitar

2 1

Re: openFd under -threaded gets interrupted
by Donn Cave 18 Dec '09

18 Dec '09

Quoth Mitar <mmitar(a)gmail.com>, > Also is there any workaround possible in Haskell/GHC? For example > making time while openFd is in progress without interrupts? You might try something like this: import System.Posix.Signals ... setSignalMask fullSignalSet fd <- openFd ... setSignalMask emptySignalSet I'm not in a position to try it in exactly the same situation, but I see that when I run with all signals blocked as above, after a while I have a SIGALRM pending (with -threaded or not), so I reckon that might be the signal used by the runtime thread manager. If it works, I would recommend blocking only that signal during the openFd, so for example you'll be able to abort normally with SIGINT if the device is stuck. Donn

2 1