Why do we need a Heap if everything can be done much more efficiently on the Stack?

Question

This is actually somewhat related to the question I asked yesterday about why both a Stack and a Heap are necessary in the applications we use today (and why we can't just go with a Heap instead of both, in order to have a simple & singular standard to go by).

However, many of the responses indicated that a Stack is irreplaceable due to the fact that is many hundreds (or thousands) of times faster than trying to allocate/reference the Heap. I know there is a problem with dynamic storage allocation if we do away with the Heap, but isn't there a way around this, or perhaps, a way to improve on the Stack so that it can handle dynamic memory allocation?

Answer 1

The problem with stacks is that you can't "free" memory unless it is on top of the stack. For instance, say you allocated 3 things of varying sizes:

a = allocate(2000000); // 2000000 bytes
b = allocate(1);
c = allocate(5000000);

The stack would have a on the bottom, b in the middle, and c on top. This becomes problematic if we want to free b:

free(b); // b is not on top! We have to wait until c is freed!

The workaround is to move all the data after b and shift if so that it comes after a. This works, but will require 5000000 copies in this case - something that will be much slower than a heap.

This is why we have a heap. While allocation may be slower than a stack (O(log n) vs O(1)), heaps allow freeing memory at an arbitrary location to be fast - O(log n), compared to a stack's O(n)

Answer 2

Stack is per-thread, Heap is process-wide

If have 100 threads all processing work items I put into a queue, exactly where do I allocate the work items such that any of the 100 threads could see them?

There are other types of memory, too

E.g. memory-mapped files, shared memory, I/O mapped (kernel mode). The efficiency argument is kind of moot in these situations.

Answer 3

A stack is a LIFO (last-in-first-out) structure, to the top of which a reference pointer is kept (usually supported by hardware). Having said this, anything that you are attempting to allocate on the stack instead of the heap would have to be a local variable in every function, at the top of this stack. So, the main reason against a stack is that your main() routine would need to preallocate all the data structures that your program uses (that are intended to be around for the complete duration of your program) ahead of time as all data structures allocated within function calls will eventually be removed when those function calls return and their frames or activation records are popped-off the stack.

Answer 4

Stacks work great for memory allocations that obey Last in First out (LIFO) rules, that is, you free the memory in the exact reverse order that you allocate it. LIFO is a very common, perhaps the most common, memory allocation pattern. But it's not the only pattern, or even the only common pattern. To write efficient program that can tackle a wide variety of problems we have to make allowance for the less common patterns, even if it means a more complex infratstructure.

If I can get all meta for a paragraph: you are a beginner, as a beginner you value simplicity, and black and white rules. However, as a beginner you have only a peephole view of the range of problems and constraints that have to be accommodated by computer programs. You are entering a technology that has been under active development for going on 75 years. There is nothing wrong with asking why things are the way they are, but the answer is generally going to be "Yeah, we tried the simple, straight-forward method 50 years ago, and it turned out not to work very well for entire classes of problems, so we had to do something more complicated". As a technology advances simplicity generally has to give way to efficiency and flexibility.

Answer 5

For another example, closures. If you stack pop, then you can lose your closure's activation record. So if you want that anonymous function and its data to persist you've got to store it somewhere other than the runtime stack.

Answer 6

Among many other reasons for allocating heap storage.

If you want to pass the address of an object back to a calling program, you should not pass the address of a stack variable, as, the stack storage will be reused and possibly overwritten by the next function called. You need to get the required storage using malloc() to ensure it will not be overwritten by calls to subsequent functions.

You can pass addresses of stack items from your function to functions you call, because you can guarantee they will exist until your program "returns()". But as soon as your function returns all the stack storage is up for grabs.