Simply put:
non-tail-calls allocate space and tail-calls don't allocate space.
If you have many non-tail-calls in a deep recursion you will allocate a lot (look at the report from the "time" macro to see how much) and this will cause a large garbage-collection time and even thrashing if you don't have enough physical memory. If the recursion is relatively shallow, then Gambit can manage to reclaim the frames without help from the garbage collector, so you will see little difference compared to a tail-call recursion.
So the tip is this: try to use tail-calls for deep recursions (say more than 1000 deep). Shallow recursions can be done either with tail-calls or non-tail-calls. There is a graceful degradation, so if you happen to do a non-tail-call recursion that is 10000 deep it will not be a big mistake. Gambit was designed to allow arbitrarily deep non-tail-call recursions (up to the size of your heap) which I think is the right thing to do (certainly better than the core dump that C gives). If you want to limit the depth of recursion for testing your code, you can add the -:hNNNN runtime option when you start gsi.
The declarations you mention have two effects
1) they make operations like (- n 1) faster because they are inlined
2) they partly unroll the recursion so that a few of the original recursive calls are performed per actual recursive call (due to the (inlining-limit 1000) declaration)
The second point has an impact on the size of the stack frames that are generated. They make the recursion take less total stack space than without the inlining-limit declaration. Here's an example:
original code:
(declare (not run-time-bindings) (block) (inlining-limit 1000))
(define (f n) (if (= n 0) 0 (+ 1 (f (- n 1)))))
is transformed by the inliner into:
(define (f n) (if (= n 0) 0 (+ 1 (let ((n (- n 1))) (if (= n 0) 0 (+ 1 (let ((n (- n 1))) (if (= n 0) 0 (+ 1 (let ((n (- n 1))) (if (= n 0) 0 (+ 1 (let ((n (- n 1))) (if (= n 0) 0 (+ 1 (f (- n 1)))))))))))))))))
By examining the C code generated I see that the original code allocates 4 words per stack frame. The transformed code also allocates 4 words per stack frame, but each stack frame represents 5 original recursive calls. So the transformed code takes only 20% of the stack space. This can (and in your case did) make a big difference in GC time when you are filling your memory with stack frames. I suspect that in the first case the size of the stack was 2000 MB and thus exceeded your physical memory and caused thrashing, and in the second case the stack was 400 MB and fit in physical memory with no thrashing.
Marc
On 15-Nov-05, at 1:28 AM, Bill Richter wrote:
I have a question about tail recursion, which a mathematician here explained to me over the weekend. I have a simple program gsc/gcc didn't optimize as I expected, until I used the declarations
(declare (standard-bindings) (fixnum) (not safe) (inline) (inlining-limit 1000) (block))
Prior to that, it took gsc/gcc 15 minutes to add up 50 million 1s, and as John said, the non-tail-recursive program used up way too much memory. Toward the end of the calculation, I was taking 85% of the memory of a 1GB machine, and only 4% of its 2.8 Ghz CPU:
% ps aux |grep a.out richter 22120 4.1 84.7 3143368 869084 pts/1 D+ 00:04 0:24 ./a.out
But with these magic declarations, it went down to 6 seconds. Perhaps someone can offer a tip about when it's necessary to use tail-recursion, considering Gambit's blinding speed. Code + output:
(declare (standard-bindings) (fixnum) (not safe) ; (run-time-bindings) (inline) (inlining-limit 1000) (block))
(define (sub1 x) (- x 1))
(define (addones n) (if (< n 1) 0 (+ 1 (addones (sub1 n)))))
(define (tail_addones n) (let loop ([n n] [accum 0]) (if (< n 1) accum (loop (sub1 n) (+ 1 accum)))))
(display (tail_addones 50)) (newline) (display (addones 50)) (newline) (time (display (tail_addones 5000000))) (newline) (time (display (addones 5000000)))
(time (display (tail_addones 50000000))) (newline) (time (display (addones 50000000)))
% gsc tail-john.scm % gcc -O2 -L. -I. tail-john_.c tail-john.c -lgambc % ./a.out
50 50 5000000(time (display (tail_addones 5000000))) 54 ms real time 4 ms cpu time (4 user, 0 system) no collections 152 bytes allocated 5 minor faults no major faults
5000000(time (display (addones 5000000))) 483 ms real time 281 ms cpu time (225 user, 56 system) 7 collections accounting for 205 ms real time (87 user, 20 system) 39917112 bytes allocated 8092 minor faults no major faults 50000000(time (display (tail_addones 50000000))) 137 ms real time 37 ms cpu time (37 user, 0 system) no collections 160 bytes allocated no minor faults no major faults
50000000(time (display (addones 50000000))) 5993 ms real time 2984 ms cpu time (2581 user, 403 system) 7 collections accounting for 2342 ms real time (1058 user, 181 system) 400087168 bytes allocated 84606 minor faults no major faults