What follows are some (very simplistic) speed measurements of some simple recursive functions that calculate powers in Haskell. This is not a meaningful benchmark, but it's interesting anyway.
These are results on my system, compiling the code with
ghc --make power.hs (version 6.12.3, adding
-O2 for the second column).
The runs were actually done with the command
time ./power, adding
+RTS -K100m to increase the stack size when necessary.
* indicates runs that required increased stack size.
As an aside:
ghc -O2 takes just about the same time as an iterative C version compiled with
gcc -O0. Compiling with
gcc -O2 is much faster again (possibly due to using registers for the calculations instead of storing results in memory?).
There are a few lessons here:
- Good algorithms will usually beat good “optimization”.
- In the (perhaps rare) situation where managing the callback stack is the part taking the time, tail recursion gives a significant speedup.
- The GHC optimizer is pretty good.
- I don't understand what makes
- Recursion can be very fast.