3 ms·

The other question I always had is why do we need to have a fixed limit for the stack. Why can't it grow automatically as needed, just like the heap?

by ufo 6y ago

CJefferson 6y ago
I don't know either -- I understand in 32-bit OSes, as you need continuous memory space and that can be lacking (early Rust experimented with "segmented stacks", where the stack can be split, and took it out as it was too hard to do). However, in 64-bit OSes, just set up a GB of address space for the stack and be done with it.
chriswarbo 6y ago
I think this is partly Stockholm syndrome. Having a finite stack will cut off infinite recursion before it consumes the whole memory, and infinite recursion is often an error (e.g. if we get some branching logic wrong, our base case may never be taken). Over time this has become self-reinforcing: - Recursive algorithms may hit stack limits, which makes them less attractive, so programmers are less likely to choose them - Error rates presumably remain pretty constant, so this avoidance decreases the proportion of recursive programs that are deliberately so, and increases the proportion of recursive programs that are accidentally so - Stack limits remain justified, due to how rarely programmers are choosing recursive approaches, and how often stack overflows help us to stop buggy programs I don't think the 'stops buggy programs' argument is particularly compelling, since that could apply to pretty much any restriction (e.g. we could limit RAM usage to 64K to prevent buggy programms allocating too much, those which want more can edit files in a tempfs; processes should run for no longer than 1 minute, to stop buggy programs, those which need more time can spawn children; etc.). I appreciate that low-level languages are operating under some pretty tight constraints (both in what's available to them, and the performance their users expect). What I find very strange is how many high-level scripting languages impose such stack limits, and don't even eliminate tail-calls. The raison d'etre for such languages is to be more ergonomic and powerful than bare-metal languages, and they don't mind sacrificing a lot of performance to do so (using interpreters, boxed values, dynamic dispatch, etc.); yet they're somehow fine with inheriting these weird restrictions from C & co.?
- Someone 6y ago
  “we could limit RAM usage to 64K to prevent buggy programms allocating too much, those which want more can edit files in a tempfs; processes should run for no longer than 1 minute” In JCL (https://en.wikipedia.org/wiki/Job_Control_Language https://en.wikipedia.org/wiki/Job_Control_Language), you can specify how much CPU time a program can spend, how many pages it can output before the OS kills it, and have to specify what files it reads and writes. That was useful at a time when CPU time, memory and disk space were scarce and expensive, and still would be useful when sandboxing untrusted code.
  - chriswarbo 6y ago
    > you can specify It's nice to have the option of specifying such limits, but not all programs are batch jobs. For example, the correct CPU time cap for a HTTP server is infinity. Likewise, if that server were written as a recursive function then the correct stack size would be infinity: def serve(request): response = process(request) socket.send(response) serve(socket.receive())
- ufo 6y ago
  > I don't think the 'stops buggy programs' argument is particularly compelling, since that could apply to pretty much any restriction This is the part that irks me the most. If I have an algorithm that is neatly written as a recursive algorithm and mechanically rewrite it to use an explicit stack, that doesn't change the fact that an infinite loop is still a bug. It's just that it's going to manifest as the process using all the available RAM instead of as a stack overflow. > yet they're somehow fine with inheriting these weird restrictions from C & co.? Sometimes that's because the interpreter itself uses recursion. That can be convenient for whoever is implementing the interpreter, at the cost of inheriting the stack limit from C. That said, there are also languages that enforce a recursion limit even when they don't use the C stack at all. In which case I ask the exact same question as you do.
- recursivecaveat 6y ago
  I tend to think of it as a handy feature of recursive algorithms that encourages me to use them. Just twice in my life have I wanted to exceed the default stack size in Python, but many times have my programs crashed with a helpful stack trace when they would otherwise have locked up in an infinite loop. I do however work in a subfield where it's pretty acceptable to just say "yaaa, don't do that" to unbounded input sizes, so ymmv.

The other question I always had is why do we need to have a fixed limit for the stack. Why can't it grow automatically as needed, just like the heap?

by ufo 6y ago

The other question I always had is why do we need to have a fixed limit for the stack. Why can't it grow automatically as needed, just like the heap?

CJefferson 6y ago

I don't know either -- I understand in 32-bit OSes, as you need continuous memory space and that can be lacking (early Rust experimented with "segmented stacks", where the stack can be split, and took it out as it was too hard to do). However, in 64-bit OSes, just set up a GB of address space for the stack and be done with it.

chriswarbo 6y ago

I think this is partly Stockholm syndrome. Having a finite stack will cut off infinite recursion before it consumes the whole memory, and infinite recursion is often an error (e.g. if we get some branching logic wrong, our base case may never be taken). Over time this has become self-reinforcing: - Recursive algorithms may hit stack limits, which makes them less attractive, so programmers are less likely to choose them - Error rates presumably remain pretty constant, so this avoidance decreases the proportion of recursive programs that are deliberately so, and increases the proportion of recursive programs that are accidentally so - Stack limits remain justified, due to how rarely programmers are choosing recursive approaches, and how often stack overflows help us to stop buggy programs I don't think the 'stops buggy programs' argument is particularly compelling, since that could apply to pretty much any restriction (e.g. we could limit RAM usage to 64K to prevent buggy programms allocating too much, those which want more can edit files in a tempfs; processes should run for no longer than 1 minute, to stop buggy programs, those which need more time can spawn children; etc.). I appreciate that low-level languages are operating under some pretty tight constraints (both in what's available to them, and the performance their users expect). What I find very strange is how many high-level scripting languages impose such stack limits, and don't even eliminate tail-calls. The raison d'etre for such languages is to be more ergonomic and powerful than bare-metal languages, and they don't mind sacrificing a lot of performance to do so (using interpreters, boxed values, dynamic dispatch, etc.); yet they're somehow fine with inheriting these weird restrictions from C & co.?

Someone 6y ago
“we could limit RAM usage to 64K to prevent buggy programms allocating too much, those which want more can edit files in a tempfs; processes should run for no longer than 1 minute” In JCL (https://en.wikipedia.org/wiki/Job_Control_Language https://en.wikipedia.org/wiki/Job_Control_Language), you can specify how much CPU time a program can spend, how many pages it can output before the OS kills it, and have to specify what files it reads and writes. That was useful at a time when CPU time, memory and disk space were scarce and expensive, and still would be useful when sandboxing untrusted code.
- chriswarbo 6y ago
  > you can specify It's nice to have the option of specifying such limits, but not all programs are batch jobs. For example, the correct CPU time cap for a HTTP server is infinity. Likewise, if that server were written as a recursive function then the correct stack size would be infinity: def serve(request): response = process(request) socket.send(response) serve(socket.receive())
ufo 6y ago
> I don't think the 'stops buggy programs' argument is particularly compelling, since that could apply to pretty much any restriction This is the part that irks me the most. If I have an algorithm that is neatly written as a recursive algorithm and mechanically rewrite it to use an explicit stack, that doesn't change the fact that an infinite loop is still a bug. It's just that it's going to manifest as the process using all the available RAM instead of as a stack overflow. > yet they're somehow fine with inheriting these weird restrictions from C & co.? Sometimes that's because the interpreter itself uses recursion. That can be convenient for whoever is implementing the interpreter, at the cost of inheriting the stack limit from C. That said, there are also languages that enforce a recursion limit even when they don't use the C stack at all. In which case I ask the exact same question as you do.
recursivecaveat 6y ago
I tend to think of it as a handy feature of recursive algorithms that encourages me to use them. Just twice in my life have I wanted to exceed the default stack size in Python, but many times have my programs crashed with a helpful stack trace when they would otherwise have locked up in an infinite loop. I do however work in a subfield where it's pretty acceptable to just say "yaaa, don't do that" to unbounded input sizes, so ymmv.