[Haskell-cafe] Profiling nested case

Max Bolingbroke batterseapower at hotmail.com
Fri Jul 11 21:33:00 EDT 2008


> It is somehow award that passing function as an argument slow down the
> program so much. Is not Haskell a functional language and this such
> (functional) code reuse is one of its main points?

I can think of a few reasons why function passing is slow:
* There is an overhead to closure creation (I don't know how big this
is in practice, but it can be significant)
* GHC has little information about what function-typed variables mean,
because the function they are bound to is not known until runtime.
This precludes the use of inlining, rewrite rules etc, which are
absolutely key factors in making Haskell fast

Regarding your first example: currently GHC does not do loop
unrolling. It probably should though because loop unrolling reduces
braches and increases the amount of information about the execution
path that is available statically (as in e.g. the case liberation
transformation), which probably explains the increased performance you
saw by doing it manually in your first email.  Earlier this year I
implemented something somewhat similar though: fusable list literals.
In this example from your first email:

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

If findColor had been a function defined in terms of foldr rather than
using explicit recursion, then theres a good chance GHC 6.9 would have
fused it with the list to yield your optimized, loop unrolled,
version:

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

Incidentally, if in your most recent email castRayScene2 was your only
used of castRay, GHC would have inlined the whole definition into that
use site and you would have got castRayScene1 back again.

So, GHC does try its best to make higher order functions fast :-). But
it's quite tricky!

All the best,
Max


More information about the Haskell-Cafe mailing list