May 2008 - Haskell-Cafe

Write Haskell as fast as C. [Was: Re: GHC predictability]
by Don Stewart 18 May '08

18 May '08

> I offer up the following example: > > mean xs = sum xs / length xs > > Now try, say, "mean [1.. 1e9]", and watch GHC eat several GB of RAM. (!!) > > If we now rearrange this to > > mean = (\(s,n) -> s / n) . foldr (\x (s,n) -> let s' = s+x; n' = n+1 > in s' `seq` n' `seq` (s', n')) (0,0) > > and run the same example, and watch it run in constant space. > > Of course, the first version is clearly readable, while the second one > is almost utterly incomprehensible, especially to a beginner. (It's even > more fun that you need all those seq calls in there to make it work > properly.) > > The sad fact is that if you just write something in Haskell in a nice, > declarative style, then roughly 20% of the time you get good > performance, and 80% of the time you get laughably poor performance. I've written an extended post on how to understand and reliably optimise code like this, looking at it all the way down to the assembly. The result are some simple rules to follow for generated code as good as gcc -O2. Enjoy, http://cgi.cse.unsw.edu.au/~dons/blog/2008/05/16#fast -- Don

16 32

ByteString comparison question (was: another Newbie performance question)
by Philip Müller 18 May '08

18 May '08

Hi, I'm changing my CSV program to use ByteStrings, but I have problems with this: readCSVLine :: String -- line as String -> [String] -- line broken down into the value Strings readCSVLine = unfoldr builder where builder [] = Nothing builder xs = Just $ readField xs readField [] = ([],[]) readField (',':xs) = ([],xs) readField ('"':xs) = (field,rest) where (field,'"':rest) = break (== '"') xs So far, I have something like this - doesn't look too good to me, and doesn't compile: import qualified Data.ByteString as B import qualified Data.ByteString.Char8 as C8 type CSV = [[B.ByteString]] readCSVLine :: B.ByteString -- line as String -> [B.ByteString] -- line broken down into the value Strings readCSVLine = unfoldr builder where builder xs | xs == B.empty = Nothing | otherwise = Just $ readField xs readField xs | xs == B.empty = ([],[]) | B.head xs == ',' = ([], B.tail xs) | B.head xs == '"' = (field, B.tail rest) where field,rest) = B.break (== '"') xs I do not know how to compare a Word8 to a Char. Or maybe I don't need to? Regards Philip

3 4

Type inference; always
by Peter Verswyvelen 18 May '08

18 May '08

In Haskell, I sometimes have to annotate code with type info because the type-inferer otherwise fails (even with |-XNoMonomorphismRestriction)|. Surely, most of the time this is because I was writing buggy code, but sometimes, type annotation just seems needed to get a successful compilation (luckily not as often as in C# 3.0) It seems some new papers appeared regarding this, e.g. http://research.microsoft.com/~simonpj/papers/boxy Is this work being incorporated into GHC? Unfortunately I'm not able to read those papers, so I'm not really sure what it means anyway and what implications (example code?) it would have ;-) Cheers, Peter

5 5

STM applications
by Nehir Sonmez 18 May '08

18 May '08

Good day all, We are Haskell STM researchers, looking for Haskell applications written using STM for profiling their STM behaviour. The benchmark currently consists of the ones in: www.cs.rochester.edu/meetings/TRANSACT07/papers/perfumo.pdf (3rd page) + binary trees + parallel sudoku and additional programs would be greatly greatly appreciated... Cheers, Nehir Sonmez Barcelona Supercomputing Center PS: We also know of Conjure and Happs.

1 0

hmp3 compilation problem
by Levi Stephen 18 May '08

18 May '08

Hi, I am trying to compile hmp3. I have the version from darcs at http://code.haskell.org/~dons/code/hmp3 I am getting the following errors: Tree.hs:190:14: No instance for (Binary FilePathP) arising from a use of `get' at Tree.hs:190:14-16 Possible fix: add an instance declaration for (Binary FilePathP) In a 'do' expression: nm <- get In the expression: do nm <- get i <- get return (File nm i) In the definition of `get': get = do nm <- get i <- get return (File nm i) Tree.hs:236:31: Couldn't match expected type `L.ByteString' against inferred type `bytestring-0.9.0.1:Data.ByteString.Lazy.Internal.ByteString' In the second argument of `L.writeFile', namely `(compress (encode s))' In the expression: L.writeFile f (compress (encode s)) In the definition of `writeTree': writeTree f s = L.writeFile f (compress (encode s)) Tree.hs:240:46: Couldn't match expected type `bytestring-0.9.0.1:Data.ByteString.Lazy.Internal.ByteString' against inferred type `L.ByteString' In the first argument of `decompress', namely `s' In the first argument of `decode', namely `(decompress s)' In the first argument of `return', namely `(decode (decompress s))' Any help is much appreciated. Thanks, Levi

2 1

Starting Haskell with a web application
by Jonathan Gardner 18 May '08

18 May '08

I am sure I am missing something obvious, but since the cafe is the place to ask stupid questions... I am getting more and more excited about Haskell as I learn more and more about it. Professionally, and as a hobby, I love working on web applications. Where do I get started in writing a web app with Haskell? I am looking more for a framework like Pylons and less like Apache, if that helps. I am sure someone has already done the homework on this, so a link will be fine. -- Jonathan Gardner jgardner(a)jonathangardner.net

11 15

Another optimization question
by Jeroen 18 May '08

18 May '08

Hi, I know there's been quite some performance/optimization post lately, so I hope there still room for one more. While solving a ProjectEuler problem (27), I saw a performance issue I cannot explain. I narrowed it down to the following code (never mind that 'primes' is just [1..], the problem is the same or worse with real primes): primes :: [Int] primes = [1..] isPrime :: Int -> Bool isPrime x = isPrime' x primes where isPrime' x (p:ps) | x == p = True | x > p = isPrime' x ps | otherwise = False main = print $ length (filter (== True) (map isPrime [1..5000])) $ time ./experiment1 5000 real 0m4.037s user 0m3.378s sys 0m0.060s All good, but if I change isPrime to the simpeler isPrime x = elem x (takeWhile (<= x) primes) it takes twice as long: time ./experiment2 5000 real 0m7.837s user 0m6.532s sys 0m0.141s With real primes, it even takes 10 times as long. I tried looking at the output of ghc -ddump-simpl, as suggested in a previous post, but it's a bit over my head (newby here...). Any suggestions? Thanks a lot, Jeroen

7 14

Std lib equivalent for liftM concat . sequence
by Alistair Bayley 18 May '08

18 May '08

A couple of days ago I had need for: > concatM :: Monad m => [m [a]] -> m [a] > concatM = liftM concat . sequence but found no such thing in the std libs, except perhaps for msum (I don't want to add instances for MonadPlus. Should I have to?). Have I missed something trivial? Alistair

4 5

Random numbers and splitting
by Lauri Oksanen 18 May '08

18 May '08

Hi, Does there exists any random number generator in Haskell that is suitable for doing heavy simulations and that can be splitted? At least there exists some c implementations of such generators, see http://www.iro.umontreal.ca/~lecuyer/myftp/papers/streams00.pdf Also some new theory for Mersenne Twister and its relatives exists, see http://www.iro.umontreal.ca/~lecuyer/myftp/papers/jumpf2.pdf http://www.iro.umontreal.ca/~lecuyer/myftp/papers/jumpmt.pdf I'm trying to implement Metropolis algorithm with lazy mutations and a state space that is infinite dimensional in theory (although, of course, not in practice). Without good splitting I'm forced to write as ugly code as with non-lazy language. Thanks in advance, Lauri

2 1

Multi threaded garbage collector
by Peter Verswyvelen 18 May '08

18 May '08

Hi all, I did some experiments with concurrent Haskell, and unfortunately I couldn't get my code run faster when using more cores, actually it ran a bit slower. Now I noticed after profiling that about 70% of the time my program was performing garbage collection (I had lists of 50000 tiny objects that got recreated 100 times per second). If I understood it correctly, the current garbage collector of GHC is single threaded, which really hinders SMP Any plans on improving this or workarounds? Thanks, Peter

4 3