Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
4  
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". –  Jefromi Oct 9 '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 9 '11 at 18:32
    
...assuming your hardware has a stack, or stack-relative addressing. –  Ritch Melton Oct 9 '11 at 18:38
3  
I'm convinced. I say do it. –  JeffO Oct 10 '11 at 0:52

6 Answers 6

up vote 15 down vote accepted

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)

share|improve this answer
3  
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 9 '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 0:02
1  
@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 0: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
2  
@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

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
3  
LIFO, not FIFO. –  Pubby Oct 9 '11 at 20:02
    
sometimes also called FILO ;) –  oenone Oct 10 '11 at 8:50
    
Thanks @Pubby8. Yes, I meant LIFO. –  Alex Oct 12 '11 at 6:03

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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