[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Chicken-users] Unbounded stack growth
From: |
Alex Shinn |
Subject: |
Re: [Chicken-users] Unbounded stack growth |
Date: |
Thu, 12 Jul 2012 11:25:44 +0900 |
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
- [Chicken-users] Unbounded stack growth, Marc Feeley, 2012/07/11
- Re: [Chicken-users] Unbounded stack growth, John Cowan, 2012/07/11
- Re: [Chicken-users] Unbounded stack growth, Marc Feeley, 2012/07/11
- Re: [Chicken-users] Unbounded stack growth, Felix, 2012/07/11
- Re: [Chicken-users] Unbounded stack growth, Marc Feeley, 2012/07/11
- Re: [Chicken-users] Unbounded stack growth,
Alex Shinn <=
- Re: [Chicken-users] Unbounded stack growth, Matthew Flatt, 2012/07/11
- Re: [Chicken-users] Unbounded stack growth, John Cowan, 2012/07/11
- Re: [Chicken-users] Unbounded stack growth, Alex Shinn, 2012/07/11
- Re: [Chicken-users] Unbounded stack growth, cjtenny, 2012/07/12
- Re: [Chicken-users] Unbounded stack growth, Alex Queiroz, 2012/07/12
- Re: [Chicken-users] Unbounded stack growth, Alex Shinn, 2012/07/12
- Re: [Chicken-users] Unbounded stack growth, Alex Queiroz, 2012/07/12
- Re: [Chicken-users] Unbounded stack growth, Alex Shinn, 2012/07/12
Re: [Chicken-users] Unbounded stack growth, Marc Feeley, 2012/07/11
Re: [Chicken-users] Unbounded stack growth, Shiro Kawai, 2012/07/11