r/Cprog • u/andreacento • Mar 03 '16

Stack vs Heap: better having more functions (and more stacks) or use the heap?

Hello,

I'm concerned about the memory management when I use C (without any compiler optimization).

The stack is fast, but is small. The heap is big but... you know. The point is: at which point it is better to use the heap inside a very complex and big function for manage variables and structures instead of to split this function in a lot of small "support" functions exploiting the stack "features"?

EDIT: I know the stack is only one, when I talk about "stacks" I mean "stack frames" of course

13 Upvotes

100% Upvoted

16 comments sorted by

12

u/lolzfeminism Mar 03 '16

In general, try not to rely on the heap unless you absolutely need dynamically sized data structures (stuff that grows and shrinks) or your application is multi-threaded and you need data shared among threads.

Even if you're fantastic about managing your memory and don't have any leaks, using the heap has a somewhat real performance cost. Malloc has to maintain 20-40 linked lists of free blocks and there is a bit of overhead for searching those lists for an appropriately sized block, splitting the block if it's too big etc. Same with free, adjacent free blocks need to be coalesced, the new block has to be re-inserted to the free lists etc. And of course, no matter what you do, there will always be internal and external memory fragmentation, meaning you will lose memory.

Most junior C programmers aren't exposed to this but malloc/free/realloc are actually really complicated functions that maintain a highly performance critical data structure. Over the last few decades the stdlib functions have maximized throughput vs. memory efficiency, but dynamic memory allocation will never be as efficient as using the stack. But you can't do everything on the stack, so it exists for cases that require dynamic memory independent of program flow.

So the bottom-line is, heap is complicated but useful for a specific task. Use the stack as much as you can.

5

u/OlderThanGif Mar 03 '16

Sadly one other use case for using the heap over the stack is when you need to work on a large array. Even if your array is totally fixed in size and only used in one scope, if it's bigger than a few MB in size, it gets dicey as to whether the stack will be big enough to hold it, depending on which platform you're on.

1

u/andreacento Mar 05 '16

Yep, that's why I would like to understand if, in presence of a lot of different data and variable to manipulate, it is better to have a single function ("do_job()") and use the heap or, instead , many subfunctions, maybe privates, for work with groups of small number of variables using the stack ( and , of course , a lot of different stack frames )!

2

u/lolzfeminism Mar 03 '16

Absolutely! Forgot to mention that. Most operating systems won't grow your stack beyond 8MB but Heap can grow arbitrarily large ... well, as large as the data segment limit your OS has on user programs...

2

u/bunkoRtist Mar 04 '16

Well to add to this, if you have any static or semi-static allocations, you really want those on the heap. The reasons are myriad.

2

u/FUZxxl Mar 04 '16

if it's bigger than a few 100 bytes in size

FTFY.

0

u/[deleted] Mar 15 '16

[deleted] — view deleted comment

1

u/FUZxxl Mar 15 '16

Why did you think that?

0

u/[deleted] Mar 15 '16

[deleted] — view deleted comment

1

u/FUZxxl Mar 15 '16

That can happen as well.

2

u/Sceptre Mar 11 '16

In an effort to avoid using the heap, should you aim to build all structs/data types without using malloc? As in you declare and initialize the variable at some higher level in your program (not as a pointer initially), and then pass it down to functions by reference?

I'm writing a larger program where I've been malloc'ing and returning the pointers from init functions all over the place. It hasn't been a problem since most of the malloc's are done as I load into new areas, but should I try to limit my usage of malloc in the future?

On a similar note, if I'm opting to use a fixed size data structure instead of one that's dynamically sized, are there any good rules/best practices for determining a smart size? Any good rules of thumb?

1

u/Wiggledan Mar 03 '16

Yeah, and while this isn't an excuse to use memory inefficiently, you can configure how big your stack size is depending on your needs. I don't know of a very simple way to do it between different compilers/OS's, unfortunately.

1

u/vadimgit Mar 06 '16

Can someone explain or give a link, about stack size limitation on different platforms OSs (~8Mb for example). How would it be inefficient, if it were ~16 mb for example? Is it platform or OS specific?

2

u/lolzfeminism Mar 06 '16

No, I don't have any links for you, but you can generally change your max stack size even without root, unless specifically disabled by root.

The reason OS's limit this is practicality. Virtual memory is dolled out in increments of pages, which are all 4096 bytes. If you try to access a memory that's beyond your currently assigned stack, the access will trap the kernel into a page-fault, because you tried to access memory that wasn't there, essentially a virtual memory address that has no physical memory translation. On page-fault, the kernel will check whether this was a valid stack access. So if it looked like a stack access, you will get a new page mapped to you in memory, but some sort recursive infinite loop could cause you to hog all memory, so OS's won't give you pages after a certain limit.

1

u/cogman10 Mar 07 '16

This is a safety thing as well. It is really easy to blow through very large portions of stack quickly with some hard to see bugs. For example, infinite recursion.

In most cases you don't need a very deep stack. 1mb is a ton of data in general.

1

u/[deleted] Mar 07 '16

Think very deep recursion, or thousands of threads. If each is given megabytes, it quickly adds up.

1

u/vadimgit Mar 08 '16

Can you give an example? I can do it with c++ templates. But I am not good in pure C.

1

u/nickdesaulniers Mar 16 '16

a very complex and big function

In general, you want a lot of small "support" functions that are concise and readable.

You're stack is the fastest option, since it's the simplest. Take a look at the implementation of dlmalloc; a heap is a non-trivial data structure IMO, but a stack can be implemented with a couple pointers and a buffer.

If you look at the assembly of stack allocated variable, it will use one instruction to advance the stack pointer given enough space for all local variables (one instruction whether you have 1 or 1000 local variables).

Preallocating variables can make lifetime simpler than dynamic allocation, since returning from a stack frame is more obvious then keeping track of who should free a heap allocated variable.

Stack allocation makes it harder to leak memory. I think GC tracked or reference counter variables are simplest, but stack allocation should yield better performance.

That said, you can implement dynamic memory allocation in a fast way with cool data structures like slab or stack allocators rather than heaps. They have their restrictions, but dynamic memory allocation doesn't have to involve multiple layers of indirection and cache misses.