[gambit-list] Re: simple unoptimized gsc nontail recursion
Bill Richter
richter at math.northwestern.edu
Mon Dec 5 01:51:20 EST 2005
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? Note I get 2 different answers, and the compiled answer makes
more sense to me: 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. 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).
BTW both gsi & gcc crash at the same place:
% tail -40 Min_t-Max_t-BZ ; ps aux | grep [.]out
((23 11 12 4 5 3 3 3) (25 17 3 6 6 5 3))
((25 3 5 9 3 5 7 7) (35 12 4 5 3 3 3))
((27 3 5 7 3 5 7 7) (29 5 9 3 5 7 7))
((27 7 12 4 5 3 3 3) (28 13 2 3 5 7 7))
((31 5 5 3 6 6 5 3) (33 9 3 6 6 5 3))
((33 21 1 2 4 1 1 1) (34 22 2 4 1 1 1))
((41 13 1 2 4 1 1 1) (49 1 2 4 3 3 3))
((47 1 1 2 4 3 3 3) (48 2 2 4 3 3 3))
((49 5 1 2 4 1 1 1) (50 6 2 4 1 1 1))
((53 1 1 2 4 1 1 1) (54 2 2 4 1 1 1)))
(Z 8 72
(5 10 8 9 11 7 7 7)
(10 20 5 7 3 5 7 7)
(17 9 3 5 9 7 7 7))
(B 9 72
((1 1 2 4 7 7 11 15 15) (4 5 3 4 7 11 15 15))
((1 2 4 3 5 7 11 15 15) (2 3 6 5 7 11 15 15))
((2 4 5 5 7 11 15 7 7) (4 8 5 7 11 15 7 7))
((3 4 4 5 7 11 15 7 7) (4 5 10 9 15 7 7 7))
((3 5 1 2 4 7 11 15 15) (4 6 2 4 7 11 15 15))
((3 6 4 5 9 15 7 7 7) (4 7 8 9 15 7 7 7))
((5 9 11 8 12 9 3 3 3) (6 11 12 5 9 7 7 7))
((7 9 9 3 5 9 7 7 7) (9 17 3 5 9 7 7 7))
((9 13 11 12 4 5 3 3 3) (16 8 5 5 9 7 7 7))
((11 6 8 3 5 9 7 7 7) (12 8 7 14 4 5 7 7))
((12 3 5 10 11 3 5 7 7) (18 8 3 5 9 7 7 7))
((15 4 6 3 5 9 7 7 7) (16 5 10 11 3 5 7 7))
((15 25 13 1 2 4 1 1 1) (16 28 2 4 5 3 3 3))
((17 11 6 5 2 3 5 7 7) (18 14 9 3 6 6 5 3))
((21 9 5 5 3 6 6 5 3) (22 10 9 3 6 6 5 3))
((23 5 6 5 2 3 5 7 7) (29 6 5 2 3 5 7 7))
((25 3 6 5 2 3 5 7 7) (26 6 9 3 6 6 5 3))
((29 5 6 2 3 5 7 3 3) (35 6 2 3 5 7 3 3))
((31 3 6 2 3 5 7 3 3) (32 6 3 3 6 6 5 3))
((33 7 13 1 2 4 1 1 1) (34 10 2 4 5 3 3 3))
((37 4 2 2 4 5 3 3 3) (38 6 2 4 5 3 3 3))
((46 1 2 3 4 4 1 1 1) (48 2 3 4 4 1 1 1)))
More information about the Gambit-list
mailing list