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

Christian christian at pflanze.mine.nu
Tue Dec 6 06:53:26 EST 2005


Hello Bill

You did address Marc, but I think I can reply something to your 
questions as well.

At 0:51 Uhr -0600 05.12.2005, Bill Richter wrote:
>    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.
>
>Marc, I finally realized you gave me a tip, and tried to debug my
>program accordingly.  So I set a maximum heap size of 100MB:
>
>export GAMBCOPT=d-,h100000
>
>  % gsi Curtis-algorithm &
>  % fg
>*** ERROR IN ##make-vector -- Heap overflow
>
>  %  gsc Curtis-algorithm
>  %  gcc -O2 -L. -I. Curtis-algorithm.c Curtis-algorithm_.c -lgambc
>  %  ./a.out &
>*** ERROR IN Poly->Tree -- Heap overflow
>
>Can I get the debugger to tell me what's happening when it crashes
>here?

If you run code from the repl (start gsc without arguments), using 
compile-file and load, like (compile-file "Curtis-algorithm" 
'(debug)) (load "Curtis-algorithm")
then when running out of memory the debugger is entered.

(I haven't used batch compilation for such a long time that I don't 
remember if the resulting executables should enter the debugger as 
well.)

>Note I get 2 different answers, and the compiled answer makes
>more sense to me:

Might just be coincidence. To see the place in your code where it 
happens, enter ",b" in the debugger. (Read the fine manual!)

>  I'm trying to build a huge tree.  It's a dumb
>question, because if I thought about my code, I might figure something
>out.

Well, what is your question then? Maybe you want single step your 
code: use the interpreter, switch tail-call optimization off (read 
about proper-tail-calls-set! in the manual), then insert (step) 
statements into your code (or before running it from the repl).

>Also, I have no idea how to relate the recursion depth to the
>heap size, but 100MB is 5% of the available memory (2 GB).

What does "available memory" mean? Hardware RAM, or a resource limit 
enforced by your OS? That's probably irrelevant anyway if you set a 
heap limit using gambit options. What's your question? If you want to 
know how much memory a particular recursion depth takes, why not 
insert a recursion depth count in your code and stop recursion at a 
particular depth to let you see at memory usage, or regularly print 
the current depth?

You probably took Marc Feeley's reply literally ("If you want to 
limit the depth of recursion for testing your code, you can add the 
-:hNNNN option"), but this option limits the heap size, not the 
recursion depth per se (read the help, gsc -:h), and since recursion 
is only limited by the heap size, this of course also limits 
recursion depth.

>BTW both gsi & gcc crash at the same place:

(I don't understand anything in the following output.)

Christian.



More information about the Gambit-list mailing list