jhaase wrote:
What we can see is, that:
- cps style versions are much faster than the srfi or built-in version
(especially for big inputs)
- the optimization of taking the car of the list only once is probably
also done by Ikarus (cps-partition1 and cps-partition2 take the same
time)
- full cps-style (cps-partition3) is a tiny bit slower (why?)
- reversing lists must be incredibly fast in Ikarus, because simple-
partition beats them all (are lists double-linked internally?)
- simple-partition does the least memory allocation
- simple-partition becomes relatively faster with bigger inputs
Additionally, looking at the source code of srfi-partition reveals
that it isn't tail-recursive (yuck!), so large inputs might result in
a memory overflow.
Very interesting investigation and report! Thanks!
We need Dan to write a third book, "The Little Optimizer". ;-) I.e.
after a beginner learns about recursion and higher order procedures,
learn about how to combine them in efficient ways. Of course, this
should only be taught in the context of a sophisticated compiler
otherwise the only thing they'd learn to do is manually expand things...
The reader should also be armed with a good profiler.
Exercises like this give insight into how Ikarus optimizes code and the
results are useful for tweaking the compiler (adjusting the thresholds
for inlining, for example).
Ed
