February 2009 - Glasgow-haskell-users

Type (class) recursion + families = exponential compile time?
by Ben Franksen 27 Feb '09

27 Feb '09

Hi the attached module is a much reduced version of some type-level assurance stuff (inspired by the Lightweight Monadic Regions paper) I am trying to do. I am almost certain that it could be reduced further but it is late and I want to get this off my desk. Note the 4 test functions, test11 .. test14. The following are timings for compiling the module only with all test functions commented out, except respectively, test11, test12, test13, and test14: ben@sarun[1] > time ghc -c Bug2.hs ghc -c Bug2.hs 1,79s user 0,04s system 99% cpu 1,836 total ben@sarun[1] > time ghc -c Bug2.hs ghc -c Bug2.hs 5,87s user 0,14s system 99% cpu 6,028 total ben@sarun[1] > time ghc -c Bug2.hs ghc -c Bug2.hs 23,52s user 0,36s system 99% cpu 23,899 total ben@sarun[1] > time ghc -c Bug2.hs ghc -c Bug2.hs 102,20s user 1,32s system 97% cpu 1:45,89 total It seems something is scaling very badly. You really don't want to wait for a version with 20 levels of nesting to compile... If anyone has a good explanation for this, I'd be grateful. BTW, I am not at all certain that this is ghc's fault, it may well be my program, i.e. the constraints are too complex, whatever. I have no idea how hard it is for the compiler to do all the unification. Also, the problem is not of much practical relevance, as no sensible program will use more than a handfull levels of nesting. Cheers Ben

3 2

optimization and rewrite rules questions
by Claus Reinke 26 Feb '09

26 Feb '09

In the recently burried haskell-cafe thread "speed: ghc vs gcc", Bulat pointed out some of the optimizations that GHC doesn't do, such as loop unrolling. I suggested a way of experimenting with loop unrolling, using template haskell to bypass GHC's blindspot (it usually doesn't unfold recursive definitions http://www.haskell.org/pipermail/glasgow-haskell-users/2007-July/012936.html , but if we unfold a loop combinator at compile time, GHC's normal optimizations can take over from there): http://www.haskell.org/pipermail/haskell-cafe/2009-February/056241.html While this is fine as far as it goes (it should really be handled within GHC), and does offer some initial speedup, Bulat pointed out that GCC does further optimizations after unrolling, such as reassociating sums to expose potential for constant folding: http://www.haskell.org/pipermail/haskell-cafe/2009-February/056367.html (since the ghc -ddump-simpl output doesn't show this optimization, I assume that gcc handles it, and the "*ghc*" in that message is a typo, but haven't checked - how would I do that, btw?). In this case, GHC optimizations following the loop unrolling leave a sum like (note the repeated variable interspersed with constants) (GHC.Prim.+# (GHC.Prim.+# ww_s1lN 3) (GHC.Prim.+# (GHC.Prim.+# ww_s1lN 2) (GHC.Prim.+# (GHC.Prim.+# ww_s1lN 1) (GHC.Prim.+# (GHC.Prim.+# ww_s1lN 0) ww_s1lR)))))))) which can be simplified (assuming associativity and commutativity of + here..) after sorting the variable references and constants into separate groups. We currently inherit such optimizations when using -fvia-C, even though GHC sometimes produces C code that GCC can't handle optimally. If I understand correctly, -fvia-C is on its way out - is that correct, and what plans are there for recovering the optimizations previously left to GCC? The next thing I was looking at was rewrite rules, the obvious GHC tool for implementing this kind of rule (var+const1)+(var+const2) ==> 2*var + const3 and I ran into more questions: - can RULES left-hand sides test for variables (I don't want to reassociate sums randomly, that wouldn't terminate; instead, I want to float out subterms that are non-variable, and group repeated variables)? - is there any way to control the rewrite strategy, similar to strategy combinators (if rules are applied all over the place, they introduce new structure not covered by rules; if I could limit the strategy to top-down, or bottom-up, I could at least cover some special cases)? - how would one handle this kind of optimization in GHC in full generality? wait for compiler plugins? are there features of rewrite rules that I'm missing? would it make sense to flag rewrite rules system improvements as a GHC GSoC project, given that GHC will have to pull its weight there when moving away from GCC? Claus

3 5

finally part run twice on Ctrl-C
by Neil Mitchell 26 Feb '09

26 Feb '09

Hi, I've got the following code: import Control.Exception import System.Cmd main = system "sleep 1m" `finally` putStrLn "goodbye" When compiled with GHC 6.10.1.20090225, if I hit Ctrl-C during the sleep, I get the goodbye printed twice. If I leave evaluation to finish normally I get goodbye once. Is this a bug? Thanks Neil

1 0

queued GHCi commands are not context specific; a bug?
by Peter Hercek 25 Feb '09

25 Feb '09

Hi GHCi users, The example is at the end of this email. I think it is a bug that the second part (:continue) of the command `:cmd return "rv\n:continue"' is executed in a different context than the first part (rv (request for the value of rv variable)). Notice that we did not stop at breakpoint 1 (line 7). Well, the stop happened but it continued immediately because of queued :continue command. But the command was queued in the context of breakpoint 0 and not breakpoint 1. Is it a feature or a bug? If it is a feature it is not good for scripting breakpoints :-/ ... and I do not see an easy way to work around it. Thanks, Peter. PS: I owe responses to some of you on this list, but I must check some docs or do some tests first so I hope I'll answer during weekend at worst. *status:0 peter@metod [716] ~/tmp %* grep -n '^' b.hs 1:fn :: Int -> Int 2:fn x = 3: let rv = add x 1 in 4: rv 5: 6:add :: Int -> Int -> Int 7:add a b = a + b *status:0 peter@metod [717] ~/tmp %* ghci b.hs GHCi, version 6.10.1: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer ... linking ... done. Loading package base ... linking ... done. [1 of 1] Compiling Main ( b.hs, interpreted ) Ok, modules loaded: Main. *Main> :set stop :list *Main> :break 4 Breakpoint 0 activated at b.hs:4:2-3 *Main> :break 7 Breakpoint 1 activated at b.hs:7:0-14 *Main> fn 100 Stopped at b.hs:4:2-3 _result :: Int = _ rv :: Int = _ 3 let rv = add x 1 in 4 *rv* 5 [b.hs:4:2-3] *Main> :cmd return "rv\n:continue" Stopped at b.hs:7:0-14 _result :: Int = _ 6 add :: Int -> Int -> Int 7 *add a b = a + b* 8 101 [b.hs:4:2-3] *Main> :continue 101 *Main> :q Leaving GHCi. *status:0 peter@metod [718] ~/tmp % *

1 0

Bug in STM with data invariants
by Ben Franksen 25 Feb '09

25 Feb '09

My ghc(i) crashes when using STM data invariants. This little piece of code demonstrates the problem: module Bug where import Control.Concurrent.STM test = do x <- atomically $ do v <- newTVar 0 always $ return True -- remove this line and all is fine return v atomically (readTVar x) >>= print This is what ghci makes of it: ben@sarun> ghci Bug.hs GHCi, version 6.10.1: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer ... linking ... done. Loading package base ... linking ... done. [1 of 1] Compiling Bug ( Bug.hs, interpreted ) Ok, modules loaded: Bug. *Bug> test Loading package syb ... linking ... done. Loading package array-0.2.0.0 ... linking ... done. Loading package stm-2.1.1.2 ... linking ... done. zsh: segmentation fault ghci Bug.hs I am using ghc-6.10.1 freshly installed from source with just a 'cabal install stm' thrown after it. BTW, the documentation for Control.Concurrent.STM.TVar lists... nothing. Similar with Control.Monad.STM. Well, at least the source link works, so one isn't completely lost... :-) Cheers Ben

2 1

Performance Issue
by James Swaine 24 Feb '09

24 Feb '09

i'm implementing a benchmark which includes a detailed specification for a random number generator. for any of the kernels outlined in the benchmark, i might have to generate a set of random numbers R, which has a length n, using the following formulas: R[k] = ((2^-46)(X[k])) mod 2^46, where X[k] = (a^k)s where the values of a and s are constant and defined below. many of the kernels in the benchmark require a large number of randoms to be generated (in the tens of millions). when i invoke the following getRandAt function that many times to build up a list, evaluation of the list takes forever (somewhere between 5 and 10 minutes). i've tried optimizing this several different ways, with no luck. i though i might post my code here and see if anyone notices anything i'm doing wrong that might be causing such a large bottleneck: --constants a :: Int64 a = 5^13 divisor :: Int64 divisor = 2^46 multiplier :: Float multiplier = 2**(-46) --gets r[k], which is the value at the kth --position in the overall sequence of --pseudorandom numbers getRandAt :: Int64 -> Int64 -> Float getRandAt 0 seed = multiplier * (fromIntegral seed) getRandAt k seed = multiplier * (fromIntegral x_next) where x_prev = (a^k * seed) `mod` divisor x_next = (a * x_prev) `mod` divisor thanks all in advance for your help! -james

1 0

./T and ./T >& log
by Serge D. Mechveliani 24 Feb '09

24 Feb '09

People, I observe the output difference in running ./Bug and ./Bug >& log (under Linux) for the program import Dumatel main = do calcInput <- readFile "List0.inp" (putStr $ parseComputeShow calcInput) where parseComputeShow calcInput = concat ["t = ", showsn 3 t "\n", "tR = ", showsn 3 tR "\n"] where calc = addInput_default nilParseOpts (bool rpos) calcInput t = parse_default calc "parsing Term" "(a:nil) + (b:nil)" tR = evaluate emptyUMRMemo AllRules calc t -- I think, it can be reduced to much simpler one. The error break has to occur while computing tR. The difference is in printing or skipping of the result part before tR. The first command outputs --------------------------------- t = ((a : nil) + (b : nil)) Bug: substitute {(X, a), (Xs, nil), (Ys, (b : nil))} X: sort mismatch in substitution --------------------------------- And the second command skips (in ./log) the line of t = ... Who can tell what is the matter? How to have identic outputs in this example? Thank you in advance for explanation. ----------------- Serge Mechveliani mechvel(a)botik.ru

5 5

Building GHC on Windows
by Felix Martini 23 Feb '09

23 Feb '09

Hi all, Simon Marlow has recently posted a patch that adds Unicode support to Handle I/O. He mentioned that it didn't work yet on Windows so i was thinking of looking at the source code to see how the new Unicode support works and perhaps try to make it work on Windows. I have built GHC from source in the past on Windows and the process was cumbersome compared to building it on Linux. But i was curious to see if it has gotten easier. After reading the Wiki i decided to get the source with Git as Darcs was slow with remote downloads. Ok, that was a lot quicker than before! Let's see, i need to run sync-all to get the core libraries. I remember that i used to use darcs-all so it must be a new script. Sync-all doesn't have an extension so i probably need to run it with msys. That doesn't work, somehow my msys environment does not find git. So let's try the Git Bash environment which also uses msys (and does not have bash). Now i get a cryptic error: "at ./sync-all line 99, <IN> line 19." It seems the script cannot determine the default remote repo. The top line shows that it is a Perl script and i don't know Perl enough to see what is wrong. I have Perl installed on this Windows pc so let's try to run the script directly. That doesn't work either: the Perl script wants to use grep and sed. All this is likely trivial to fix but at the same time these little roadblocks may also explain why few developers on Windows contribute code to GHC and Haskell. Regards, Felix

3 6

DLL support with GHC
by Neil Mitchell 22 Feb '09

22 Feb '09

Hi, What is the current status of shared object support within GHC? Using GHC 6.10.2 (or the branch for it) I can create DLL's under Windows, following these instructions: http://www.haskell.org/ghc/docs/latest/html/users_guide/win32-dlls.html .Can a similar thing be done under Linux? If so, where is this documented? Many thanks Neil

2 2

Re: [Haskell-beginners] Baffled by Parsec
by Antoine Latter 22 Feb '09

22 Feb '09

On Sun, Feb 22, 2009 at 2:14 AM, Felipe Lessa <felipe.lessa(a)gmail.com> wrote: > > My GHC 6.10.1 was compiled from source and Parsec comes from a > different ebuild (Gentoo), and digit isn't documented as well. It must > be some problem with parsec < 3, because Hackage has the same problem > for old Parsec[1]. > > [1] http://hackage.haskell.org/packages/archive/parsec/2.1.0.1/doc/html/Text-Pa… > >From the sources: > upper, lower, alphaNum, letter, digit, hexDigit, octDigit :: CharParser st Char I think I've seen Haddock have trouble documenting declarations which share a type signature in other places, as well. Antoine

1 0