Hello all, A question on that most elusive of subjects.... performance in haskell (GHC 6.2) Using the GHC profiler, I obtained the following analysis results (i hope the code doesn't come out too ugly by mail): total time = 0.92 secs (46 ticks @ 20 ms) total alloc = 83,373,032 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc isIn Main 50.0 22.8 getCon Main 13.0 16.7 o' Main 8.7 6.6 satisfies Main 6.5 0.0 powerList Main 6.5 46.9 CAF Main 6.5 0.1 showCon Main 4.3 0.3 MAIN MAIN 4.3 0.0 a' Main 0.0 6.7 The problem child, that isIn function, has got about 78000 entries in the profile log. I should probably mention that this is an incredibly dumbed down version of the program, the dimensions of the data it is supposed to handle are such that, on a trial run I killed the process after about 15 minutes, when I found out it hadn't even completed 3% of its task. sad stuff, really. Anyways, 'isIn' is a predicate that checks whether a given Double lies within an interval, where intervals are defined as ... define an interval bound, either inclusive (I) or exclusive (E)
data Bound = I Double | E Double deriving (Eq, Show, Ord) data Interval = Il Bound Bound | Nil Bound Bound deriving (Eq,Ord)
where Nil acts as the complement of an interval, this is reflected in the isIn function. ....
isIn :: Double -> Interval -> Bool isIn r (Nil x y) = not (isIn r (Il x y)) isIn r (Il (I x) (I y)) = r >= x && r <= y isIn r (Il (I x) (E y)) = r >= x && r < y isIn r (Il (E x) (I y)) = r > x && r <= y isIn r (Il (E x) (E y)) = r > x && r < y
I tried rewriting it to something that intuitively 'feels' like it should be faster, but i have no real idea about the cost of the respective haskell expressions: ... version 2
isIn :: Double -> Interval -> Bool isIn r (Nil x y) = not (isIn r (Il x y)) isIn r (Il x y) = case x of (I x') -> if r >= x' then case y of (I y') -> r <= y' (E y') -> r < y' else False (E x') -> if r > x' then case y of (I y') -> r <= y' (E y') -> r < y' else False
... which indeed turns out to be a tad bit faster, according to the new profile log. total time = 0.80 secs (40 ticks @ 20 ms) total alloc = 64,404,104 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc isIn Main 30.0 0.0 getCon Main 25.0 21.6 powerList Main 15.0 60.7 showCon Main 7.5 0.3 o' Main 7.5 8.6 CAF Main 7.5 0.1 MAIN MAIN 5.0 0.0 a' Main 2.5 8.6 But it can hardly be called impressive. Can anyone see another obvious optimization, or have I just hit the ceiling because of the sheer number of function calls to isIn? I am still pretty new to haskell, and I find it hard to wrap my head around the way the compiler deals with my code. If someone has a few leads on general performance heuristics in haskell/GHC, I would be happy to read them too... thanks for your time. stijn