[plt-scheme] tree-recursion vs explicit stack tail-recursive

You may wish to read this article:

http://hdl.handle.net/1721.1/6622
Garbage Collection is Fast, But a Stack is Faster

Don't be mislead by the fact that they include details of specific
architectures.
The main point is that explicit stack management requires more
work (in particular, linking the frame-list together) than using a `real'
stack.

On the other hand  Matthew said:
> If your computation has a continuation, let the runtime system
> represent it. Your program will be easier to write and read in direct
> style.

The clarity of the program is *far* more important than whether the
particular Scheme implementation performs better or worse with
one strategy or the other.  You should only care if

  a) you have actually *measured* the code in real-life use and
      found that there is a *noticeable* problem.

  b) you are a serious interpreter or compiler implementor and
      are trying to push the performance for everyone.  Even then,
      you should be measuring.

A good 80-90% of the time, performance at this level simply
does not matter.  Even Matthew's example:

--------
(define (count/tail l)
   (let loop ([l l][accum 0])
     (if (null? l)
         accum
         (loop (cdr l) (add1 accum)))))

is 10 times faster than a direct version

 (define (count l)
   (if (null? l)
       0
       (+ 1 (count (cdr l)))))
--------

If your code is not spending at least 10% of its time counting
the elements in a list, you will not see a noticeable improvement
by switching to the faster implementation.  PROFILE THE CODE FIRST.

In real life I *did* find a program that was spending an inordinate
amount of time counting the elements in a list --- a good 20%!
The performance dramatically improved not because I improved the
implementation of LENGTH, but because I changed stupid calls
like  (= (length x) 1)  into (null? (cdr x)).



-- 
~jrm