Re: [Chicken-users] Unbounded stack growth

[Alex Shinn]

On Thu, Jul 12, 2012 at 10:52 AM, Marc Feeley <address@hidden> wrote:
>
> On 2012-07-11, at 5:59 PM, Felix wrote:
>
>>>
>>> Performance should not trump safety and correctness.
>>
>> Absolutely right, yet everybody has a different perception of what
>> performance, safety and correctness means. Segfaulting on
>> _stack-overflow_ is not something that I'd call "incorrect" or "unsafe"
>> - I'd call it "inconvenient" and it may be the case that handling the
>> overflow gracefully isn't such a big deal at all. On the other hand,
>> an extremely deep recursion could in such a case (stack checks
>> everywhere) bring the machine to a halt due to excessive thrashing.  I
>> don't know whether I'd perhaps prefer the segfault in such a situation...
>
> The point is that, in a high-level language, a segfault represents a loss of 
> control of the language implementation.  On unix systems, it is usually 
> caused by a protected virtual memory page that has been touched, and a 
> segfault signal is generated.  Not very informative, but not a big safety 
> issue.  On other operating systems (e.g. in a Nintendo DS, a FPGA, or a 
> toaster), some unrelated zone of memory (say the heap containing Scheme 
> objects) has been corrupted silently and the program has started executing 
> random stuff, possibly burning your toast and setting fire to the house.
>
> The programmer already has control (with the csc -heap-limit N option) over 
> how much memory is available to the program to avoid thrashing caused by an 
> infinite recursion, or an allocation loop gone wild.  There should be no 
> difference in heap and stack allocation.  These are implementation terms.  It 
> is all just memory.  After all, the Cheney on the MTA approach was designed 
> to migrate the stack frames to the heap transparently, so the user should be 
> isolated from the concern of where the continuation is stored.

I disagree - I think a stack grown too large is likely indicative
of a programming error, or at the very least an inefficient
algorithm.  In the general case I want my programs to be
able to allocate as much heap as possible, but have a
separate limitation on the stack.

The default Chibi stack is only 1k.  It can grow, but again to
a limit of only 1M (by default).  This coincidentally causes
it to also return #t on the 200,000 input to even and raise
an "out of stack" error on 300,000 (with a ridiculously long
stack trace making me wonder if 1M is too large).

-- 
Alex

>
> What is unfortunate with this bug is that it goes against the programmer's 
> intuition.  If you slightly modify the code to this :
>
> ;; File: even.scm
>
> (define (even i n)
>   (if (= 0 (modulo i 100000)) (print i))
>   (if (= i n)
>       #t
>       (not (even (+ i 1) n))))
>
> (print (even 0 (string->number (car (command-line-arguments)))))
>
> So that it is easy to see how deep in the recursion the program has gone, 
> then you get this output :
>
> % ./even 900000
> 0
> 100000
> 200000
> 300000
> 400000
> 500000
> 600000
> 700000
> 800000
> 900000
> Segmentation fault: 11
> % ./even 300000
> 0
> 100000
> 200000
> 300000
> Segmentation fault: 11
>
> This shows that the stack overflow is occuring during the unwinding phase of 
> the recursion.  This is quite unintuitive for me.  Try explaining to a 
> beginner that the unwinding of the recursion is causing memory allocation!  
> Moreover, if you slightly modify the code so that there is a call to the 
> my-not function instead of the builtin not, then there are no problems 
> (because the call to my-not at each step of the unwinding is going to 
> gracefully handle the growing C stack and garbage collect it):
>
> ;; File: even.scm (slightly modified)
>
> (define (my-not x) (not x))
>
> (define (even i n)
>   (if (= 0 (modulo i 100000)) (print i))
>   (if (= i n)
>       #t
>       (my-not (even (+ i 1) n))))
>
> (print (even 0 (string->number (car (command-line-arguments)))))
>
> % ./even 900000
> 0
> 100000
> 200000
> 300000
> 400000
> 500000
> 600000
> 700000
> 800000
> 900000
> #t
>
> The decision for not testing the stack limit on returns is based on a 
> performance concern.  Adding this test at return points would allow the above 
> code to work correctly, for very large values of n.
>
> By the way, I'm surprised that the very similar looking code for rev-iota :
>
> (define (rev-iota n)
>   (if (= n 0)
>       '()
>       (cons n (rev-iota (- n 1)))))
>
> does not trigger the bug.  Is "cons" treated differently from "not"?
>
> Marc
>
>
> _______________________________________________
> Chicken-users mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/chicken-users