• Advertisement
Sign in to follow this  

Allocating memory on the stack or heap

This topic is 3901 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I was asked some months ago if I knew how to allocate memory on the stack versus the heap (C or C++ related). I wasn't able to answer the question, and since then I've been looking for a good answer. I've done a bit of research on the subject and I wanted to see if someone could verify for me if I'm going in the right direction. And there's some follow-on questions that I have now, as well. Thus far what I've found out (and please correct me if I'm wrong (and why was this so hard to find?? Am I just stupid?)) is that by not using a memory allocation function memory is automatically allocated on the stack. Thus: int a = 5; <- memory from the stack But if I do this: int* a = new int; <- c++ or int* a = (int)malloc(sizeof(int)); <- c I get memory from the heap. Assuming that's correct, aren't there limits to using stack memory? And if there are, how do I find out what the sizes are (I'm assuming that this is operating system dependent)? Let's say I have some big huge array that I suddenly decide absolutely has to be on the stack, is there some way of dynamically resizing a stack to make room for it? For that matter, are there pros/cons (other than memory size limitations) I would want memory from one or the other? Thanks for your help with this, - Goishin

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by Goishin
But if I do this:
int* a = new int; <- c++
or
int* a = (int)malloc(sizeof(int)); <- c

I get memory from the heap.

Assuming that's correct, aren't there limits to using stack memory? And if there are, how do I find out what the sizes are (I'm assuming that this is operating system dependent)? Let's say I have some big huge array that I suddenly decide absolutely has to be on the stack, is there some way of dynamically resizing a stack to make room for it? For that matter, are there pros/cons (other than memory size limitations) I would want memory from one or the other?
It depends on your OS, yes. And your compiler. One of the linker settings is "Stack reserve size", which last time I checked was 1MB for Visual Studio (Can't remember what version, probably 2003).
The stack is allocated as a fixed size chunk of memory when your application starts, and each thread in your app gets it's own stack (You're probably just using the one thread, which is the main thread created by the OS).

The stack isn't just used for your variables though, there's also information in there about where a return statement returns to, and suchlike.

Every time you call a function, the code will start a new function at the next free space on the stack, and put that functions local variables (stack variables) there. So, if you have two functions called funcA() and funcB(), and funcA() has 100 bytes used in local variables, then calls funcB(), which allocates 200 bytes, you'll use a little over 300 bytes of stack (100 for funcA, 200 for funcB, and a little added by the compiler to tell it where to return to when funcB finishes).


When you allocate memory from the heap, you're technically allocating memory on the heap and stack. When you do:
int* a = new int[10];
You're allocating 10*sizeof(int) bytes from the heap (Usually sizeof(int) == 4, so that'd be 40 bytes). You also store sizeof(int*) bytes on the stack, which is the actual value of a (Again, usually 4 on a 32-bit OS), and that value is a pointer to tell the CPU where the 40 byte chunk exists.


Hope that helps a bit...

Share this post


Link to post
Share on other sites
Quote:
For that matter, are there pros/cons (other than memory size limitations) I would want memory from one or the other?

One thing you have to consider is that any memory allocated on the stack by the current function will be returned when the function returns. Thus any memory that you want left intact after the function returns will have to be allocated on the heap.
Any memory areas with it's size unknown at compile time will also have to be allocated on the heap.
Allocating very large amounts of memory from the stack is not recommended since a dynamic allocation from the heap can fail wheres you'll run into problems if the stack is filled...

Share this post


Link to post
Share on other sites
Quote:
Original post by Goishin
For that matter, are there pros/cons (other than memory size limitations) I would want memory from one or the other?
Dynamic memory allocation is generally slow. Allocating memory on the stack is essentially free. It's going through a linked list of allocations, finding a block that's a reasonable size, and possibly allocating memory from the OS versus just changing a register from one value to another.

Share this post


Link to post
Share on other sites
Thanks guys(by the way, diggin' on your username there Steve).

That's helping. But also generating new questions [smile]

If memory on the stack is returned when a function returns, how are static variables (in a function, not global) handled? Is that memory stored on the heap instead?

And if stack memory is around a meg, aren't you in danger of of running out of stack space when using recursion(assuming whatever you're recursing is going to be doing a WHOLE bunch of recursing)?

- Goishin

Share this post


Link to post
Share on other sites
Quote:
Original post by Evil Steve
Quote:
Original post by Goishin
For that matter, are there pros/cons (other than memory size limitations) I would want memory from one or the other?
Dynamic memory allocation is generally slow. Allocating memory on the stack is essentially free. It's going through a linked list of allocations, finding a block that's a reasonable size, and possibly allocating memory from the OS versus just changing a register from one value to another.


Is this how it actually works though? I had a game that suddenly became very very slow to start up. I found this was because a function called many times at start up had a largish array in it. I guessed the speed was due to the memory was being re-allocated.

I moved the array to the global scope. Result game started at normal (near instant) speed. So what happened there?

Share this post


Link to post
Share on other sites
Quote:

If memory on the stack is returned when a function returns, how are static variables (in a function, not global) handled? Is that memory stored on the heap instead?

It is stored elsewhere, in the memory location set aside for global and static data. "Heap" and "stack" (heap/freestore for dynamic allocations, stack for local allocations) are just semantic names we assign to particular regions of memory that tend to be used for and treated the same way. To the code, it's all one big 32- or 64-bit address space that the OS has (hopefully) virtualized for us, and it all maps down to the real 32-or-61-bit address space of the physical RAM.

Quote:

And if stack memory is around a meg, aren't you in danger of of running out of stack space when using recursion(assuming whatever you're recursing is going to be doing a WHOLE bunch of recursing)?

Yes.

Quote:

Is this how it actually works though?

In C++? Pretty much. The standard doesn't actually stipulate how dynamic memory allocation takes place, but most implementations involve some kind of walk through lists or other data structures in order to find an available free block of appropriate size. Compare this to C#, where the same operation is generally little more than an addition operation. All languages differ, but its fairly common in C and C++ that "dynamic allocation is not superfast."

On the other hand, it's not cripplingly slow, either, and you should not pre-emptively avoid dynamic allocation on the misguided assumption that its too slow.

Quote:

I had a game that suddenly became very very slow to start up. I found this was because a function called many times at start up had a largish array in it. I guessed the speed was due to the memory was being re-allocated.

I moved the array to the global scope. Result game started at normal (near instant) speed. So what happened there?

This really could have been a result of any number of things, so its hard to say. I should also point out that by moving the array like that you completely changed the semantics and behavior of the code -- its entirely possible, for example, that you actually broke something and you only saw speed increases because massive chunks of functionality were no longer executing (I've seen it happen). The fastest code is the code that never executes, after all!

But yeah. Without the code and some analysis, it's pretty much impossible to tell.

Share this post


Link to post
Share on other sites
Quote:
Original post by empirical2
Quote:
Original post by Evil Steve
Quote:
Original post by Goishin
For that matter, are there pros/cons (other than memory size limitations) I would want memory from one or the other?
Dynamic memory allocation is generally slow. Allocating memory on the stack is essentially free. It's going through a linked list of allocations, finding a block that's a reasonable size, and possibly allocating memory from the OS versus just changing a register from one value to another.


Is this how it actually works though?

Pretty much, yes, at least in "low-level" languages like C/C++. And yes, it does get a bit costly, at least compared to stack allocation.
(in .NET it's a different matter. Heap allocations are cheap enough there (Basically just pushing and popping on a stack)

Share this post


Link to post
Share on other sites
If somebody asked me "how do you allocate memory from the stack?" my first assumption would be that they wanted to see if I knew about alloca. alloca is to the stack as malloc is to the heap.

One downside to using excess stack that hasn't been brought up yet is that depending on how your OS handles stack overflows it can be difficult to properly recover. If malloc fails you my be able to delete a bunch of cache that you don't really need, try again, and go about your business. The same is not necessarily true with the stack because you have to properly reset all the stuff the OS is using to detect when you've gone over the stack limit.

Share this post


Link to post
Share on other sites
Quote:
If memory on the stack is returned when a function returns, how are static variables (in a function, not global) handled? Is that memory stored on the heap instead?

You have to remember that static variables are only stored once, global and local statics the same. I don't know exactly where it puts them, but since there is only one instance, the compiler can basically put them anywhere and hard-code their adresses.

Quote:

nd if stack memory is around a meg, aren't you in danger of of running out of stack space when using recursion(assuming whatever you're recursing is going to be doing a WHOLE bunch of recursing)?

yes, but I guess the OS can introduce some reservations to that statement. Swapping out/in pages etc.

Share this post


Link to post
Share on other sites
Quote:
Original post by Necator
yes, but I guess the OS can introduce some reservations to that statement. Swapping out/in pages etc.


Paging has nothing to do with and is not a solution for running out of stack space.

Share this post


Link to post
Share on other sites
Thanks for all the answers guys, that clears it up. And special points to Anon Mike for the explicit reference to a function!

- Goishin

Share this post


Link to post
Share on other sites
Quote:
Paging has nothing to do with and is not a solution for running out of stack space.

Yeah, true. What I was thinking was that the OS might swap out some parts of the stack and move the remaining part, allowing the stack to grow even further. But I realized that it wouldn't work that well

Share this post


Link to post
Share on other sites
Quote:
Original post by Necator
You have to remember that static variables are only stored once, global and local statics the same. I don't know exactly where it puts them, but since there is only one instance, the compiler can basically put them anywhere and hard-code their adresses.

And that is pretty much what it does. The compiler uses a separate chunk of memory to put all the static stuff into, so it's not exactly stack- or heap-allocated.

Quote:

nd if stack memory is around a meg, aren't you in danger of of running out of stack space when using recursion(assuming whatever you're recursing is going to be doing a WHOLE bunch of recursing)?

yes, but I guess the OS can introduce some reservations to that statement. Swapping out/in pages etc.[/quote]
Yep, recursion can be dangerous like that. [smile]
Of course, in the languages that rely on recursion, there are plenty of solutions for this (an obvious one could be a bigger stack. But also in those languages, most recursive function calls can be optimized to reuse the same stack frame, so the stack usage doesn't grow. That's also possible in some cases in C++, but you have to be more careful with your code to make it possible, and it requires a bit more effort from the compiler. On the other hand, it's also less important since C++ programmers don't rely as much on recursion.

Share this post


Link to post
Share on other sites
You can test creating a stack overflow by infinity recursion:

void foo () {
int i=0;
while (1) foo ();
}

The return addresses and the storage space for i (both 4 bytes on
32 bit machines) will be pushed onto the stack with each function call.
As it is an infinity loop, it will fill up the stack space, causing
a stack overflow exception to generate.

Stack space is in RAM, just like the heap. However, the stack
is directly manipulated through simple pushing and poping.

The heap has to be allocated (and managed) alot more, as your
program either directly (or indirectly) has control over each byte
(rather then a simple push or pop)

Use the stack whenever possible. As others explained (and shown above),
heap memory is generally slower then the stack. However, it also has
more control. Hence, you have to balance control and speed.

Dont introduce bad programming habits here--Alot of people (*Ahem*, Andre
Lamothe), uses *Tons* of globals to favor speed--which is not neccessary.
Using To much stack space is just as bad as to little[smile]



Share this post


Link to post
Share on other sites
So here's what I did.


void foo (int i) {
i++;
printf("up to %d\n",i);
while (1) foo(i);
}

void main(){
int i = 0;
foo(i);
return;
}





When I tried it, I got all the way up to 4777 before I got dumped back to the command prompt. I guess I was expecting some sort of error message or something. [oh]

- Goishin

Share this post


Link to post
Share on other sites
This should work:

#include <iostream>

void foo () {

static int i=0;
std::cout << i++ << std::endl;
foo ();
}

int main () {

foo ();

return 0;
}



MSVC++ gives me a warning about runtime stack overflow from foo()

Share this post


Link to post
Share on other sites
A faster way to get the stack blown up is like this:


struct WOAH_THISISBIGSTRUCT {
int junk [50000];
};
void crazy (WOAH_THISISBIGSTRUCT wtibs)
{
static int i = 0;
printf ("Up to %d\n", i++);
crazy (wtibs);
}





here is the full output of my program before crashing:

Up to 0
Up to 1
Up to 2
Up to 3

Of course you could also overflow it by just making one huge array..

Share this post


Link to post
Share on other sites
LOL! --That code killed my MSVC++ optomizing compilier![grin]

(I am unable to compile it because the compilier keeps crashing[grin])

Share this post


Link to post
Share on other sites
Oh man, that was hilarious!

And that struct name? WOAH_THISISBIGSTRUCT

Priceless...

- Goishin

Share this post


Link to post
Share on other sites
Quote:
Original post by Goishin
Assuming that's correct


Technically, 'new' and 'new[]' allocate from the freestore, which is part of why you can't mix and match new/delete calls with malloc/free calls. (Note that you also cannot mix new/delete calls with new[]/delete[] calls.)

Quote:
aren't there limits to using stack memory?


Yes.

Quote:
And if there are, how do I find out what the sizes are (I'm assuming that this is operating system dependent)?


They're platform-dependent, and you usually find out (if you do) by running out.

Quote:
Let's say I have some big huge array that I suddenly decide absolutely has to be on the stack


No such thing; trust me.

Quote:
is there some way of dynamically resizing a stack to make room for it?


Not dynamically, no.

Quote:
For that matter, are there pros/cons (other than memory size limitations) I would want memory from one or the other?


Not that are likely to matter for most programmers, no. Generally, KISS; the decision about where things go in memory depends on the quality of the needed memory (i.e. is there a specific, logical size it should be, as opposed to "this should be enough"?) rather than the quantity. When you *do* allocate from the freestore, use smart containers like std::vector that let you deal with memory *as if* it were on the stack, and be happy.

Share this post


Link to post
Share on other sites
As for stack resizing, doesn't Linux automatically grow the stack for you?

Seems to, using the WOAH_THISISBIGSTRUCT example I got up to 39 before it segfaulted...

Share this post


Link to post
Share on other sites
Quote:
Original post by empirical2
Is this how it actually works though? I had a game that suddenly became very very slow to start up. I found this was because a function called many times at start up had a largish array in it. I guessed the speed was due to the memory was being re-allocated.

I moved the array to the global scope. Result game started at normal (near instant) speed. So what happened there?
Look at the generated assembly. In debug mode, the compiler will fill all local variables with junk (0xcccccccc in MSVC), and that'll get done every call of the function.
And if your array was of a non POD type, it'll be calling the constructor and destructor for each element of the array too.

Quote:
Original post by rip-off
As for stack resizing, doesn't Linux automatically grow the stack for you?

Seems to, using the WOAH_THISISBIGSTRUCT example I got up to 39 before it segfaulted...
That would be around 1950K of memory used. I'd assume that it's defaulting to a 2MB stack.

Another thing to remember is that the run time library requires some stack space as well, and there's some function on the stack under main(), where the OS actually enters the program.

Share this post


Link to post
Share on other sites
Im sure I read somewhere that the stack grows (while it can) on Linux. Obviously it cannot grow forever because once the stack and heap hit each other we can't relocate either.

However, I found something. On my default install of ubuntu there is an artifical limit set on the stack of. By using ulimit to set this to "unlimited", the program ran until 3959 iterations were completed. Thats what, 50K * ~4000 = ~200Mb, without recompiling my program.

I knew I had read that the stack could grow on Linux somewhere... but I can't find it.

Share this post


Link to post
Share on other sites
Quote:
Original post by Evil Steve
Look at the generated assembly. In debug mode, the compiler will fill all local variables with junk (0xcccccccc in MSVC), and that'll get done every call of the function.


Ahhh! Good point. That must have why.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement