[Haskell-cafe] performance question

[Stijn De Saeger]

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