10

Possible Duplicate:
C++ Which is faster: Stack allocation or Heap allocation

What is more efficient from memory allocation perspective - stack memory or heap memory? What it depends on?

Obviously there is an overhead of dynamic allocation versus allocation on the stack. Using heap involves finding a location where the memory can be allocated and maintaining structures. On the stack it is simple as you already know where to put the element. I would like to understand what is the overhead in worst case in milliseconds on supporting structures that allow for dynamic allocation?

Community
  • 1
  • 1
Leonid
  • 22,360
  • 25
  • 67
  • 91
  • 6
    efficient for what? – Anycorn Feb 11 '11 at 22:17
  • 2
    Voting to close as NARQ. –  Feb 11 '11 at 22:20
  • The obvious answer is the stack but the stack, itself, governs the lifecycle (which could be very limiting) on anything you allocate on. – bestsss Feb 11 '11 at 22:21
  • I think that this is a very reasonable question. If you aren't already sure what the answer is (that it depends on what you're doing), there's no way to ask a more nuanced question. I think we should reopen this. – templatetypedef Feb 11 '11 at 22:26
  • @templatetypedef: Agreed. The question could probably use some clarification, but I don't think it needed closing. – James Feb 11 '11 at 22:30
  • I also voted to re-open. I don't think that the question is ambiguous or poorly formed at all. – Puppy Feb 11 '11 at 22:32
  • 3
    This is the wrong question. In 99% of the time the difference should not make any difference to you. The question of dynamic or automatic should solely be done based on its usage. In the 1% of cases where it does matter that fact that you know it matters means that you know how to do the appropriate stuff. – Martin York Feb 11 '11 at 23:09

4 Answers4

10

Stack is usually more efficient speed-wise, and simple to implement!

I tend to agree with Michael from Joel on Software site, who says,

It is more efficient to use the stack when it is possible.

When you allocate from the heap, the heap manager has to go through what is sometimes a relatively complex procedure, to find a free chunk of memory. Sometimes it has to look around a little bit to find something of the right size.

This is not normally a terrible amount of overhead, but it is definitely more complex work compared to how the stack functions. When you use memory from the stack, the compiler is able to immediately claim a chunk of memory from the stack to use. It's fundamentally a more simple procedure.

However, the size of the stack is limited, so you shouldn't use it for very large things, if you need something that is greater than something like 4k or so, then you should always grab that from the heap instead.

Another benefit of using the stack is that it is automatically cleaned up when the current function exits, you don't have to worry about cleaning it yourself. You have to be much more careful with heap allocations to make sure that they are cleaned up. Using smart pointers that handle automatically deleting heap allocations can help a lot with this.

I sort of hate it when I see code that does stuff like allocates 2 integers from the heap because the programmer needed a pointer to 2 integers and when they see a pointer they just automatically assume that they need to use the heap. I tend to see this with less experienced coders somewhat - this is the type of thing that you should use the stack for and just have an array of 2 integers declared on the stack.

Quoted from a really good discussion at Joel on Software site:

stack versus heap: more efficiency?

Nawaz
  • 353,942
  • 115
  • 666
  • 851
5

Allocating/freeing on the stack is more "efficient" because it just involves incrementing/decrementing a stack pointer, typically, while heap allocation is generally much more complicated. That said, it's generally not a good idea to have huge things on your stack as stack space is far more limited than heap space on most systems (especially when multiple threads are involved as each thread has a separate stack).

Laurence Gonsalves
  • 137,896
  • 35
  • 246
  • 299
  • Why would having *more* stack space through multiple stacks mean stack space is "especially" limited? – Fred Nurk Feb 11 '11 at 22:28
  • @Fred per-thread stack space is more limited. On single-threaded systems you could have the stack start at one end of memory and have your heap "grow" from the other end, so you could theoretically use your entire virtual address space for stack (if you didn't use heap). Once you have threads each thread needs its own stack. The way that's commonly done is to allocate a relatively small slice of the address space for each stack. The more threads you expect the smaller each slice has to be. This is presumably less of an issue on 64-bit machines given that they have far more address space. – Laurence Gonsalves Feb 11 '11 at 22:46
  • I should probably add that I'm assuming you're on a system with a "flat" address space. If you're using segmented pointers you could have each thread's stack be on a different segment. Also, some languages/runtimes do fancy stuff with the stack so they can be expandedrelocated. I believe Go may actually do this, though I don't see how you could do this in C++ (or C) without breaking the semantics of pointers to the stack. – Laurence Gonsalves Feb 11 '11 at 22:52
  • With a 64-bit address space, you could leave room for a rather large per-thread stack, mapping in actual memory one page at a time, as needed. Having said that, the usual reason people run out of stack space is uncontrolled recursion, not a genuine need for more memory. – Steven Sudit Feb 12 '11 at 11:34
  • @Steven: yeah, I mentioned that this is less of an issue on 64 bit machines in a comment above. Uncontrolled recursion is certainly one reason people run out of stack, though I don't know if it's the "usual reason". It seems most C and C++ programmers have actually had it drilled into them that "recursion is inefficient and/or bad" when one of the real problems is that you just can't recurse very deep with the kind of stack you typically have on a 32-bit platform that supports multi-threading. The tradeoffs are a bit different when a 1MB stack becomes a 4GB stack. – Laurence Gonsalves Feb 12 '11 at 19:46
  • Well said. I guess the stack could also be used up by large local arrays and calls to calloc, but in my experience, recursion is it, because any recursion that creates an infinite loop will overflow the stack. – Steven Sudit Feb 12 '11 at 22:56
1

These two regions of memory are optimized for different use cases.

The stack is optimized for the case where objects are deallocated in a FIFO order - that is, newer objects are always allocated before older objects. Because of this, memory can be allocated and deallocated quickly by simply maintaining a giant array of bytes, then handing off or retracting the bytes at the end. Because the the memory needed to store local variables for function calls is always reclaimed in this way (because functions always finish executing in the reverse order from which they were called), the stack is a great place to allocate this sort of memory.

However, the stack is not good at doing other sorts of allocation. You cannot easily deallocate memory allocated off the stack that isn't the most-recently allocated block, since this leads to "gaps" in the stack and complicates the logic for determining where bytes are available. For these sorts of allocations, where object lifetime can't be determined from the time at which the object is allocated, the heap is a better place to store things. There are many ways to implement the heap, but most of them rely somehow on the idea of storing a giant table or linked list of the blocks that are allocated in a way that easily allows for locating suitable chunks of memory to hand back to clients. When memory is freed, it is then added back in to the table or linked list, and possibly some other logic is applied to condense the blocks with other blocks. Because of this overhead from the search time, the heap is usually much, much slower than the stack. However, the heap can do allocations in patterns that the stack normally is not at all good at, hence the two are usually both present in a program.

Interestingly, there are some other ways of allocating memory that fall somewhere in-between the two. One common allocation technique uses something called an "arena," where a single large chunk of memory is allocated from the heap that is then partitioned into smaller blocks, like in the stack. This gives the benefit that allocations from the arena are very fast if allocations are sequential (for example, if you're going to allocate a lot of small objects that all live around the same length), but the objects can outlive any particular function call. Many other approaches exist, and this is just a small sampling of what's possible, but it should make clear that memory allocation is all about tradeoffs. You just need to find an allocator that fits your particular needs.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
-1

Stack is much more efficient, but limited in size. I think it's something like 1MByte.

When allocating memory on the heap, I keep in mind the figure 1000. Allocating on the heap is something like 1000 times slower than on the stack.

Stephane Rolland
  • 38,876
  • 35
  • 121
  • 169
  • 5
    The stack size depends on your platform, and your application. If you create a worker thread, you can typically even define the stack size. There's definitely no magic number like "1MB". – EboMike Feb 11 '11 at 22:20
  • Where a factor of 1000 comes from? – Leonid Feb 11 '11 at 22:22
  • @Leonid: I have no idea. It would vary depending on the system, and, frankly, I've never timed it. – David Thornley Feb 11 '11 at 22:30
  • @Leonid, 1000 times is probably an overstate but: it will require a CAS at least (likely to be a cache-miss as well), few cache-misses for the new memory, a cache miss is like 300cpu clocks. Stack allocation is a single CPU instruction that's necessary for the method body anyways and the stack is likely to be in the CPU cache. – bestsss Feb 11 '11 at 22:57
  • @Stephane Rolland Windows' stack size used to default to 1MB at some point (still is?), there is no universal number, though. – bestsss Feb 11 '11 at 22:58
  • +1, this is accurate. One cpu instruction to adjust the stack pointer vs acquiring the heap lock and find the right hole to return. Three orders of magnitude is about right. – Hans Passant Feb 11 '11 at 23:08
  • @EboMike @Leonid @bestsss... Twice did I write "something like"... you undestand: it's an estimation... something to keep in mind when coding... Where does this figure come from ? talking with a lot of developers, talented most of the time, I learn a lot from them. I never measured it exactly either, but for me it makes sense. You definitely miss the point when arguing about magic numbers and universal numbers... – Stephane Rolland Feb 12 '11 at 11:00
  • @Stephane Rolland, I am mostly agreeing w/ ya. Reread what I have wrote, plus you will never see any voting from me :) – bestsss Feb 12 '11 at 16:35
  • @bestsss no problem, I was still arguing about my point of view :) However it seems the 1000 is really overestimated. cf this SO question I asked after wondering about that: http://stackoverflow.com/questions/4977726/cpu-cost-order-of-magnitude-for-some-basic-operations/4977916#4977916 – Stephane Rolland Feb 12 '11 at 16:44
  • @Stephane Rolland, the 1st heap alloc can be 1000times slower easily, if it misses the cache, the performance depends mostly on the cache misses – bestsss Feb 12 '11 at 17:18