Printable View
I been reading many C prog books by now and no one have really explained what the real difference is between the stack and the heap. One is accesed by new/delete and the other one not. But when should I use the stack and when should I use the heap?Is both the stack and the heap located in RAAM? How can I find out how big the stack and heap are? Do they have the same access speed?
Thanks
~Barjor
the stack is an area of memory that is used to astore the return address of functions and to hold local variables. Variables are pushed onto the stack and pooped of.
And be assured your don't want to touch those variables after the stack has pooped them out. :)Quote:
Originally posted by iain
Variables are pushed onto the stack and pooped of.
The heap is a much larger memory resource for your applications. Having a few integers (etc) pushed onto the stack won't hurt you, but it is a good idea to put your large arrays and structs on the heap. You can overflow your stack fairly easily, especially if you're not keeping a close eye on your recursive functions.
I'm assuming that you know what the data structure known as a stack is. A lot of my discussion is going to maybe be inaccurate, and it probably will be DOS/Intel-specific... and the syntax I made up.
The stack and heap both reside in RAM. The heap is at the bottom, the stack is at the top. Here's a picture....Now, let's say that you want to push an item on the stack, you just decrement sp, and voila, your stack is now 1 block bigger. If your stack hits reserved memory in the heap, then your program go bye bye. The stack is nice because it's extremely easy to allocate / deallocate memory for it like this. Handling memory on the heap is a lot more complicated (see the K&R implementation of malloc). Raising sp (and thus removing a block from the stack) is called popping. Lowering sp (and this adding a block to the stack) is called pushing. When you push, you can also choose a value for the new block in the stack at the same time.Code:[] <- This is the top of memory
[] <-Every block above the sp is reserved
[] <-Every block above the sp is reserved
[] <-Every block above the sp is reserved
[] <- sp (stack pointer) points here
[] <- below
[]
[] <- this is a memory block.
[]
[] <- Everything here is your heap
[] <- Some might be reserved, some might not, but it tries to
[] <- keep low so it doesn't collide with sp
[]
[] <- I think your program resides here
Now, what goes on the stack, and what goes on the heap?Let's just run down the lines. First, you have your global data. These are the first things to go into your program's heap. They go at the bottom. It's hard to allocate and deallocate memory on the fly, but since your program is going to have them in memory the whole time, it just has to allocate it once at the beginning and deallocate it once at the end, which is easy to do. Also, there isn't really any way to have the entire program be able to access something on the stack, since our point of reference on the stack is always moving.Code:char global;
char aglobal[100];
int main (void)
{
char * s;
int a;
char c;
int array[100];
a = 2;
// Beh, let's just do nothing.
char = doNothing (a);
return 0;
}
void * doNothing (int passedVal)
{
void * result;
int b = 2;
passedVal = passedVal + b;
result = malloc (52);
return result;
}
So we have global and aglobal. The first takes one byte, the latter takes 100 bytes, both go on the bottom of the heap.
char * s;
int a;
char c;
int array[100];
Okay, now this is 409 bytes worth of local variables we've got here (each int and pointer takes 4 bytes), and we don't have to initialize any of them... hurray. This memory we allocate on the stack, and it's easy to do...
sp -= 409
That was easy enough no? s is on the top, a is next, c comes next, then the 100 ints. So, when we refer to each of these, your computer does it like this...
#define s (sp + 405)
#define a (sp + 401)
#define c (sp + 400)
#define array (sp)
Next, we assign the value of 2 to a....
*(a) = 2
or equivalently...
*(sp + 401) = 2
Or in english, move the value 2 into the memory pointed at by sp+401.
Next we call a function. This is kinda tricky. We need to somehow get a from main to doNothing, get result from doNothing back to main, and there's a bit of CPU information that needs saved. First, we put a on the stack.
sp -= 4
*sp = *(a + 4)
Notice we have to take the change of sp into account, since a is referenced relative to sp. Everything on the stack is referenced relative to sp.
Next, we need memory where result (a pointer, and thus it takes 4 bytes) will be. Again, we use the stack..
sp-= 4
We don't have anything to put in there though.
Finally, we have some machine stuff to put in there. What exactly this entails depends, but the most important bit of information is it pushes a pointer to the current location in your program. This is possible because your program is loaded in memory, so we can have a pointer to it. When we call the function, we jump to another point in the program, so we need this information to know where to go back to when we're done in the function.
I'm going to assume that we have to store 8 bytes of information for this stuff...
sp -= 8
*sp = *CPUarea
goto doNothing
---- Notice how you can skip the following section, and ignore the mechanics of the function, just like in C. You can also understand how this function works without having to look at the caller.
Now we're in doNothing. First let's make some space for result and b....
sp -= 8
#define result (sp + 4)
#define b (sp)
We don't really know much anything about who called us, although we do know information about the stack....The parts that interest us are passedVal and result, so...Code:For the sake of space, each block represents 4 bytes...
[] <- passedVal
[] <- returnVal
[] <- CPU stuff
[] <- address of caller
[] <- result
[] <- b (sp)
#define passedVal (sp + 20)
#define returnVal (sp + 16)
So, let's do the math.
*b = 2
*passedVal = *passedVal + *b
Now we have a call to malloc, which is kinda tricky. It reserves memory on the heap, but we let the operating system handle this.
*result = (get address of memory allocated on heap)
Finally, we get to the return statement. This has two parts. First, we have to take the value we want to return and put it in returnVal...
*returnVal = *result
Now we have to actually return. First, we scrap the local variables...
sp += 8 // frees b and result
Then we load CPU information off the stack...
*CPUarea = *sp
----- Stop skipping here.
Now the CPU is looking back at the main function, at the point after goto doNothing. It's our job to get the stack back to normal...
First, let's scrap the information the CPU needed for the jump
sp += 8
Next on the stack is the space we allocated for the result. We have to put it into s...
*s = *sp
sp += 4
Finally we have to get rid of the copy of a we made.
sp += 4
Apparantly the function changed the value of the copy we made of a, but that doesn't have any effect on us, since it wasn't actually able to access a, just the copy we put on the stack.
Now sp is back to where we expect it to be, at the bottom of our local variables. We can resume execution.
Then we hit return. Since it's a return from main, it's quite unique, and not something I am going to discuss.
You don't really have any choice over when you use the stack and when you use the heap. Local variables use the stack, and global variables use the heap. malloc() also uses the heap, but since it does so during the program's execution, it's a fairly slow operation.
Some things I wasn't quite accurate about in the above discussion...
1) The size of the stack is not neccisarily 'however so long as you don't hit something in the heap', although in some cases it is.
2) Technically, the address that is pushed on the stack is not that of the calling function. Instead, that gets put into a register, and whatever was in the register before gets pushed onto the stack.
What's important is that, every time you call a function, even if that function has no return value and accepts no arguments, something will have to be put on the stack.
Your C programs really should be blind to the fact that there's even a stack and a heap. In fact, your compiler very well may change how it deals with memory on a program-by-program basis for optimization sake (it might even not store some variables in memory, instead using registers which are extremely fast).
Wow! Thanks for the replays. I appreciate it alot
~Barjor
That's a really good explanation.
One question: You said that the stack can "grow" until it reaches some data in the heap, but it must have a minimum size, right? ie it can't be smaller than 64kb or something?
Well... it's kinda strange ground. There are three memory models: Real Mode Flat, Real Mode Segmented, and Protected Mode Flat.
I was thinking of Real Mode Flat memory when I wrote that description (this basically describes .COM files). So the discussion's a bit antiquated, but still generally gets the idea across I think.
In Real Mode Segmented (DOS .EXE files), and Protected Mode Flat (32-bit programs), I think that your stack is actually some finite size defined by the assembly program.
Now, I"m pretty sure Real Mode Segmented didn't have any minimum size, but really I dunno anything about Protected Mode Flat, so maybe.