Sign in to follow this  
DrDev

Stacks and Heaps - What are they?

Recommended Posts

Hi, i am new to c++ and programming in general and would like to know what a stack and heap is. I have seen these terms thrown around alot but have no idea what they are and its starting to confuse me.

Share this post


Link to post
Share on other sites
Different "types" of memory. Stack is basically local scope memory. It's generally faster but you get less of it: about 1MB.

Heap is the rest of the memory. It's slower but you get a lot more of it: 2GB on a 32 bit operating system

Practically:


int poop; // this is allocated on the stack

int *poop = new int; //the integer is allocated on the heap




The rule of thumb: if it's big or put it on the heap (large array, big classes, etc).

-me

Share this post


Link to post
Share on other sites
Well, it depends. Are you talking about the Call Stack and the Memory Heap, or the data-structures the stack and heap? Both are very different things.

I will talk about the call stack and the memory heap first.

Think of the stack as a pile of cards. When a function is called, you create a whole bunch of cards representing where you were in the program, variables you are going to create and parameters you are passing in. You put a rubber-band around these cards, and call it a 'frame'. This frame represents all the static information you know about.

But sometimes we don't know everything. What if we are taking user input? What if we are creating enemies based on how well the user is doing in the game? These things are dynamic! So we can't put them on a static stack, can we? We don't know the size! So we put a place-holder on the stack (a pointer). Now, to create dynamic information, we go to the heap and grab all the data we need. Then, we attach a string from the place-holder on the stack to the data we just pulled from the heap. Now the pointer on the static is a reference to the data we grabbed from the heap.

For a much, much more technical, and better explanation, check out the Call Stack and static memory allocation. For information on the memory heap, check out dynamic memory allocation.


Now, the stack and heap data structures.

Think of the stack data structure as a pile of cards. When you 'push' something on the stack, you place it on top of the cards. When you 'pop' from the stack, you remove the top item from the pile of cards. It is as simple as that.

The heap data structure, on the other hand, is a bit more complex. You can read about it here.

Share this post


Link to post
Share on other sites
A stack is a data structure. Due to its properties, it's useful paradigm on top of which programming languages can be built. There are also programming models which do not use stack.

In C++, stack is how auto-allocations are implemented. There are some restrictions to keep in mind when using those due to the way stack works.

Heap is just that. A big chunk of memory. Applications use it to allocate memory for use. In C++ terminology it's called free store.

Stack is continuous, memory can be allocated only from top (or bottom, matter of terminology), and it's released in same way. This means it's impossible to release memory from middle of stack, but allocations have low overhead.

Heap however allows arbitrary allocations. This gives great flexibility at the expense of higher overhead for allocations. Another side-effect of this is memory fragmentation, where holes created by repeated (de)allocations of differently sized chunks exhaust usable memory, although there's enough of it left. This is similar to disk fragmentation.

Share this post


Link to post
Share on other sites
Quote:
Original post by Palidine
Different "types" of memory. Stack is basically local scope memory. It's generally faster but you get less of it: about 1MB.

Heap is the rest of the memory. It's slower but you get a lot more of it: 2GB on a 32 bit operating system
Your example illustrates the different types of memory [sort of] correctly, but the description may be a bit misleading. First of all, both are the same 'type of memory'. They both exist in the main physical memory, and are thus both the same 'speed'. The difference has to do with how the data is allocated.

Stack memory is a structure allocated exclusively to your program that is used exclusively by your program. When you call a function, the local variables go there. Every thread of execution has its own exclusive stack. This memory is considered 'fast' because there is no allocation process, since the entire memory region has already been given to your program for its use, and there is never a question about where things go. Since the stack has a somewhat small size, though the size is a value that you can set, large things tend to be allocated on the heap.

Heap memory is a pool of memory when you need to allocate things during runtime, or want to allocate something that persists beyond the function that is allocating it. There IS an allocation process to this memory, and this process involves combing over all available memory to find a chunk that is large enough to give to your program. This is why it is considered 'slow'.

This allocation cost is a one time payment though, and even this varies from implementation to implementation. For example, C++ uses a very low level heap implementation with a comparably large allocation cost, but performs very efficiently with respect to the memory used, while a language like C# uses a different type of allocation strategy that is much faster for dynamic allocation, though depends on the garbage collector to deal with collecting discarded data afterwards. In certain instances, it also depends on the platform on which you are working. For example, the heap implementation that C++ relies on is pretty good in PC's, but is utterly horrible in video game consoles like the playstation. Thus the allocation cost is drastically higher on a playstation than your average PC, and the decision to use stack memory where possible instead of heap memory would be more important.

Any speed difference you hear about between heap and stack memory is the result of the allocation process, as the actual physical memory that is used is all the same stuff. Even then, as mentioned, this allocation cost isn't a universally constant thing.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this