Understanding stack and heap using a C/C++/Java program

Question

Can someone suggest me any exercise or code to help me understand heap and stack memory better? I have read about this in textbooks a lot, just wanted to see some code to understand better. Maybe some stack overflow example or something like that. I assume C/C++ would be an ideal candidate.

Answer 1

Both the stack and the heap reside in memory. Where exactly isn't necessarily important but you should seek to understand their data structure.

Heap:

For the Heap you should read this example implementation of malloc and it should give you an idea of how it works (code included).

Stack (theory):

The stack (the basic data structure) is a rather simple concept to understand and is explained well enough here. That link also briefly covers how it is used in your program. I haven't found something that I think describes it in a nice way so I'll include the following as additional references to follow up:

1. There is a simple power point about it available here,
2. an interesting (and quite involved) video here
3. and a simplified explanation here.

If these don't quite explain it right, you should try and find something that explains the call stack and the stack frame in a way you will understand.

Stack (code):

All the links I pointed out explain the theory and don't give you the code. My understanding of the stack was significantly improved after I learned about computer architecture and assembly language.

So if you want a code example you should try and implement a simple assembly function and link it to a C program. Here is an example (with a brief intro into assembly).

Java and C++:

Java and C++ hide this stuff from you so if this is a learning exercise I recommend C and assembly. I'm not sure if it is even possible to do it in Java. You can in C++ but it gets complicated...

My explanation of the Call Stack:

I will try and give a short explanation of the call stack and the stack frame with respect to the C programming language and Assembly.

To do that lets define a simple machine so that we can begin on the same page.

Our processor has a finite number of registers, lets say 8. Operations like add, subtract, compare and others can ONLY be done on registers. There are only two instructions that you can execute on memory and they are load and store. These instructions copy from memory to a register, or from a register to memory respectively.

Now, if we want to add 2 numbers we have plenty of variables. We will load one number into register 1 and the other into register 2, add them and put the result into register 3. Now, if we do another operation on registers 4 and 5, store the result in register 6 and then want to add registers 7 and 8 where do we put the result? We have run out of variables...

Clearly we need to use memory and save information there when we are not processing it. To do that we need to know where in memory each variable lives.

You could remember the address of each variable and manually type them in every time, possibly writing it down next to a sensible name on a piece of paper on your desk. But that would be tedious and would pose a serious limitation on functions.

Functions have local variables. If these variable's addresses were hardwired they would always be allocated to the function and would pose a big problem to recursion. If a function were to call itself it would overwrite the values that it's caller (itself) was using.

To solve this the simplest way is to use a stack. However, to do so we need to keep the Stack Pointer address somewhere. So lets just agree that from now on we will use register 8 as our stack pointer.

Also lets say that when you push stuff onto the stack we will subtract the number of bytes we want from the stack pointer and when we want to pop we will add the number of bytes to the stack pointer.

Every time we call a function we will put its local variables on the stack. Since we know what variables we want, we know how much memory we need.

But to access each local variable we need to know its address... Let us set up an example.

Lets say that we have 2 variables, both of which have 2 bytes in our function and that the stack pointer is 18.

As per our agreement lets subtract 4 bytes from the stack pointer, making the stack pointer equal 14.

Now to access the first variable we will simply use the stack pointer. To access the second we will subtract 2 from the stack pointer.

As long as our function is running this will be true, but before our function exits we will free our local variables from the stack by adding 4 to it again, making the stack pointer 18 (like it was before we started).