Stack, Static, and Heap in C++

Question

I've searched, but I've not understood very well these three concepts. When do I have to use dynamic allocation (in the heap) and what's its real advantage? What are the problems of static and stack? Could I write an entire application without allocating variables in the heap?

I heard that others languages incorporate a "garbage collector" so you don't have to worry about memory. What does the garbage collector do?

What could you do manipulating the memory by yourself that you couldn't do using this garbage collector?

Once someone said to me that with this declaration:

int * asafe=new int;

I have a "pointer to a pointer". What does it mean? It is different of:

asafe=new int;

?

Solution 1

A similar question was asked, but it didn't ask about statics.

Summary of what static, heap, and stack memory are:

• A static variable is basically a global variable, even if you cannot access it globally. Usually there is an address for it that is in the executable itself. There is only one copy for the entire program. No matter how many times you go into a function call (or class) (and in how many threads!) the variable is referring to the same memory location.

• The heap is a bunch of memory that can be used dynamically. If you want 4kb for an object then the dynamic allocator will look through its list of free space in the heap, pick out a 4kb chunk, and give it to you. Generally, the dynamic memory allocator (malloc, new, et c.) starts at the end of memory and works backwards.

• Explaining how a stack grows and shrinks is a bit outside the scope of this answer, but suffice to say you always add and remove from the end only. Stacks usually start high and grow down to lower addresses. You run out of memory when the stack meets the dynamic allocator somewhere in the middle (but refer to physical versus virtual memory and fragmentation). Multiple threads will require multiple stacks (the process generally reserves a minimum size for the stack).

When you would want to use each one:

• Statics/globals are useful for memory that you know you will always need and you know that you don't ever want to deallocate. (By the way, embedded environments may be thought of as having only static memory... the stack and heap are part of a known address space shared by a third memory type: the program code. Programs will often do dynamic allocation out of their static memory when they need things like linked lists. But regardless, the static memory itself (the buffer) is not itself "allocated", but rather other objects are allocated out of the memory held by the buffer for this purpose. You can do this in non-embedded as well, and console games will frequently eschew the built in dynamic memory mechanisms in favor of tightly controlling the allocation process by using buffers of preset sizes for all allocations.)

• Stack variables are useful for when you know that as long as the function is in scope (on the stack somewhere), you will want the variables to remain. Stacks are nice for variables that you need for the code where they are located, but which isn't needed outside that code. They are also really nice for when you are accessing a resource, like a file, and want the resource to automatically go away when you leave that code.

• Heap allocations (dynamically allocated memory) is useful when you want to be more flexible than the above. Frequently, a function gets called to respond to an event (the user clicks the "create box" button). The proper response may require allocating a new object (a new Box object) that should stick around long after the function is exited, so it can't be on the stack. But you don't know how many boxes you would want at the start of the program, so it can't be a static.

Garbage Collection

I've heard a lot lately about how great Garbage Collectors are, so maybe a bit of a dissenting voice would be helpful.

Garbage Collection is a wonderful mechanism for when performance is not a huge issue. I hear GCs are getting better and more sophisticated, but the fact is, you may be forced to accept a performance penalty (depending upon use case). And if you're lazy, it still may not work properly. At the best of times, Garbage Collectors realize that your memory goes away when it realizes that there are no more references to it (see reference counting). But, if you have an object that refers to itself (possibly by referring to another object which refers back), then reference counting alone will not indicate that the memory can be deleted. In this case, the GC needs to look at the entire reference soup and figure out if there are any islands that are only referred to by themselves. Offhand, I'd guess that to be an O(n^2) operation, but whatever it is, it can get bad if you are at all concerned with performance. (Edit: Martin B points out that it is O(n) for reasonably efficient algorithms. That is still O(n) too much if you are concerned with performance and can deallocate in constant time without garbage collection.)

Personally, when I hear people say that C++ doesn't have garbage collection, my mind tags that as a feature of C++, but I'm probably in the minority. Probably the hardest thing for people to learn about programming in C and C++ are pointers and how to correctly handle their dynamic memory allocations. Some other languages, like Python, would be horrible without GC, so I think it comes down to what you want out of a language. If you want dependable performance, then C++ without garbage collection is the only thing this side of Fortran that I can think of. If you want ease of use and training wheels (to save you from crashing without requiring that you learn "proper" memory management), pick something with a GC. Even if you know how to manage memory well, it will save you time which you can spend optimizing other code. There really isn't much of a performance penalty anymore, but if you really need dependable performance (and the ability to know exactly what is going on, when, under the covers) then I'd stick with C++. There is a reason that every major game engine that I've ever heard of is in C++ (if not C or assembly). Python, et al are fine for scripting, but not the main game engine.

Solution 2

The following is of course all not quite precise. Take it with a grain of salt when you read it :)

Well, the three things you refer to are automatic, static and dynamic storage duration, which has something to do with how long objects live and when they begin life.

---

Automatic storage duration

You use automatic storage duration for short lived and small data, that is needed only locally within some block:

if(some condition) {
    int a[3]; // array a has automatic storage duration
    fill_it(a);
    print_it(a);
}

The lifetime ends as soon as we exit the block, and it starts as soon as the object is defined. They are the most simple kind of storage duration, and are way faster than in particular dynamic storage duration.

---

Static storage duration

You use static storage duration for free variables, which might be accessed by any code all times, if their scope allows such usage (namespace scope), and for local variables that need extend their lifetime across exit of their scope (local scope), and for member variables that need to be shared by all objects of their class (classs scope). Their lifetime depends on the scope they are in. They can have namespace scope and local scope and class scope. What is true about both of them is, once their life begins, lifetime ends at the end of the program. Here are two examples:

// static storage duration. in global namespace scope
string globalA; 
int main() {
    foo();
    foo();
}

void foo() {
    // static storage duration. in local scope
    static string localA;
    localA += "ab"
    cout << localA;
}

The program prints ababab, because localA is not destroyed upon exit of its block. You can say that objects that have local scope begin lifetime when control reaches their definition. For localA, it happens when the function's body is entered. For objects in namespace scope, lifetime begins at program startup. The same is true for static objects of class scope:

class A {
    static string classScopeA;
};

string A::classScopeA;

A a, b; &a.classScopeA == &b.classScopeA == &A::classScopeA;

As you see, classScopeA is not bound to particular objects of its class, but to the class itself. The address of all three names above is the same, and all denote the same object. There are special rule about when and how static objects are initialized, but let's not concern about that now. That's meant by the term static initialization order fiasco.

---

Dynamic storage duration

The last storage duration is dynamic. You use it if you want to have objects live on another isle, and you want to put pointers around that reference them. You also use them if your objects are big, and if you want to create arrays of size only known at runtime. Because of this flexibility, objects having dynamic storage duration are complicated and slow to manage. Objects having that dynamic duration begin lifetime when an appropriate new operator invocation happens:

int main() {
    // the object that s points to has dynamic storage 
    // duration
    string *s = new string;
    // pass a pointer pointing to the object around. 
    // the object itself isn't touched
    foo(s);
    delete s;
}

void foo(string *s) {
    cout << s->size();
}

Its lifetime ends only when you call delete for them. If you forget that, those objects never end lifetime. And class objects that define a user declared constructor won't have their destructors called. Objects having dynamic storage duration requires manual handling of their lifetime and associated memory resource. Libraries exist to ease use of them. Explicit garbage collection for particular objects can be established by using a smart pointer:

int main() {
    shared_ptr<string> s(new string);
    foo(s);
}

void foo(shared_ptr<string> s) {
    cout << s->size();
}

You don't have to care about calling delete: The shared ptr does it for you, if the last pointer that references the object goes out of scope. The shared ptr itself has automatic storage duration. So its lifetime is automatically managed, allowing it to check whether it should delete the pointed to dynamic object in its destructor. For shared_ptr reference, see boost documents: http://www.boost.org/doc/libs/1_37_0/libs/smart_ptr/shared_ptr.htm

Solution 3

It's been said elaborately, just as "the short answer":

• static variable (class)
  lifetime = program runtime (1)
  visibility = determined by access modifiers (private/protected/public)

• static variable (global scope)
  lifetime = program runtime (1)
  visibility = the compilation unit it is instantiated in (2)

• heap variable
  lifetime = defined by you (new to delete)
  visibility = defined by you (whatever you assign the pointer to)

• stack variable
  visibility = from declaration until scope is exited
  lifetime = from declaration until declaring scope is exited

---

(1) more exactly: from initialization until deinitialization of the compilation unit (i.e. C / C++ file). Order of initialization of compilation units is not defined by the standard.

(2) Beware: if you instantiate a static variable in a header, each compilation unit gets its own copy.

Solution 4

I'm sure one of the pedants will come up with a better answer shortly, but the main difference is speed and size.

Stack

Dramatically faster to allocate. It is done in O(1) since it is allocated when setting up the stack frame so it is essentially free. The drawback is that if you run out of stack space you are boned. You can adjust the stack size, but IIRC you have ~2MB to play with. Also, as soon as you exit the function everything on the stack is cleared. So it can be problematic to refer to it later. (Pointers to stack allocated objects leads to bugs.)

Heap

Dramatically slower to allocate. But you have GB to play with, and point to.

Garbage Collector

The garbage collector is some code that runs in the background and frees memory. When you allocate memory on the heap it is very easy to forget to free it, which is known as a memory leak. Over time, the memory your application consumes grows and grows until it crashes. Having a garbage collector periodically free the memory you no longer need helps eliminate this class of bugs. Of course this comes at a price, as the garbage collector slows things down.

Solution 5

What are the problems of static and stack?

The problem with "static" allocation is that the allocation is made at compile-time: you can't use it to allocate some variable number of data, the number of which isn't known until run-time.

The problem with allocating on the "stack" is that the allocation is destroyed as soon as the subroutine which does the allocation returns.

I could write an entire application without allocate variables in the heap?

Perhaps but not a non-trivial, normal, big application (but so-called "embedded" programs might be written without the heap, using a subset of C++).

What garbage collector does ?

It keeps watching your data ("mark and sweep") to detect when your application is no longer referencing it. This is convenient for the application, because the application doesn't need to deallocate the data ... but the garbage collector might be computationally expensive.

Garbage collectors aren't a usual feature of C++ programming.

What could you do manipulating the memory by yourself that you couldn't do using this garbage collector?

Learn the C++ mechanisms for deterministic memory deallocation:

• 'static': never deallocated
• 'stack': as soon as the variable "goes out of scope"
• 'heap': when the pointer is deleted (explicitly deleted by the application, or implicitly deleted within some-or-other subroutine)

View more solutions

Comments

[raju]

There was a very similar question asked sometime ago: What and where are the stack and heap? There are a few really good answers to that question that should shed some light on yours.

[Swati Garg]

Possible duplicate of What and where are the stack and heap?

[P Daddy]

It's not really relevant to the original question (or to much at all, actually), but you got the locations of the stack and heap backwards. Typically, the stack grows down and the heap grows up (although a heap doesn't actually "grow", so this is a huge oversimplification) ...

[Johannes Schaub - litb]

i don't think that this question is similar or even duplicate of the other question. this one is specifically about C++ and what he meant is almost certainly the three storage durations existing in C++. You can have a dynamic object allocated on static memory just fine, for example, overload op new.

[markets]

@P Daddy - I'll fix the growing direction, thanks... I thought I might have had it backwards, but didn't bother to look it up. Re meeting in middle, I'm being simplistic. I didn't want to explain physical vs. virtual mem. Re GC, I said it was "wonderful" and that python would be "horrible" withoutit

[markets]

@ litb: I think the other question is certainly worth referring to, but not a duplicate. Do you agree? Can you explain to me more about having a dynamic object in static memory? Are you referring to an overloaded new using a static buffer? If so, then true, but the buffer is not dynamic. I'll tweak.

[Stefan]

Often garbage collection is nowadays better than manual freeing memory because it happens when there is little work to do, as opposed to freeing memory that can happen right when the performance could be used otherwise.

[markets]

@gs: Interesting point. Of course, you could lazily deallocate with non-GC, so it comes down, again, to ease of use versus the ability to micromanage. If the ease of use lets you have time to optimize elsewhere, then it was a good perofrmance gain. I'll tweak.

[Johannes Schaub - litb]

@Mark, yeah that's what i meant (overloading op new): an object can have a dynamic storage duration, even though its storage is statically allocated. i think your answer sufficiently explains that and i also (of course) agree the other question is certainly worth referring to by the link. have fun

[Martin B]

Just a small comment -- garbage collection doesn't have O(n^2) complexity (that would, indeed, be disastrous for performance). The time taken for one garbage collection cycle is proportional to the size of the heap -- see hpl.hp.com/personal/Hans_Boehm/gc/complexity.html.

[sellibitze]

I would avoid the term "static variable" because "static" can affect two things depending on the context: the storage duration and linkage.

[Nowhere man]

Actually, with memory size N and live data (non-garbage data) of size M, some GC are not even O(N) but O(M)…

[Shivan Dragon]

I don't think current GCs have such a huge impact on performance as opposed to manual memory management. Depending on what's needed from the program, having it create and destroy a great number of objects on the heap might prove faster with a GC then with a manual approach. The area where manual memory management still takes the cake over GC is that with the former you end up with an application taking (sometimes a lot) less memory than with the latter.

[JBRWilkinson]

With manual memory management, I can have per-thread allocation using private heaps or stackalloc(). This is way cheaper than global heap or global GC even if just because there's no locking to do.

[NPSF3000]

"There is a reason that every major game engine that I've ever heard of is in C++" probably confirmation bias. Heck EVE online IIRC uses that 'scripting language' python. Plenty of games have engines written in C#, Python, Erlang, Flash, Javascript etc.

[markets]

@NPSF3000 I haven't been in the games industry since 2006 so my knowledge is not current. The industry may have changed a bit since I wrote that over four years ago. But I'm still not aware of any major game engine (by which I mean an engine used for AAA titles) that does not use C++, eschewing garbage collection, for its main, time critical processing. Every online isn't licensable, but some might consider it AAA. Do you know of any others?

[NPSF3000]

Typical AAA game engines (Cryengine, Unreal, Unity etc) use C++ for core processing, but they are only a slice of the market. In addition to some MMO's like EVE (IIRC) have you ever seen the play count of Flash based games (e.g. take a look at Kongregate?). I'd also suggest that there may have been mobile AAA games made with GC engines, but don't follow those engines (being a Unity dev) to know their hits. Minecraft was made with Java IIRC.

[NPSF3000]

TL;DR, don't confuse 'allows significant low level optimisation' with 'is performant'. C++ is a great language, and widely used, but it has various tradeoffs including poor performance in many real life scenarios.

[Deduplicator]

@NPSF3000: At most, you can say "poor performance using the default in some real life scenarios". You can just about always replace the default easily if you need it.

[markets]

@Deduplicator: True, and that goes to the heart of C++. In general, C++ never makes you lose performance, and there is always the possibility to drop back to C or even assembly. But it is often time consuming to code the efficient algorithm, at least as much in C++ as elsewhere. Lately I've been thinking more in terms of developer efficiency. C++ is not very efficient with the developer's time. Maybe that is what NPSF3000 is thinking.

[eyalalonn]

@markets: A bit late to the party but there it goes... while manual memory management is certainly important and it can certainly increase the performance of applications if done right, saying bold statements like "C++ never make you lose performance" is not really serious. C++ is a great language but you can't really compare it to Python/Java/C# or whatever because they aren't system languages, however, at the same time these languages can certainly outperform C++ in certain situations mostly due to on the fly optimization of the JIT'ers that are getting better and better.

[markets]

@Eyal Solnik: Yes, JITs can provide a shortcut to an efficient algorithm, as can the friendly development of Python. The fastest way to a performant program is not necessarily through C++, but imagine a graph of performance as a function of effort. If you go far enough out, the C++ curve does reach beyond all the others. It has to, because the others aren't system languages. Python, Java and C# accepted some unconquerable overhead as the price of more usability, and that was a good choice.

[eyalalonn]

@markets I don't know about shortcuts but the JIT can certainly take advantage over CPU features ON THE FLY without ever recompiling the program and I don't see why C++ would win over other languages just because it's a system language. you have this thinking that because other languages are more usable than a price needs to be paid, it's bullshit, assembler programmers told the same things to C programmers in the old days and compilers today are able to produce the same level of optimization, sometimes even better but certainly worst at rare times.