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.