5 ms·

From a conceptual point of view, I agree, but... in practice, stacks are incredibly cheap. The entire set of local variables can be allocated with a single bum

From a conceptual point of view, I agree, but... in practice, stacks are incredibly cheap. The entire set of local variables can be allocated with a single bump of the stack pointer upon entry into a function, and they can all be freed with another bump of the stack pointer upon exit. With heap allocations, even with the simplest bump allocator.. you still have to allocate once per object, which can easily be an order of magnitude more work than what you have to do with an equivalent number of stack allocated objects. Your program doesn't magically know where those objects are, so it still also has to pay to stack allocate the pointers to keep track of the heap objects. Then you have the additional pointer-chasing slowing things down and the decreased effectiveness of the local CPU caches due to the additional level of indirection. A contiguous stack frame is a lot more likely to stay entirely within the CPU cache than a bunch of values scattered around the heap. Beyond that, and beyond the additional scanning you already mentioned, in the real world the heap is shared between all threads, which means there will be some amount of contention whenever you have to interact with the heap, although this is amortized some with TLABs (thread-local allocation buffers). You also have to consider the pointer rewriting that a generational GC will have to perform for the survivors of each generation, and that will not be tied strictly to function frames. The GC will run whenever it feels like it, so you may pay the cost of pointer rewriting for objects that are only used until the end of this function, just due to the coincidence of when the GC started working. I think (but could be wrong/outdated) that generational GCs almost all require both read and write barriers that perform some synchronization any time you interact with a heap allocated value, and this slows the program down even more compared to stack objects. (I believe that non-copying GCs don't need as many barriers, and that the barriers are only active during certain GC phases, which is beneficial to Go programs, but again, stack objects don't need any barriers at all, ever.) GCs are really cool, but stack allocated values are always better when they can be used. There's a reason that C# makes developer-defined value types available; they learned from the easily visible problems that Java has wrestled with caused by not allowing developers to define their own value types. Go took it a step further and got rid of developer-defined reference types altogether, so everything is a value type (arguably with the exception of the syntax sugar for the built-in map, slice, channel, and function pointer types), and even values allocated behind a pointer will still be stack allocated if escape analysis proves it won't cause problems.

chrisseaton 5y ago
> you still have to allocate once per object Why can’t you bump once to allocate enough space for multiple objects?
- afiori 5y ago
  No, outside special code it is impossible to know at compile time how many heap allocation a function will have. The stack has the requirement that its size must be known at compile time for each function. In oversimplified terms its size is going to be the sum of size_of of all the syntactically local variables. So for example you cannot grow the stack with a long loop, because the same variable is reused over and over in all the iterations. You can instead grow the heap as much as you want with a simple `while(true){malloc(...)}`.
  - morelisp 5y ago
    > The stack has the requirement that its size must be known at compile time for each function. Not really. You can bump your stack pointer at any time. Even C has alloca and VLAs. In lots of languages it's dangerous and not done because you can stack overflow with horrible results, and some (but not all) performance is lost because you need to offset some loads relative to another variable value, but you can do it. What the stack really has a requirement that any values on it will go full nasal demon after the function returns, so you'd better be absolutely certain the value can't escape - and detecting that is hard.
  - chrisseaton 5y ago
    > No, outside special code it is impossible to know at compile time how many heap allocation a function will have. Huh? def foo: return [new Object, new Object] That'll always bump the TLAB three times. Why not bump it one time for all objects? > The stack has the requirement that its size must be known at compile time for each function. Also huh? For example a local array that has a dynamic size.
- coder543 5y ago
  You can’t do it that way because each object has to have its own lifetime. If you allocate them all as a single allocation, then the entire allocation would be required to live as long as the longest lived object. This would be horribly inefficient because you couldn’t collect garbage effectively at all. Memory usage would grow by a lot, as all local variables are continuously leaked for arbitrarily long periods of time whenever you return a single one, or store a single one in an array, or anything that could extend the life of any local variable beyond the current function. If you return a stack variable, it gets copied into the stack frame of the caller, which is what allows the stack frame to be deallocated as a whole. That’s not how heap allocations work, and adding a ton of complexity to heap allocations to avoid using the stack just seems like an idea fraught with problems. If you know at compile time that they all should be deallocated at the end of the function… the compiler should just use the stack. That’s what it is for. (The one exception is objects that are too large to comfortably fit on the stack without causing a stack overflow.)

chrisseaton 5y ago

> you still have to allocate once per object Why can’t you bump once to allocate enough space for multiple objects?

afiori 5y ago
No, outside special code it is impossible to know at compile time how many heap allocation a function will have. The stack has the requirement that its size must be known at compile time for each function. In oversimplified terms its size is going to be the sum of size_of of all the syntactically local variables. So for example you cannot grow the stack with a long loop, because the same variable is reused over and over in all the iterations. You can instead grow the heap as much as you want with a simple `while(true){malloc(...)}`.
- morelisp 5y ago
  > The stack has the requirement that its size must be known at compile time for each function. Not really. You can bump your stack pointer at any time. Even C has alloca and VLAs. In lots of languages it's dangerous and not done because you can stack overflow with horrible results, and some (but not all) performance is lost because you need to offset some loads relative to another variable value, but you can do it. What the stack really has a requirement that any values on it will go full nasal demon after the function returns, so you'd better be absolutely certain the value can't escape - and detecting that is hard.
- chrisseaton 5y ago
  > No, outside special code it is impossible to know at compile time how many heap allocation a function will have. Huh? def foo: return [new Object, new Object] That'll always bump the TLAB three times. Why not bump it one time for all objects? > The stack has the requirement that its size must be known at compile time for each function. Also huh? For example a local array that has a dynamic size.
coder543 5y ago
You can’t do it that way because each object has to have its own lifetime. If you allocate them all as a single allocation, then the entire allocation would be required to live as long as the longest lived object. This would be horribly inefficient because you couldn’t collect garbage effectively at all. Memory usage would grow by a lot, as all local variables are continuously leaked for arbitrarily long periods of time whenever you return a single one, or store a single one in an array, or anything that could extend the life of any local variable beyond the current function. If you return a stack variable, it gets copied into the stack frame of the caller, which is what allows the stack frame to be deallocated as a whole. That’s not how heap allocations work, and adding a ton of complexity to heap allocations to avoid using the stack just seems like an idea fraught with problems. If you know at compile time that they all should be deallocated at the end of the function… the compiler should just use the stack. That’s what it is for. (The one exception is objects that are too large to comfortably fit on the stack without causing a stack overflow.)