29

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?

Community
  • 1
Dark Templar
  • 6,223
  • 16
  • 46
  • 46
  • 5
    Two excerpts from your previous question: "the most important downside is that it has limited space, and so keeping large objects in it, or trying to use it for long-lived objects, are both bad ideas" and "stacks are an extremely efficient structure for managing data that obeys LIFO (last in first out) rules". – Cascabel Oct 09 '11 at 18:00
  • 2
    Your premise is faulty - not *everything* can be done much more efficiently on the stack. This is no contradiction to the answers you received - that what *can* be done on the stack can be done much faster there. – Ingo Oct 09 '11 at 18:32
  • ...assuming your hardware has a stack, or stack-relative addressing. – Ritch Melton Oct 09 '11 at 18:38
  • 4
    I'm convinced. I say do it. – JeffO Oct 10 '11 at 00:52

6 Answers6

34

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)

Pubby
  • 3,290
  • 1
  • 21
  • 26
  • 4
    Related to this is that Facebook doesn't remove content from its disk when you ask it to remove it, it just removes the pointer to it. Evidently the overhead of trying to defragment or trying to find the equivalent gap on the disk is too time consuming at the rates they're writing data, so they just add everything at the high water mark of the disk. – Paul Tomblin Oct 09 '11 at 20:37
  • Well, facebook's disks can be seen as heap. And I'm pretty sure they have some kind of garbage collection for thoses disks. – deadalnix Oct 10 '11 at 00:02
  • 2
    @deadalnix Actually that is an example of using a huge stack instead of the heap that is normally used for larger amounts of memory. Facebook is a special case though. Data is added so much faster than it is removed that deallocation doesn't make a significant difference to growth rate - you can deliberately include memory leaks in the design to get that O(1) allocation. – Tom Clarkson Oct 10 '11 at 00:58
  • @deadlnix I think their garbage collection is either non-existent, or based upon expiring a drive (clear the whole thing and let it re-replicate). I imagine the latter only happens when a server die or has some other issue. – Jeff Ferland Oct 10 '11 at 14:09
  • Do not repeat not ever try to free any storage on the stack. The stack must be a contiguous piece of storage, you cannot free bits of it as the whole stack algorithm depends on reusing (not freeing, not allocating) storage on the stack. – James Anderson Oct 11 '11 at 03:35
  • @JamesAnderson I don't understand what you mean. Allocation and free are perfectly fine terms for stack-based memory **allocation**. All memory gets reused - I don't see the significance. – Pubby Oct 11 '11 at 05:02
  • @Pubby. The entire "stack" is allocated just after the program is loaded. All functions share this stack for automatic variables. – James Anderson Oct 11 '11 at 06:22
  • @JamesAnderson: Quite a few compilers disagree with you. Or did you perhaps mean "never call `free(&stackVar)`" ? Also, your statement on stack allocation is generally wrong. E.g. Windows uses a "guard page" at the top of the allocated stack, to grow the stack as needed. – MSalters Oct 11 '11 at 11:09
  • 7
    @PaulTomblin The main reason FB doesn't remove the content is so that they can mine it for their profit... – quant_dev Oct 11 '11 at 16:55
  • 6
    `Facebook doesn't remove content from its disk when you ask it to remove it, it just removes the pointer to it` -- Which is essentially what happens when you do an ordinary delete of a file on any operating system. – Robert Harvey Feb 11 '13 at 20:44
  • please explain why allocating on the heal would be O(log2n) – RollRoll Jun 12 '20 at 04:30
6

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.

JBRWilkinson
  • 6,759
  • 29
  • 36
4

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.

Jetti
  • 5,163
  • 2
  • 26
  • 41
Alex
  • 59
  • 2
3

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.

Charles E. Grant
  • 16,612
  • 1
  • 46
  • 73
0

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.

anon
  • 1,474
  • 8
  • 8
0

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.

James Anderson
  • 18,049
  • 1
  • 42
  • 72