- Haskell-Cafe - Haskell.org

Performance help
by Justin Bailey 14 Nov '07

14 Nov '07

I've been working on a program over the last few days to evolve cellular automata rules using a genetic algorithm. Luckily, this email has nothing to do with CAs but everything to do with Haskell performance. For those who don't know, a CA is represented as a row of cells, where each can be either black (on/1) or white (off/0). A CA is "run" by generating a new row from the previous row according to some rule. Each cell is examined in turn and based on the state of it's neighbors and itself, a new cell in the next row is generated that is either black or white. The function below is my "step" function that generates this new row. It's at the heart of my program and where all the execution time is spent. In this scenario it's executed around 800 million times. On my relatively modest desktop using GHC 6.8.1, the program takes about 30 seconds to run. Here's the function, with some of the type declarations: data Rule = Rule { ruleWidth :: Int, rules :: UArray Int Bool } data Ring = Ring { currIdx :: !Int, vals :: (UArray Int Bool), lower, upper, size:: !Int } type CA = Ring currR :: Int -> Ring -> Bool currR amt r@(Ring curr arr l u s) = unsafeAt arr ((curr + amt) `mod` s) stepWithUArray :: Int -> Rule -> CA -> CA stepWithUArray rowLen rule@(Rule width rules) row = let upper = rowLen - 1 getRule currIdx = pattern' start 0 where start = currIdx - width end = currIdx + width pattern' cnt !result | cnt > end = result | otherwise = if (currR cnt row) then pattern' (cnt + 1) (result * 2 + 1) else pattern' (cnt + 1) (result * 2) makeNewRow :: ST s (ST.STUArray s Int Bool) makeNewRow = do arr <- ST.newArray_ (0, upper) let fill idx | idx > upper = return () | otherwise = do unsafeWrite arr idx (unsafeAt rules (getRule idx)) fill (idx + 1) fill 0 return $! arr in fromUArray (ST.runSTUArray makeNewRow) fromUArray produces a new Ring (i.e. CA) from an array. 'makeNewRow' iterates over every cell in the current row using getRule to get the new value for each cell and returns the new row as an array. getRule essentially treats the neighbors of the current cell as bits, with the most significant to the left. An index into the rules array is constructed based on the values around the cell being examined (which wrap on the ends, thus the Ring construct). That index is used to get the value of the new cell from the rules array. Profiling shows that the following lines take up the most execution and allocation: makeNewRow = ... -- 20.5% execution, 26.7% allocation if (currR cnt row) ... -- 14.7% execution, 26.6% allocation, in pattern' currR ... -- 14.7% execution, 0% allocation Any suggestions for improving this code? Thanks in advance! Justin p.s. The entire program is attached. Compile with ghc -O2 -funbox-strict-fields -fbang-patterns --make GA-CA.hs. It runs 25 rules on each of 25 initial CAs for 2 generations. p.p.s. On the bright side, this program has excellent memory performance. It uses a constant 2 - 7 MB depending on the initial parameters for the entire run. Beautiful!

4 8

Somewhat random history question
by Andrew Coppin 14 Nov '07

14 Nov '07

Somebody just asked me "...if GHC is written in Haskell, how the heck did they compile GHC in the first place?"

19 37

Haskell library documentation question
by Galchin Vasili 13 Nov '07

13 Nov '07

Hello, Is there anyway to get a .pdf version of http://www.haskell.org/ghc/docs/latest/html/libraries/? Kind regards, Vasili

2 1

Annoying (windows only?) related GHCi "problem"?
by Peter Verswyvelen 13 Nov '07

13 Nov '07

When I start a windowed program (e.g. GLUT or GTK2Hs) from within GHCi, my application's window does not become the foreground window. Is this on purpose? Thanks, Peter

2 1

Trouble using HDBC-postgres on Windows - can't find libpq.dll
by Justin Bailey 13 Nov '07

13 Nov '07

I've compiled HDBC 1.0.1 and HDBC-postgresql-1.0.1 under Windows with a little tweaking. However, when I try to run the tests I get this error: >runghc -package HDBC-postgresql runtests.hs ghc.exe: can't load .so/.DLL for: pq (addDLL: unknown error) libpq.dll is in my path, and I added the correct paths to the .cabal file when I built it. Does anyone have an idea what might be the problem? Justin p.s. I have postgres 8.2 installed if that matters.

2 3

Building Haskell stuff on Windows
by Arthur van Leeuwen 13 Nov '07

13 Nov '07

Hello all, maybe I'm just not used enough to Windows, but let me explain my woes of today. It seems to me to be *much* too hard to get a full install of GHC + GTK2Hs going on Windows, going from the idea that I want the currently released stable versions of everything. So, this is the way I progressed (from a clean Windows install): - Installed MinGW 5.1.3 - Installed MSYS 1.0.10 - Installed GHC 6.8.1 - edit /etc/fstab in MSYS to correctly bind MinGW - Installed gtk-dev-2.10.11-win32-1 - Downloaded gtk2hs-0.9.12.tar.gz - cd /d/haskell/gtk2hs-0.9.12 - ran configure - discovered I needed happy (this was not documented!) - Downloaded happy-1.17.tar.gz - unpacked, configured, built, installed - ran configure for gtk2hs - discovered I needed alex (this was not documented!) - Downloaded alex-2.10.tar.gz - Setup.lhs of alex-2.10 did not compile due importing Distribution.Simple(compilerPath) - Installed darcs - darcs got alex development tree - Setup.lhs of alex-2.10 compiled - building alex-2.10 failed due to wishing an existing alex - broke down and downloaded alex-2.10 binaries - installed alex-2.10 next to happy in C:\Program Files\Haskell\bin - ran configure for gtk2hs - ran make - discovered alex should not be in C:\Program Files as make breaks on paths with embedded spaces... - copied C:\Program Files\Haskell to C:\Haskell and modified $PATH - reran configure for gtk2hs - ran make - discovered gtk2hs 0.9.12 hides 'containers' - broke down and darcs got gtk2hs development tree - installed automake - ran autoreconf - discovered automake for MSYS 1.0.10 is too old - installed automake-1.9 - ran aclocal-1.9 - ran autoconf - ran configure - discovered I need to explicitly add GTK libs to aclocal - ran aclocal-1.9 -I with GTK library path - ran autoconf - ran configure for gtk2hs - ran make - complained on IRC - ran make install - sighed deeply Ofcourse, on complaining I learned that hackage contains alex 2.2, rather than 2.10, but that is not apparent from the alex webpages. It seems to me that much of this is way too hard to figure out... figuring out the dependency graph should not be necessary, as the developers should know what parts go into their code! Furthermore, as much as I applaud hackage, it is not ready for use, as it does not afford things you might want, such as searching for latest (stable) releases of packages. Plus, it is still not the default go-to place for many things. Maybe developers that decide to put their most recent versions on hackage could document that on the main webpages of their code? (I've ran into this with FileManip as well, not just with Alex). With kind regards, Arthur. -- /\ / | arthurvl(a)cs.uu.nl | Work like you don't need the money /__\ / | A friend is someone with whom | Love like you have never been hurt / \/__ | you can dare to be yourself | Dance like there's nobody watching

11 18

Ray tracer benchmark: GHC 6.6 vs 6.8
by Jon Harrop 13 Nov '07

13 Nov '07

Following Lennart Augustsson's improvements of the Haskell implementations of my ray tracer language comparison: http://augustss.blogspot.com/2007/11/benchmarking-ray-tracing-haskell-vs.ht… I thought I'd share the performance improvements offered by Lennart's new code with the latest release of GHC. Time in seconds to run the five versions on my Athlon64 X2 2.2GHz running 64-bit Debian Lenny: ghc-6.6.1 22.0715339184 16.5431628227 13.3524830341 11.1260569096 6.33169198036 ghc-6.8.1 16.654654026 12.3998670578 7.8039829731 7.31486296654 6.03285193443 So 6.8 is up to a third faster! The fastest implementations in other language run at around 4s, so Haskell has gone from being 3x slower in the previous implementations with GHC 6.6 to only 50% slower with the new implementations and new GHC. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/products/?e

1 0

Using type-level programming to tag functions with time and space complexity
by Daniel McAllansmith 13 Nov '07

13 Nov '07

I was wondering if anyone had done work on tagging functions at the type level with their time or space complexity and, if it's even feasible, calculating the complexity of compound functions. Any pointers? Cheers Daniel

3 2

Interesting effect of upgrading GHC
by Andrew Coppin 13 Nov '07

13 Nov '07

Hi guys. I just removed GHC 6.6.1 and installed 6.8.1, and I noticed something rather unexpected. I recompiled an existing program (with -O2), and instead of taking 30 seconds to compile, it took roughly 2 seconds. That's a really serious speedup! o_O Anybody have any idea what might have caused this? (Not, you understand, that I'm complaining! But the release notes say 10-15% faster, not 15,000% faster...) I am also curiose to see whether the compiled code execution speed is better/worse - but the program in question is mainly GUI, so I can't test it with that... Perhaps my Chaos program? ;-)

5 4

can someone explain monad transformers to me, or how do you combine maybe and IO?
by Anatoly Yakovenko 13 Nov '07

13 Nov '07

I wanted something that would work like liftM but with IO as well, so something like this: > liftM ((+) 1) $ Just 1 Just 2 but with the function lifted being of type (a -> IO b). so I came up with maybeIO::(a -> IO b) -> (Maybe a -> IO (Maybe b)) maybeIO ff = (\ aa -> case aa of Nothing -> return $ Nothing Just vv -> do rv <- ff vv return $ Just rv) incIO:: Int -> IO Int incIO ii = return $ ii + 1 > maybeIO incIO $ Just 1 Just 2 works just like I want it to. But isn't this something that a monad transformer should be able to do?

3 2