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

Marc Feeley feeley at iro.umontreal.ca
Tue Nov 15 10:10:32 EST 2005


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




More information about the Gambit-list mailing list