- Haskell-Cafe - Haskell.org

Ghc: -O harmful?
by Petr Skovron 08 Apr '09

08 Apr '09

Hello all, I have a haskell program that runs an order of magnitude slower when compiled with optimisations turned on. This happens on 6.8.2 as well as 6.10.1: petr@r4at184:/tmp[1]% ghc --make -fforce-recomp -o out buga.hs [1 of 1] Compiling Main ( buga.hs, buga.o ) Linking out ... petr@r4at184:/tmp% time ./out < 3-med.in >|/dev/null ./out < 3-med.in >| /dev/null 0,03s user 0,00s system 99% cpu 0,038 total petr@r4at184:/tmp% ghc --make -fforce-recomp -o out buga.hs -O [1 of 1] Compiling Main ( buga.hs, buga.o ) Linking out ... petr@r4at184:/tmp% time ./out < 3-med.in >|/dev/null ./out < 3-med.in >| /dev/null 0,99s user 0,01s system 99% cpu 1,001 total petr@r4at184:/tmp[1]% ghc --make -fforce-recomp -o out buga.hs -O2 [1 of 1] Compiling Main ( buga.hs, buga.o ) Linking out ... petr@r4at184:/tmp% time ./out < 3-med.in >|/dev/null ./out < 3-med.in >| /dev/null 0,99s user 0,01s system 99% cpu 1,004 total petr@r4at184:/tmp% ghc --version The Glorious Glasgow Haskell Compilation System, version 6.8.2 psxxxxxx:/tmp$ ghc --make -fforce-recomp -o out buga.hs [1 of 1] Compiling Main ( buga.hs, buga.o ) Linking out ... psxxxxxx:/tmp$ time ./out < 3-med.in >|/dev/null real 0m0.028s user 0m0.011s sys 0m0.007s psxxxxxx:/tmp$ ghc --make -fforce-recomp -o out buga.hs -O [1 of 1] Compiling Main ( buga.hs, buga.o ) Linking out ... psxxxxxx:/tmp$ time ./out < 3-med.in >|/dev/null real 0m0.252s user 0m0.225s sys 0m0.011s psxxxxxx:/tmp$ ghc --make -fforce-recomp -o out buga.hs -O2 [1 of 1] Compiling Main ( buga.hs, buga.o ) Linking out ... Vazeny pane, cekam na Vase rozkazy. psxxxxxx:/tmp$ time ./out < 3-med.in >|/dev/null real 0m0.239s user 0m0.225s sys 0m0.010s psxxxxxx:/tmp$ ghc --version The Glorious Glasgow Haskell Compilation System, version 6.10.1 The GHC documentation states that > -O2: > Means: "Apply every non-dangerous optimisation, even if it means > significantly longer compile times." The avoided "dangerous" > optimisations are those that can make runtime or space worse if > you're unlucky. They are normally turned on or off individually. If I understand this correctly, the dangerous optimisations should not be performed with -O. Am I doing anything wrong? Am I hitting a bug in GHC optimiser? A known one? The program source: -------------- petr@r4at184:/tmp$ cat buga.hs {-# LANGUAGE FlexibleContexts #-} import Control.Monad import Control.Monad.State data Predpoc a = Nic | Kus { delka :: Int, levy :: Predpoc a, pravy :: Predpoc a } deriving Show gList i = Kus 1 Nic Nic gPredpoc kus1 kus2 = Kus (delka kus1 + delka kus2) kus1 kus2 pop :: MonadState [a] m => m a pop = get >>= \(x:xs) -> put xs >> return x mbuild :: MonadState [Int] m => Int -> m (Predpoc Int) mbuild 1 = gList `liftM` pop mbuild n = liftM2 gPredpoc (mbuild n1) (mbuild n2) where n1 = n`div`2 n2 = n - n1 build n li = evalState (mbuild n) li best :: Predpoc Int -> Int -> Int -> Int best kus i j | i == 1 && j == delka kus = delka kus | j <= del1 = best (levy kus) i j | i > del1 = best (pravy kus) (i-del1) (j-del1) | otherwise = best (levy kus) i del1 + best (pravy kus) 1 (j-del1) where del1 = delka (levy kus) main = do n <- read `liftM` getLine pole <- liftM (build n . map read . words) getLine replicateM_ 100 $ do getLine print $ best pole 42 420 -------------- The sample input file (30k) can be downloaded from http://pikomat.mff.cuni.cz/petr/3-med.in I suspect that the main's variable "pole" (which is a large binary tree of type Predpoc Int) may be built from scratch in each iteration of the replicateM_ loop. Petr

3 3

Functions from Data.Hashtable
by Peter Verswyvelen 08 Apr '09

08 Apr '09

These functions have their arguments reversed when compare to e.g. Map For example Data.HashTable.lookup<http://haskell.org/ghc/docs/latest/html/libraries/base/Data-HashTable.html#…> :: HashTable<http://haskell.org/ghc/docs/latest/html/libraries/base/Data-HashTable.html#…> key val -> key -> IO<http://haskell.org/ghc/docs/latest/html/libraries/base/System-IO.html#t%3AIO> (Maybe<http://haskell.org/ghc/docs/latest/html/libraries/base/Data-Maybe.html#t%3A…> val) Data.Map.lookup<http://hackage.haskell.org/packages/archive/containers/0.2.0.0/doc/html/Dat…> :: Ord<http://hackage.haskell.org/packages/archive/base/4.0.0.0/doc/html/Data-Ord.…> key => key -> Map<http://hackage.haskell.org/packages/archive/containers/0.2.0.0/doc/html/Dat…> key val -> Maybe<http://hackage.haskell.org/packages/archive/base/4.0.0.0/doc/html/Data-Mayb…> val I find this a bit odd. Is this by design?

7 10

A challenge
by Thomas Davie 08 Apr '09

08 Apr '09

We have two possible definitions of an "iterateM" function: iterateM 0 _ _ = return [] iterateM n f i = (i:) <$> (iterateM (n-1) f =<< f i) iterateM n f i = sequence . scanl (>>=) (return i) $ replicate n f The former uses primitive recursion, and I get the feeling it should be better written without it. The latter is quadratic time – it builds up a list of monadic actions, and then runs them each in turn. Can anyone think of a version that combines the benefits of the two? Bob

5 12

stream fusion -- multi-module programs
by Jason Dusek 08 Apr '09

08 Apr '09

In the paper "Stream Fusion: From Streams To Lists To Nothing At All", we find: For large multi-module programs, the results are less clear, with just as many programs speeding up as slowing down. We ﬁnd that for larger programs, GHC has a tendency to miss optimisation op- portunities for stream fusible functions across module boundaries, which is the subject of further investigation. What's the state of these things? Is this still an issue for stream fusion? -- Jason Dusek

2 1

Re: A challenge
by Thomas Davie 08 Apr '09

08 Apr '09

Woops, the second version there applies it one too many times, it should have been replicate (n-1) f. Bob

1 0

Parallel combinator, performance advice
by Neil Mitchell 08 Apr '09

08 Apr '09

Hi, I've written a parallel_ function, code attached. I'm looking for criticism, suggestions etc on how to improve the performance and fairness of this parallel construct. (If it turns out this construct is already in a library somewhere, I'd be interested in that too!) The problem I'm trying to solve is running system commands in parallel. Importantly (unlike other Haskell parallel stuff) I'm not expecting computationally heavy Haskell to be running in the threads, and only want a maximum of n commands to fire at a time. The way I'm trying to implement this is with a parallel_ function: parallel_ :: [IO a] -> IO () The semantics are that after parallel_ returns each action will have been executed exactly once. The implementation (attached) creates a thread pool of numCapabililties-1 threads, each of which reads from a task pool and attempts to do some useful work. I use an idempotent function to ensure that all work is done at most one, and a sequence_ to ensure all work is done at least once. Running a benchmark of issuing 1 million trivial tasks (create, modify, read and IO ref) the version without any parallelism is really fast (< 0.1 sec), and the version with parallelism is slow (> 10 sec). This could be entirely due to space leaks etc when queueing many tasks. I'm useful for any thoughts people might have! Thanks in advance, Neil

5 25

Monad transformer to consume a list
by Stephan Friedrichs 08 Apr '09

08 Apr '09

Hello, is there a monad transformer to consume an input list? I've got external events "streaming into the monad" that are consumed on demand and I'm not sure if there's something better than a StateT. //Stephan -- Früher hieß es ja: Ich denke, also bin ich. Heute weiß man: Es geht auch so. - Dieter Nuhr

4 8

How to cut a file effciently?
by Magicloud Magiclouds 08 Apr '09

08 Apr '09

Hi, Let us say I have a text file of a million lines, and I want to cut it into smaller (10K lines) ones. How to do this? I have tried a few ways, none I think is lazy (I mean not reading the file all at the start). -- 竹密岂妨流水过山高哪阻野云飞

3 2

Painful Data Abstraction
by Brad Larsen 08 Apr '09

08 Apr '09

I asked this earlier on #haskell, but it was quiet hour. Here goes. Suppose I have an abstract data type for prefix dictionaries of bytestrings. I define a typeclass in a module PrefixDict.Class: module PrefixDict.Class where import qualified Data.ByteString.Char8 as B type Word = B.ByteString class PrefixDict d where empty :: d isEmpty :: d -> Bool insert :: Word -> d -> d delete :: d -> Word -> d hasWord :: d -> Word -> Bool hasPrefix :: d -> Word -> Bool I then write several implementations, including a naive list implementation, and a trie implementation, in the modules PrefixDict.ListDict and PrefixDict.TrieDict, both looking something like this: module PrefixDict.ListDict where import PrefixDict.Class data ListDict = ListDict [Word] instance PrefixDict ListDict where ... Now, there are many properties that should be satisfied by any implementation of PrefixDict, that are not easily captured in the type system. Trying to be a good coder, I write up some generic QuickCheck properties, such as prop_insert_idempotent :: (Eq d, PrefixDict d) => d -> Word -> Bool prop_insert_idempotent d w = insert w d' == d' where d' = insert w d The problem is this: I can't think of a non-kludged way of checking that TrieDict and ListDict satisfy this abstract property without having to add explicit type signatures, e.g. quickCheck (prop_insert_idempotent :: TrieDict -> Word -> Bool) I have many abstract properties, and I *really* don't like having to put an explicit signature on each one. I came up with a hackishway that minimizes the number of signatures required, by checking all abstract properties in one, generic function, reflecting a type as a value, and using scoped type variables: testAbstractProperties :: forall d. (PrefixDict d) => d -> IO () testAbstractProperties _ = do quickCheck (prop_insert_idempotent :: d -> Word -> Bool) quickCheck (prop_delete_works :: d -> Word -> Property) ... I then call this function from a "test suite" function written for each module, e.g. testTrieDict :: IO () testTrieDict = do testAbstractProperties (undefined :: TrieDict) testTrieDictSpecificProperties This means I only have to write the type signatures on the properties in one place, but it is still less than ideal. Is there a better way of doing this, or is Haskell simply not good at this kind of data abstraction? Best, Brad Larsen

2 1

cabal on mac os x (gmp problem)
by brian 08 Apr '09

08 Apr '09

For future reference: Solved, I just created a symlink to libgmp.dylib in /usr/local, and the zlib package was able to build.

1 0