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.
| Function | ghc | ghc -O2 | ||
|---|---|---|---|---|
myPowerLinear | 1 | * | 160 | * |
myPowerLog | ∼∞ | ∼∞ | ||
myPowerTail | 4 | * | 1000 | |
myPowerTailStrict | 60 | 1000 | ||
myPowerFoldr | <1 | * | 1150 | |
myPowerFoldl | 4 | * | 350 | |
myPowerFoldl' | 175 | 350 | ||
* indicates runs that required increased stack size.
As an aside: myPowerTail with 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
foldr/foldlfast/slow. - Recursion can be very fast.