6 ms·

There is a difference between "running out of stack memory" and "running out of memory used to store stack-structured data". Any recursive algorithm can be mec

There is a difference between "running out of stack memory" and "running out of memory used to store stack-structured data". Any recursive algorithm can be mechanically transformed into an equivalent iterative algorithm that uses only a single activation record on the system call stack. If you perform that transformation on an entire program, then the total depth of the call stack is a static property of the call graph in the source code, and it does not depend in any way on run-time inputs from the outside world. The only way to run out of stack space then would be to write a program whose static, constant stack space requirements are indeed too large for the machine it is run on. Transformed algorithms may, of course, require "manually" tracking data in a stack structure, and use of such a data structure may indeed result of running out of memory depending on what inputs are provided, but that's just "running out of memory, which we happened to be using to hold a stack-like data structure", not "running out of stack".

wizeman 6y ago
To me it just seems that you're arguing semantics... I mean, what is the difference between "stack memory" and "heap memory allocated to store the stack", other than the fact that the OS preallocates the first one for you by default? To me, "the stack" and "a stack-like data structure stored in the heap that is used as a stack to replace what would otherwise be the stack" is functionally the same thing... You know that (given appropriate conditions) you can just allocate stack frames wherever you want and point your stack pointer to whatever you want, whenever you want, right? This is what the Go compiler does to prevent Go programs from running out of the stack space provided by the OS by default. But AFAIK they don't advertise that Go programs use constant stack space and you don't have to worry about out-of-stack issues... So as far as I understand, there is no transformation that would make any recursive program use "constant stack space", unless of course, you just use some other memory to store what you'd store on your stack (but then again, that doesn't mean your stack has constant space, it just means that you're not using the default OS-provided stack space as a stack, and you're using other memory as a stack instead). Apart from that, as I said before, even if you had "constant stack space" it does not mean that you won't have out-of-stack issues.
- gliese1337 6y ago
  To me it just seems that you're arguing semantics... The most important type of argument to have. If you don't agree on semantics, no other discussion is worth having, as you will never know if the other party actually agrees with you or not. I mean, what is the difference between "stack memory" and "heap memory allocated to store the stack", other than the fact that the OS preallocates the first one for you by default? That is a pretty major difference with wide-ranging effects on program performance right there. To me, "the stack" and "a stack-like data structure stored in the heap that is used as a stack to replace what would otherwise be the stack" is functionally the same thing... System-level error messages and memory managers both disagree. You know that (given appropriate conditions) you can just allocate stack frames wherever you want and point your stack pointer to whatever you want, whenever you want, right? Yes. And once you do, that memory becomes functionally privileged from the perspective of your allocation strategy. This is what the Go compiler does to prevent Go programs from running out of the stack space provided by the OS by default. But AFAIK they don't advertise that Go programs use constant stack space and you don't have to worry about out-of-stack issues... Of course not. Because they actually use that space as stack space, to store function activation records.
  - wizeman 6y ago
    > That is a pretty major difference with wide-ranging effects on program performance right there. It really isn't. The only difference is that in the second case you have to call mmap() at the beginning of your program to allocate stack space and then change the stack pointer to point to it, the rest of the execution would remain the same. > That is a pretty major difference with wide-ranging effects on program performance right there. > And once you do, that memory becomes functionally privileged from the perspective of your allocation strategy. So you're saying that the transformation you mentioned gives you better error messages at the expense of performance, because now instead of using the stack, you have to keep allocating a stack-like structure on the heap? If so, that's not entirely true, as you can have the same error messages without doing this transformation (that's why some kernels and runtimes can detect stack overflow and even resize the stack), so the only observable functional difference is that you replace a simple stack-like allocation mechanism with one that is slower without much benefit. And it would still be a bit disingenuous to say that the transformation would make your program use constant stack space, as if replacing stack space with heap space somehow makes stack usage on a recursive function irrelevant...
deleted 6y ago
[deleted]

wizeman 6y ago

To me it just seems that you're arguing semantics... I mean, what is the difference between "stack memory" and "heap memory allocated to store the stack", other than the fact that the OS preallocates the first one for you by default? To me, "the stack" and "a stack-like data structure stored in the heap that is used as a stack to replace what would otherwise be the stack" is functionally the same thing... You know that (given appropriate conditions) you can just allocate stack frames wherever you want and point your stack pointer to whatever you want, whenever you want, right? This is what the Go compiler does to prevent Go programs from running out of the stack space provided by the OS by default. But AFAIK they don't advertise that Go programs use constant stack space and you don't have to worry about out-of-stack issues... So as far as I understand, there is no transformation that would make any recursive program use "constant stack space", unless of course, you just use some other memory to store what you'd store on your stack (but then again, that doesn't mean your stack has constant space, it just means that you're not using the default OS-provided stack space as a stack, and you're using other memory as a stack instead). Apart from that, as I said before, even if you had "constant stack space" it does not mean that you won't have out-of-stack issues.

gliese1337 6y ago
To me it just seems that you're arguing semantics... The most important type of argument to have. If you don't agree on semantics, no other discussion is worth having, as you will never know if the other party actually agrees with you or not. I mean, what is the difference between "stack memory" and "heap memory allocated to store the stack", other than the fact that the OS preallocates the first one for you by default? That is a pretty major difference with wide-ranging effects on program performance right there. To me, "the stack" and "a stack-like data structure stored in the heap that is used as a stack to replace what would otherwise be the stack" is functionally the same thing... System-level error messages and memory managers both disagree. You know that (given appropriate conditions) you can just allocate stack frames wherever you want and point your stack pointer to whatever you want, whenever you want, right? Yes. And once you do, that memory becomes functionally privileged from the perspective of your allocation strategy. This is what the Go compiler does to prevent Go programs from running out of the stack space provided by the OS by default. But AFAIK they don't advertise that Go programs use constant stack space and you don't have to worry about out-of-stack issues... Of course not. Because they actually use that space as stack space, to store function activation records.
- wizeman 6y ago
  > That is a pretty major difference with wide-ranging effects on program performance right there. It really isn't. The only difference is that in the second case you have to call mmap() at the beginning of your program to allocate stack space and then change the stack pointer to point to it, the rest of the execution would remain the same. > That is a pretty major difference with wide-ranging effects on program performance right there. > And once you do, that memory becomes functionally privileged from the perspective of your allocation strategy. So you're saying that the transformation you mentioned gives you better error messages at the expense of performance, because now instead of using the stack, you have to keep allocating a stack-like structure on the heap? If so, that's not entirely true, as you can have the same error messages without doing this transformation (that's why some kernels and runtimes can detect stack overflow and even resize the stack), so the only observable functional difference is that you replace a simple stack-like allocation mechanism with one that is slower without much benefit. And it would still be a bit disingenuous to say that the transformation would make your program use constant stack space, as if replacing stack space with heap space somehow makes stack usage on a recursive function irrelevant...

deleted 6y ago

[deleted]