3 ms·

> would it really cost that much (as until the memory was touched it wouldn't really be allocated). The problem here is that once it is used once it is never f

> would it really cost that much (as until the memory was touched it wouldn't really be allocated). The problem here is that once it is used once it is never freed. (Other than being swapped out). So you effectively cache all of the space your program needs forever. There are some solutions like trying to mark the stack below you freeable but it is hard to do this in a way that doesn't cause huge performance concerns if you happen to be crossing whatever boundary is picked often. IIRC Golang used to do this but switched to copying, growable stacks because no matter how hard they tried they always ended up in scenarios where they were allocating and deallocating stacks in a hot loop.

owl57 5y ago
> IIRC Golang used to do this but switched to copying, growable stacks because no matter how hard they tried they always ended up in scenarios where they were allocating and deallocating stacks in a hot loop. They used to do segmented stacks. The bad overhead is not in allocation, but in switching between segments when stack pointer is oscillating around the boundary — but if you want to allocate really many stacks that could grow large, you don't have much choice: either this or tracking pointers that need to be updated on reallocation. Normal contiguously mapped stack, but with dynamic growing and shrinking of actually mapped pages, is an entirely different proposition.
- Dylan16807 5y ago
  Ah, that makes more sense, since you could easily limit stack deallocation to once a second or whatever.
- kragen 5y ago
  In an implementation of a language that can't take the address of a local variable, you can move some stack frames to the new segment when you switch segments, 256 bytes or so. Then, to oscillate around the boundary, you need to return enough times to deallocate those 256 bytes. This will cost enough to swamp the cost of switching segments. (If you can take the address of a local variable, but you have garbage collection and can handle memory allocation failures by exiting, you can heap-allocate whatever local variables have their address taken.) Segmented stacks are a particularly efficient way to implement call/cc.
LeifCarrotson 5y ago
> So you effectively cache all of the space your program needs forever. All the space your program uses at the largest stack size, you mean, which is different. Until you touch it, the huge stack is purely virtual. And it only lasts until you restart the program. Yes, if you default to a 10 GB stack, then recursively tree-search over 9 GB of data, then close the data and spend the next week with 1 MB data that only touches the bottom of the stack, you'll have 8.999 GB swapped out, which does suck. But that only happens if you run the program on that 9 GB of data. The alternative was to fault when you overflowed the smaller stack when that data was imported. It does mean if there's an infinite recursion bug, instead of crashing quickly with a stack overflow, you have to wait while it pages out other programs and fills the whole 10 GB of stack...
- kevincox 5y ago
  Yes, that is basically what I mean. If you are going to use a very large amount of stack space you should consider alternatively allocating something on the heap and freeing it afterwards. Yes, if most of your program is using roughly the same amout of stack space then it is great. However I think if you are worried about running out then you are likely using far more than the average part of your program. So yes, it isn't intrinsically bad, but context important to evaluate the decision.
- sgtnoodle 5y ago
  I assume you're describing a degenerate case where a tree structure is unbalanced. When operating at that scale, the overhead from all the function calls alone is going to be significant. It's likely going to be maddeningly slower than an iterative solution, like getting an answer in minutes vs. seconds. If it's a balanced tree, then consuming 9GB of stack to do a search would imply that the data structure is what, on the order of 2^1000000 in size? Yikes :-)
  - atq2119 5y ago
    Not every unbalanced tree is necessarily a degenerate situation. Syntax trees aren't necessarily balanced naturally, for example. (They typically are somewhat balanced, of course, but if you do have one that's unbalanced, there's no way of balancing it.) Search trees for NP-hard problems may be an even better example.
Pxtl 5y ago
> The problem here is that once it is used once it is never freed. (Other than being swapped out). So you effectively cache all of the space your program needs forever. What do you mean? It will get freed once you pop that stack-frame won't it?
- marcosdumay 5y ago
  No. It was never allocated either. It was virtual memory before it was used, but once you use it, it's mapped into physical memory and marked as dirty. So it may be swapped out or live there, those are the only two options. It would take your OS being fully aware of your usage schema for it to be able to free the memory.

owl57 5y ago

> IIRC Golang used to do this but switched to copying, growable stacks because no matter how hard they tried they always ended up in scenarios where they were allocating and deallocating stacks in a hot loop. They used to do segmented stacks. The bad overhead is not in allocation, but in switching between segments when stack pointer is oscillating around the boundary — but if you want to allocate really many stacks that could grow large, you don't have much choice: either this or tracking pointers that need to be updated on reallocation. Normal contiguously mapped stack, but with dynamic growing and shrinking of actually mapped pages, is an entirely different proposition.

Dylan16807 5y ago
Ah, that makes more sense, since you could easily limit stack deallocation to once a second or whatever.
kragen 5y ago
In an implementation of a language that can't take the address of a local variable, you can move some stack frames to the new segment when you switch segments, 256 bytes or so. Then, to oscillate around the boundary, you need to return enough times to deallocate those 256 bytes. This will cost enough to swamp the cost of switching segments. (If you can take the address of a local variable, but you have garbage collection and can handle memory allocation failures by exiting, you can heap-allocate whatever local variables have their address taken.) Segmented stacks are a particularly efficient way to implement call/cc.

LeifCarrotson 5y ago

> So you effectively cache all of the space your program needs forever. All the space your program uses at the largest stack size, you mean, which is different. Until you touch it, the huge stack is purely virtual. And it only lasts until you restart the program. Yes, if you default to a 10 GB stack, then recursively tree-search over 9 GB of data, then close the data and spend the next week with 1 MB data that only touches the bottom of the stack, you'll have 8.999 GB swapped out, which does suck. But that only happens if you run the program on that 9 GB of data. The alternative was to fault when you overflowed the smaller stack when that data was imported. It does mean if there's an infinite recursion bug, instead of crashing quickly with a stack overflow, you have to wait while it pages out other programs and fills the whole 10 GB of stack...

kevincox 5y ago
Yes, that is basically what I mean. If you are going to use a very large amount of stack space you should consider alternatively allocating something on the heap and freeing it afterwards. Yes, if most of your program is using roughly the same amout of stack space then it is great. However I think if you are worried about running out then you are likely using far more than the average part of your program. So yes, it isn't intrinsically bad, but context important to evaluate the decision.
sgtnoodle 5y ago
I assume you're describing a degenerate case where a tree structure is unbalanced. When operating at that scale, the overhead from all the function calls alone is going to be significant. It's likely going to be maddeningly slower than an iterative solution, like getting an answer in minutes vs. seconds. If it's a balanced tree, then consuming 9GB of stack to do a search would imply that the data structure is what, on the order of 2^1000000 in size? Yikes :-)
- atq2119 5y ago
  Not every unbalanced tree is necessarily a degenerate situation. Syntax trees aren't necessarily balanced naturally, for example. (They typically are somewhat balanced, of course, but if you do have one that's unbalanced, there's no way of balancing it.) Search trees for NP-hard problems may be an even better example.

Pxtl 5y ago

> The problem here is that once it is used once it is never freed. (Other than being swapped out). So you effectively cache all of the space your program needs forever. What do you mean? It will get freed once you pop that stack-frame won't it?

marcosdumay 5y ago
No. It was never allocated either. It was virtual memory before it was used, but once you use it, it's mapped into physical memory and marked as dirty. So it may be swapped out or live there, those are the only two options. It would take your OS being fully aware of your usage schema for it to be able to free the memory.