[gambit-list] Re: simple unoptimized gsc nontail recursion

Christian christian at pflanze.mine.nu
Wed Dec 7 02:28:43 EST 2005


At 0:46 Uhr -0600 07.12.2005, Bill Richter wrote:
>so I posted a question which Marc answered: gsc/gcc will *not* optimize
>away all possible tail recursion problems!  Don't let the recursion
>depth get above 1000 or 10000!

I think he said, if the depth of *non*-tail recursion (i.e. real 
recursion, not iteration) goes above ~10000 it will start to allocate 
call frames on the heap and thus get slower. Regarding tail calls, to 
my knowledge, Gambit always handles them correctly (unless if you 
intentionally switch off proper-tail-calls (only effective in the 
interpreter) of course).

(He also said, that if you declare a big inlining-limit, the compiler 
will partly unroll the recursion code and running it will thus 
allocate less space for the call frames, which might have had an 
effect on the speed of your first attempt.)

>Curtis-alg builds a huge tree, and the functions used, merge-tree &
>Poly->Tree, don't look tail recursive to me!  I'll fiddle with this...
>
>
>Here's my debugger output, modeled on the informative example in the
>node "Debugging commands":
>
>
>>  ,i
>#<procedure #2 Poly->Tree> =
>(lambda (X)
>   (let ((n-terms (lambda (n S) (list n (Poly->Tree S)))))
>     (if (empty? X)
>         empty
>         (let* ((x (first X)) (n (Mono-first x)) (y (Mono-rest x)))
>           (if (Mono-1? y)
>               X
>               (let loop ((n n) (S_n (list y)) (X (rest X)))
>                 (if (Poly-0? X)
>                     (list (n-terms n (reverse S_n)))
>                     (let* ((x (first X)) (m (Mono-first x)) (y (Mono-rest x)))
>                       (if (= n m)
>                           (loop n (cons y S_n) (rest X))

this (true) part of the if form is a tail call..

>                           (cons (n-terms n (reverse S_n))
>                                 (loop m (list y) (rest X))))))))))))

.. whereas this (false) part is not. To be able to return the result 
of cons, it first needs to run (loop ...), so it cannot eliminate the 
current continuation frame. So using "loop" as name in your named let 
looks misleading as it's not an iteration.

I don't have the time to delve into the code or algorithm you're using.

Maybe I can give some other quick help:

- I think some algorithms really need recursion (and I think especially trees)
- sometimes, mutation can replace recursion: for example, you can 
copy a list by using iteration and appending list elements to the 
tail of the new list using set-cdr!.
- sometimes you can replace recursion with an iterative calculation 
and a second calculation afterwards: e.g. you can copy a list using 
iteration and without mutation by reversing it two times, the 
reversion being the iteration (reverse (reverse lis)). But that only 
moves from using call frames to using cons cells, so only makes a 
small linear difference if at all.

Maybe you could reorganize your problem to only need part of the tree 
in memory? Maybe using lazy evaluation (using streams) helps? (I 
can't say without looking at the problem in detail)

Christian.



More information about the Gambit-list mailing list