[Haskell-cafe] Profiling nested case

[Mitar]

Hi!

I am making a simple raycasting engine and have a function which take
a point in space and return a color of an object (if there is any) at
this point in space.

And because the whole thing is really slow (or was really slow) on
simple examples I decided to profile it. It takes around 60 seconds
for a 640x480 px image with 400 depth of field. This is at worst
122,880,000 calculations (if the scene is rather empty) of a
coordinate of a point in space and then checking for a color. And 60
seconds look really a lot to me for that.

So I went profiling and found out that the strange part of code is the
main color checking function which has a list of objects (at this time
the list is hardcoded). It looks like this:

world :: SpacePoint -> VoxelColor
world point = case msum . sequence elements $ point of
                Just v  -> v
                Nothing -> noColor
  where elements = [redSphere (0,50,0) 50, greenSphere (25,-50,0) 50,
blueSphere (-150,0,150) 50]

So three spheres in a world and I check if the point is in any of
them. Like that:

sphere :: SpacePoint -> BasicReal -> VoxelColor -> WorldElement --
center of sphere, it's radius, it's color
sphere (x0,y0,z0) r color (x,y,z)
  | x' * x' + y' * y' + z' * z' <= r * r = Just color
  | otherwise                            = Nothing
    where x' = x - x0
          y' = y - y0
          z' = z - z0

redSphere :: SpacePoint -> BasicReal -> WorldElement
redSphere c r = sphere c r redColor

So profiling told me that world function takes 38.4 % of all running
time. So I decided to play with it. Maybe a more direct approach would
be better:

world :: SpacePoint -> VoxelColor
world point = findColor [redSphere (0,50,0) 50, greenSphere (25,-50,0)
50, blueSphere (-150,0,150) 50]
  where findColor []     = noColor
        findColor (f:fs) = case f point of
                            Just v  -> v
                            Nothing -> findColor fs

Great, it improved. To 40 s. But still it was too much. I tried this:

world :: SpacePoint -> VoxelColor
world point = case redSphere (0,50,0) 50 point of
                Just v  -> v
                Nothing -> case greenSphere (25,-50,0) 50 point of
                             Just v  -> v
                             Nothing -> case blueSphere (-150,0,150) 50 point of
                                          Just v  -> v
                                          Nothing -> noColor

And it took 15 s. And also the profiling was like I would anticipate.
Calculating points coordinates and checking spheres takes almost all
time.

So any suggestions how could I build a list of objects to check at
runtime and still have this third performance? Why this big
difference?

(I am using GHC 6.8.3 with -O2 compile switch.)

(The <* operator is casting a ray, that is multiplying a ray direction
vector with a scalar factor.)


Mitar
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Main-case.prof
Type: application/octet-stream
Size: 6535 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20080710/7a21c7c1/Main-case.obj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Main-rec.prof
Type: application/octet-stream
Size: 6536 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20080710/7a21c7c1/Main-rec.obj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Main-seq.prof
Type: application/octet-stream
Size: 6414 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20080710/7a21c7c1/Main-seq.obj