June 2007 - Glasgow-haskell-users

unneeded laziness case
by Serge D. Mechveliani 11 Jun '07

11 Jun '07

People, A couple of times I suffered of unneeded strictness in Haskell. And now unneeded laziness bites. Consider the following program: ------------------------------------------------------- main = let mK = <formed in a certain complex way> :: Map.Map Partition Integer row = [0, 1, 0 ... 0] (mK', p) = decompose mK row infoK' = sum $ map sum $ mapmap (\ n -> rem n 2) $ Map.elems mK' in putStr (shows p -- seq infoK' "\n") ------------------------------------------------------- In ghc-6.6, it needs at least 100 Mb of heap to perform. If I set seq infoK' between `shows' and `p', then it suffices 14 Mb. If I set there seq mK', then again it needs 100 Mb. 7 times as large. mK is a triangular n by n matrix, n is about 900 (so, there are about 1 million of elements in mK). mK has small integers in it. p is found actually by solving the linear system X x mK = row. Now: how to program real problems in Haskell ? Should I try to set seq everywhere and see whether it helps ? Also note: seq mK' was not sufficient. I do not know, probably, as mK' has structure, seq does not evaluate all its levels. Therefore the programmer needs to invent a function that gathers much of information of mK' and puts it into one Integer (infoK' = sum ... mK'). Then, seq infoK' forces most of evaluation of mK'. Is this a generic style to program real problems ? To write all this strange code instead of plain let (_, p) = decompose mK row in putStr (shows p "\n") ? The story was as follows. My friend asked me to decompose certain large symmetric polynomial into elementary symmetric ones. This was needed for a real mathematical problem. I applied my DoCon program, which is written in Haskell. 1000 Mb RAM was not enough. I started to investigate, because I suspected that this case needs several times smaller memory. I found a fragment of the type shown above. And I never use `seq'. I have put a bit smaller example to make it 300 Mb sufficient. The effect was discovered by occasion. I have forgotten that `decompose' returns a pair with a large matrix as fst and wrote let p = decompose mK row in putStr $ show p It has computed in a relatively small memory, and fast, but before the p value, it printed several pages of the matrix value. I said "Oh! we need to improve this, we only need p, the second part": let (_, p) = decompose mK row in putStr $ show p And this takes 7 times more of memory and 2 times more of time! Then, I understood, what is happening and verified the idea by introducing seq. And now, I wonder ... Thank you in advance for your help and comments. Regards, ----------------- Serge Mechveliani mechvel(a)botik.ru

1 0

Failure building HEAD
by Gregory Wright 08 Jun '07

08 Jun '07

Hi, Today I was building HEAD using macports and had the error: configure: Using compiler: ../../compiler/ghc-inplace configure: Compiler flavor: GHC configure: Compiler version: 6.7.20070607 configure: Using package tool: ../../utils/ghc-pkg/ghc-pkg-inplace checking for gcc... gcc checking for C compiler default output file name... configure: error: C compiler cannot create executables See `config.log' for more details. (this was in libraries/base). The config.log showed the problem: configure:1680: checking for C compiler default output file name configure:1683: gcc -I/opt/local/include --configure-option=-O2 -I/ opt/local/include --configure-option=-I/opt/local/include -L/opt/ local/lib --configure-option=-L/opt/local/lib conftest.c >&5 cc1: error: unrecognized command line option "-fconfigure-option=-O2" cc1: error: unrecognized command line option "-fconfigure-option=-I/ opt/local/include"cc1: error: unrecognized command line option "- fconfigure-option=-L/opt/local/lib"configure:1686: $? = 1 It looks like cabal is messed up, passing "--configure-option=" when it should be stripping it out. Is this a problem with the HEAD branch or do I need a development version of cabal from the darcs repository to build the latest ghc? Best Wishes, Greg

2 4

GHC 6.6.1 on Debian Etch?
by Wagner Ferenc 08 Jun '07

08 Jun '07

Hi, what's the best way to install GHC 6.6.1 on a Debian Etch system? Basically: are there installable packages available somewhere, or should I recompile the Sid packages, or create a stub package from a binary .tar.gz bundle, or some other option I didn't think of? -- Thanks, Feri.

3 4

Prelude not in haskell98?
by Iavor Diatchki 08 Jun '07

08 Jun '07

Hello, I am using GHC 6.6 and I am trying to build a library using Cabal. The library is written in Haskell'98 so I made the Cabal file depend only on the package "haskell98". Unfortunately building the library fails with the following error: MyModule.hs:1:0: Failed to load interface for `Prelude': it is a member of package base, which is hidden The module "MyModule" does not have any imports (except for the implicitly imported Prelude). If I add an extra dependency on package "base", then the library compiles. All this seems to indicate that the Prelude is not a part of the "haskell98" package. Is this the case, and if so, is this intentional? It would be nice if we could create Cabal packages that explicitly indicate that the library depends only on Haskell 98 libraries. -Iavor

7 8

"GHC as a library" stalls when nobody is consuming it's output
by Mads Lindstrøm 08 Jun '07

08 Jun '07

Hi all While trying to implement a GUI for GHCi, I have run into an annoying concurrency problems. I think "GHC as a library" is at fault, as it stalls (maybe some deadlock) when nobody is consuming it's output. This message is a literate Haskell program, which illustrates the problem. This test-program starts a thread which prints an 'A' on stderr every second. Then it wait three seconds (meanwhile the 'A's are printing), and runs, via "GHC as a library", the following Haskell code "[1..]". If I start the program as: ./IsGhcBlocking >/dev/null everything works fine and the 'A' keeps coming out on stderr. However, if I do: ./IsGhcBlocking | sleep 10 I only see three 'A's. I believe that is because the sleep-command, do not consume any input. The program was tested on Debian Etch running GHC 6.6. > module Main where > Compile with: ghc -threaded -package ghc-6.6 --make IsGhcBlocking.lhs > import qualified GHC as GHC > import qualified Outputable as GHC > import qualified Packages as GHC > import qualified DynFlags as GHC > import qualified ErrUtils as GHC > > import System.IO > import Control.Concurrent > -- the path of our GHC 6.6 installation > path :: FilePath > -- path = "c:\\ghc-6.6" > path = "/usr/lib/ghc-6.6/" > > main :: IO() > main = do let printAs = do threadDelay (10^6) > hPutStrLn stderr "A" > printAs > forkOS printAs -- forkIO gives the same result > threadDelay (10^6 * 3) > session <- initializeSession > GHC.runStmt session "[1..]" > return () > > initializeSession = > do session <- GHC.newSession GHC.Interactive (Just path) > > -- initialize the default packages > dflags0 <- GHC.getSessionDynFlags session > let myLogAction _ locSpec style errMsg = hPutStrLn stderr showMsg where > showMsg = GHC.showSDoc $ GHC.withPprStyle style $ GHC.mkLocMessage locSpec errMsg > dflags1 = dflags0 { GHC.log_action = myLogAction } > (dflags2, packageIds) <- GHC.initPackages dflags1 > GHC.setSessionDynFlags session dflags2{GHC.hscTarget=GHC.HscInterpreted} > GHC.setContext session [] [] > return session The stalling becomes a problem, when one wants to interrupt "GHC as a library"'s runStmt function. One could interrupt "GHC as a library" with Panic.interruptTargetThread (see http://article.gmane.org/gmane.comp.lang.haskell.glasgow.user/12289) However, as "GHC as a library" locks up (stalls, deadlocks) there is no way of executing Panic.interruptTargetThread. Some people may suggest that I should always consume the output from "GHC as a library". But that is easier said than done. Many GUI libraries (including WxHaskell, which I am using) only allows for one active thread at a time (see http://wxhaskell.sourceforge.net/faq.html) Thus my GUI cannot simultaneously tell "GHC as a library" to interrupt it's execution and read it's output. For thus wondering how I can run both a GUI and "GHC as a library", if WxHaskell is not happy about threading, the answer is that I run the GUI and "GHC as a library" in separate processes. Greetings, Mads Lindstrøm

2 1

Indirection vs. in-place update of closures
by Stefan Holdermans 08 Jun '07

08 Jun '07

Hi, Is there any data available on how often, in GHC-generated code, closures are being updated in-place as opposed to and in comparison with being replaced by indirections to their results? How is it decided whether an in-place or an indirecting update is performed? Thanks, Stefan

2 1

debugging why we end up calling the wrapper rather than the worker
by Duncan Coutts 08 Jun '07

08 Jun '07

Hia all, I'm trying to figure out why this piece of code does not optimise the way I expect. It's binary serialisation again. Yes, again. The crux is the write function write :: Int -> (Ptr Word8 -> IO ()) -> Put () write !n body = Put $ \c buf@(Buffer fp o u l) -> if n <= l then write' c fp o u l else write' (flushOld c n fp o u) (newBuffer c n) 0 0 0 where {-# NOINLINE write' #-} write' c !fp !o !u !l = -- warning: this is a tad hardcore B.inlinePerformIO (withForeignPtr fp (\p -> body $! (p `plusPtr` (o+u)))) `seq` c () (Buffer fp o (u+n) (l-n)) In the if condition, the first path is the fast path. We do want this write' join point, we want to make a call to write' at runtime rather than inlining it into both the fast and slow paths. This is why we tag it with NOINLINE. Simon kindly recently fixed a bug where this NOINLINE was not remembered in the .hi files, so it now really does not inline write' into both branches. However, looking at the core/stg we can see that we're always calling the write' wrapper function that takes boxed arguments and calls the wrapper. It seems to me that the calls in both branches ought to be calls directly to the worker rather than the wrapper. We do have all the unboxed arguments available but they get boxed up to make the call to the write' wrapper. This isn't going to do good things for performance. Here's the STG code: So the important question is whether we have unboxed versions of all the args available. First of all lets look at the wrapper and see what args it unboxes when it calls the worker ($wwrite'_s17v in this case). write'_s17W = sat-only \r [w1_s17P w2_s17C w3_s17G w4_s17J w5_s17M] case w2_s17C of w6_s18S { GHC.ForeignPtr.ForeignPtr ww6_s17Q ww7_s17R -> case w3_s17G of w7_s18T { GHC.Base.I# ww8_s17S -> case w4_s17J of w8_s18U { GHC.Base.I# ww9_s17T -> case w5_s17M of w9_s18V { GHC.Base.I# ww10_s17U -> $wwrite'_s17v w1_s17P ww6_s17Q ww7_s17R ww8_s17S ww9_s17T ww10_s17U; }; }; }; }; So out of the args [w1_s17P w2_s17C w3_s17G w4_s17J w5_s17M] all but the first (which is a continuation function) get unboxed and the bits passed on to $wwrite'_s17v. So we should expect that if we have all those components available that we could make a direct call to the worker $wwrite'_s17v rather than going via the wrapper write'_s17W. So lets look at the STG code that we get from this bit of source: if n <= l then write' c fp o u l else write' (flushOld c n fp o u) (newBuffer c n) 0 0 0 (The STG code here is from a use when n was 3): We want to see if all the components that the worker $wwrite'_s17v needs are available: case <=# [3 ww5_s17X] of wild1_s18W { GHC.Base.False -> case Put.newBuffer w_s17Z n1_r16x of sat_s18d { __DEFAULT -> let { sat_s189 = NO_CCS GHC.Base.I#! [ww4_s187]; } in let { sat_s186 = NO_CCS GHC.Base.I#! [ww3_s184]; } in let { sat_s183 = NO_CCS GHC.ForeignPtr.ForeignPtr! [ww1_s180 ww2_s181]; } in let { sat_s18b = \u [] Put.flushOld w_s17Z n1_r16x sat_s183 sat_s186 sat_s189; } in write'_s17W sat_s18b sat_s18d lvl_r16z lvl_r16z lvl_r16z; }; GHC.Base.True -> let { sat_s18l = NO_CCS GHC.Base.I#! [ww5_s17X]; } in let { sat_s18j = NO_CCS GHC.Base.I#! [ww4_s187]; } in let { sat_s18h = NO_CCS GHC.Base.I#! [ww3_s184]; } in let { sat_s18f = NO_CCS GHC.ForeignPtr.ForeignPtr! [ww1_s180 ww2_s181]; } in write'_s17W w_s17Z sat_s18f sat_s18h sat_s18j sat_s18l; }; In the False case it looks like there is an excuse for calling the wrapper, because we're calling the wrapper for both Put.flushOld and Put.newBuffer. For Put.flushOld it's just to construct the continuation which is a boxed arg anyway, so that's not stopping us calling the worker. The Put.newBuffer returns a ForeignPtr and the write' worker takes the components of the ForeignPtr unboxed. However we are doing a case analysis on the result of Put.newBuffer so we could easily extract the components and pass them on to the write' worker. In the True case there is no excuse at all as far as I can figure out. We are explicitly boxing up exactly the arguments that the wrapper unboxes. So we really should be able to call the worker directly with the appropriate unboxed values as args. So what is going on here? Does NOINLINE prevent calling the worker or something? >From a quick experiment it would appear so: {-# OPTIONS_GHC -fbang-patterns #-} module Foo (foo, bar) where foo :: Int -> Int foo n = bar n bar :: Int -> Int bar !n = bar (n+1) As is, bar will not be inlined because it's recursive and looking at the STG code we see that foo makes a call to bar's worker: Foo.$wbar = \r [ww_sc8] case +# [ww_sc8 1] of sat_sca { __DEFAULT -> Foo.$wbar sat_sca; }; Foo.bar = \r [w_scd] case w_scd of w1_scl { GHC.Base.I# ww_scg -> Foo.$wbar ww_scg; }; Foo.foo = \r [eta_sck] Foo.bar eta_sck; however if we add in what you'd think is a redundant pragma {-# NOINLINE bar #-} and look at the stg code again: Foo.bar = \r [w_sc9] case w_sc9 of w1_sco { GHC.Base.I# ww_scc -> Foo.$wbar ww_scc; }; Foo.$wbar = \r [ww_scf] case +# [ww_scf 1] of sat_sch { __DEFAULT -> let { sat_scj = NO_CCS GHC.Base.I#! [sat_sch]; } in Foo.bar sat_scj; }; Foo.foo = \r [eta_scn] Foo.bar eta_scn; then we see that foo is now calling bar's wrapper, and what's worse, bar is calling it's wrapper in the recursive call! Oh noes! So it seems to me that NOINLINE should prevent inlining but not prevent calling the worker rather than the wrapper. I don't fully understand how NOINLINE interacts with the worker/wrapper transform (or I wouldn't have been surprised by this behaviour). I'm guessing that it works by doing the worker/wrapper split and then trying to inline the wrapper into as many call sites as possible. If this is indeed how it works then it'd explain why attaching NOINLINE to the function causes the observed behaviour since looking at the .hi file we see that the NOINLINE is attached to the wrapper function and not the worker. So perhaps the solution is to attach the NOINLINE to the worker rather than the wrapper when doing the worker/wrapper split. Would that work or cause other problems? Seems otherwise I'm stuck. I thought I could use NOINLINE to control the creation of join points like in my original example. Duncan

2 5

ghc-6.6.1 for FreeBSD/amd64 binary distribution
by Gregory Wright 05 Jun '07

05 Jun '07

Hi, I have put a binary distribution of ghc-6.6.1 for FreeBSD/amd64 at http://www.haskell.org/ghc/dist/6.6.1/ghc-6.6.1-x86_64-unknown- freebsd.tar.bz2 No documentation or ghci. The former might be easily remedied although using FreeBSD's docbook chain, as suggested in the wiki, fails when asked to generate printable docs. The latter seems to be a bigger project since my naive interpretation of the problem is that we need data relocations across a 2GB boundary. The binary works well enough to build itself and darcs. There are only sixteen unexpected test suite failures thus far. I am ignoring these for the moment while I get back to thinking about ghci. Note that you need to install libgmp to use the compiler. libgmp from the ports collection works fine. Best Wishes, Greg

3 4

too much let-floating
by Duncan Coutts 05 Jun '07

05 Jun '07

Hia folks, More performance bugs or misunderstandings. Yes, binary serialisation again. Consider this example from an instance for the Binary serialisation class. We get lots and lots of code that looks like this: data Foo a = Foo Int | Bar ... instance Binary Foo where put (Foo a) = putTag 0 >> put a put (Bar ...) = putTag 1 ... Let's expand this one step so we can see what we want to happen: put (Foo a) = word8 (fromIntegral 0 :: Word8) >> word64le a so we want to combine the bounds checks in word8 and word64le so that we do just one check here rather than two. Lets expand it another step: put (Foo a) = write 1 (pokeWord8 (fromIntegral 0 :: Word8)) `thenPut` write 8 (pokeWord64le (fromIntegral a :: Word64)) Now we have a rule: "write/write" forall n m a b. write n a `thenPut` write m b = write (n+m) (\p -> a p >> b (p `plusPtr` n)) so obviously we'd like to apply this rule here to common-up the bounds check that write n performs. Normally this rule works fine, but in this specific example it does not. Can you spot why? Here's a simple case that works: foo :: Word8 -> Word8 -> Put () foo a b = word8 a >> word8 b and the one that doesn't bar :: Word8 -> Put () bar a = word8 0 >> put a What's the difference? Why should one work and the other not? Of course I gave it away in the email subject: let floating. In the second example, the 'bar' function, word8 0 does not depend on the arguments of the function so it gets floated out: lvl_s198 = write 1 (pokeWord8 0) bar n = thenPut lvl_s198 (write 8 (pokeWord64le n)) and now the rule does not match this because 'write' isn't there directly in the expression. This is a bit disappointing of course, so how do we fix it. There are two possibilities as far as I can see. Either don't let float it, or have the rule matcher look through the indirection. The rule matcher is already looks through lets, but that's a slightly different issue. That's for a situation like: bar n = thenPut (let lvl_s198 = pokeWord8 0 in write 1 lvl_s198) (write 8 (pokeWord64le n)) where we've got an actual let expression whose body would match the rule's pattern. It would not always be a good idea to "look up" let floated vars when doing rule matching since it could lead to duplication. Though in this example the let-floated expression is used only once, so that is not a problem. So one possibility might be to look up variables for the purpose of rule matching if they are only used once. Another possibility might be to not let-float it in the first place. Usually let-floating things like this is a good idea, so how can we spot that we might want to keep it in applicative form? The fact that it's mentioned in the pattern of a rule is the strongest hint. As I understand it, being mentioned in the head of a rule is already taken into account when doing let-floating. However in this case the head of the let-floated expression is not the head of the rule, but a sub expression: write n a `thenPut` write m b = write (n+m) (\p -> a p >> b (p `plusPtr` n)) 'thenPut' is the head of this rule's pattern. But we'd rather not float 'write' out either. So perhaps a similar heuristic should be applied to all the free variables mentioned in the pattern. Another approach might be for the library author to declare that some function is cheap, or is otherwise important to not float out, but should be kept in applicative form to aid rule matching. We have similar problems with list comprehensions and enumFromTo: [ ... | i <- [0..n], j <- [0..m] ] because in the second generator [0..m] does not depend on the first generator, it gets floated out and shared. Of course with fusion we can make the [0..m] extremely cheap, but not if it has been floated out. If it gets floated out and shared in memory between each iteration of the first generator, then we really do have to traverse the list data structure each iteration, rather than just incrementing an unboxed number. So this is another example where we'd like to say that a function, enumFromTo in this case, is extremely cheap and should not be floated out, even if it looses sharing. Actually, my example is simpler because it does not involve any loss of sharing. Duncan

2 3

specialization using RULES
by Scott Dillard 05 Jun '07

05 Jun '07

Hello, This is somewhat related to this thread: http://www.haskell.org/pipermail/glasgow-haskell-users/2007-May/012646.html In that email I asked about the performance of gaussian elimination on small matrices represented by unboxed arrays, because I noticed that unsafeRead was unexpectedly slower than readArray (the cause of this is still unknown.) Mirko Rahn replied with an indexless algorithm where unboxed arrays are replaced by lists-of-lists. http://www.haskell.org/pipermail/glasgow-haskell-users/2007-May/012648.html Besides being infinitely more elegant, I noticed this was considerably faster than my array-based functions, perhaps because of inlining/deforestation/list fusion or some other crazy GHC optimization. So I re-wrote my little affine geometry library representing vectors as lists and matrices as list-of-lists. One thing I wanted this library to do was to enforce dimensionality of the vectors at the type level, so you could not add a two-vector to a three-vector, even though both functions are just "zipWith (+)". After trying to tune my library I came across the SPECIALIZATION/RULES pagmas in the GHC manual, and thought that this phantom dimensionality type would be great for specializing the vector functions, and indeed it speeds things up quite a bit. For instance, if I define > zipWithV :: (Dim d) => (s->s->s) -> Vec d s -> Vec d s -> Vec d s > zipWithV f (Vec u) (Vec v) = Vec( zipWith f u v ) then I can specialize > zipWithV3 :: (s->s->s) -> Vec Three s -> Vec Three s -> Vec Three s > zipWithV3 f (Vec [x,y,z]) (Vec [i,j,k]) = Vec [ f x i, f y j, f k z ] > {-# RULES "zipWith3" zipWithV = zipWithV3 #-} and it makes a nice improvement to the performance of this function. But here comes my problem: Ideally, I should only have to specialize zipWith, map and foldr like this, because everything you could want to do with a vector can be implemented with these functions. (Well, everything I want to do, anyway.) But unfortunately, if I define, say... > instance (Num s) => Num (Vec d s ) where ... (-) = zipWithV (-) > sqrNorm v = sumV ( mapV sqr v ) where sqr x = x*x And I use this as > distance u v = sqrt ( sqrNorm (u-v) ) > doSomethingWith (distance (u :: Vec Three Double) v) The rules do not fire. They only seem to fire if the specialized function is called directly, such as > doSomethingWith ( zipWith (-) (u :: Vec Three Double) v ) I surely do not want to have to specialize all of my vector functions. Just the building blocks. Can anyone shed some light on my situation? Under what conditions do the rules fire? As I understand it, they fire whenever the types are the same. As far as I can tell, this is the case. How can I change things to make the rules fire more often? Thanks, Scott

2 1