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?

  • 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
    Commented Oct 9, 2011 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
    Commented Oct 9, 2011 at 18:32
  • ...assuming your hardware has a stack, or stack-relative addressing. Commented Oct 9, 2011 at 18:38
  • 4
    I'm convinced. I say do it.
    – JeffO
    Commented Oct 10, 2011 at 0:52

6 Answers 6


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)

  • 5
    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. Commented Oct 9, 2011 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
    Commented Oct 10, 2011 at 0: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. Commented Oct 10, 2011 at 0:58
  • 7
    @PaulTomblin The main reason FB doesn't remove the content is so that they can mine it for their profit...
    – quant_dev
    Commented Oct 11, 2011 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. Commented Feb 11, 2013 at 20:44

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.


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.

  • 3
    LIFO, not FIFO.
    – Pubby
    Commented Oct 9, 2011 at 20:02
  • sometimes also called FILO ;)
    – Rommudoh
    Commented Oct 10, 2011 at 8:50

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.


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.


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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.