Thread: stack vs heap memory allocation

  1. #1
    Registered User gongchengshi's Avatar
    Join Date
    Nov 2007
    Posts
    1

    stack vs heap memory allocation

    I have been taught to use the stack as little as possible. For instance when I need a large temporary buffer I was told to use the heap. I understand that one reason for this might be that the stack size is limited on most systems. If there is no fear of overflowing the stack, wouldn't allocating memory on the stack be faster than allocating it on the heap? To deallocate it, the system just needs to change the position of the frame pointer when the function that created it returns. Right? It seams like allocating and deallocating memory on the heap using new and delete is slower. Besides I like the fact that stack memory is automatically cleaned up for me.

    Any comments?

    Also, what is the maximum stack size for user applications on win32, linux86, ...?

  2. #2
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    I think it's the other way around - use the stack as much as you can. It should indeed be faster, from a theoretical standpoint at least.
    The default stack size on windows is 1 MB, but can be increased. Different stacks are created for all threads, though.
    The stack is like one contigous memory block. You store a value by writing to an address simply and use the stack pointer to read. Push/pop. Push writes to the stack pointer and decrements it and pop reads from the stack pointer and increases it.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Use the stack for small(ish) things (about 512 bytes at most) that you don't need to exist any longer than the lifetime of the function.

    IMHO if you ever find yourself needing to increase the default stack size then you have stuff on the stack that shouldn't be (or have runaway recursion whose code could be refactored).
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    The usage of stack and heap will depend very much on your system design. IN Windows or Linux, using "a bit" of stack is not a problem - the stack is fairly large, hundreds of kilobytes or megabytes. On the other hand, if you are working in a kernel driver in Windows, the stack is 8KB. In embedded systems, the stack is very often quite small.

    Of course, the heap is much larger than both - a 32-bit machine can easily have 2GB heap space [memory in the machine allowing]..

    There is another consideration: What happens when you run out of stack, vs. what happens if you can't allocate memory. If the stack runs out, it's "game over player one", whilst failure to allocate on the heap is at least somewhat recoverable [at the very least, you can (most likely) tell the user what happened!]

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    I'm not sure where this recent tide of stack only allocation posters is coming from but they are incorrect in assuming that all heap objects are bad or that all stack objects are good.

    Matsp hit the nail on the head that most have overlooked concerning the stack. What happens when you run out of stack? The answer is a major crash that is usually not recoverable nor detectable. The stack was not created for large allocations or put there for programmers who do not know how to properly allocate heap memory. For the actual design decisions of why the stack is there and what it is for check the Intel and/or AMD tech refs for the x86 platform. For other platforms you will have to check their corresponding tech refs.

    Just from an assembly language standpoint I shudder to see anything large passed in on the stack and 512 bytes sounds very reasonable if perhaps a bit smaller than what I would use. Anything more than about a couple kilobytes I would agree should be allocated on the heap or at least you should start thinking about doing your allocations differently.

    It should indeed be faster, from a theoretical standpoint at least.
    Theoretically, yes, but this statement is not always true. The stack, just like memory, must also be cleaned up. Granted you do not have to clean up the stack in C++ but the compiler does. The more you push onto the stack the more has to be popped off of it. Depending on where and how this happens the pop operations can add up and hurt performance as well. Check the Intel tech refs for more information on what pop and push do. They have a flowchart and pseudocode of what each opcode/instruction does. Actual clock cycle counts vary depending on the situation and is dependent on preceding code, register contents/usage, CPU optimizations, etc.

    As with anything in life too much of one thing becomes a bad thing. Use the stack the way it was designed to be used and use the heap the way it was designed to be used. To say one is worse or better than the other is a fundamentally flawed statement. They both are good and they both can be bad. I have traditionally used the stack for allocating storage for local function variables in pure assembly functions. It was nice and handy and very easy to use. It seems with the advent of modern OS's many seem to have gotten into a habit of abusing the stack because it is so big now. Be assured, though, it is most certainly NOT designed to store all of your objects or as a catch-all area that you can use because you do not know how to use the heap.

    I remember writing a floodfill() function a long time ago that just ate stack up like there was no tomorrow. It eventually died a horrible death and necessitated a reboot.

    I really feel all of this is a moot point since I don't think on any newer computer memory allocations and/or stack allocations will cause any noticeable performance loss. There are probably bigger fish to fry in your project that will give more significant gains.
    Last edited by VirtualAce; 11-18-2007 at 03:48 AM.

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    DOS was also famous for having a small initial stack size (a couple of K as I recall), and an absolute upper limit of 64K.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Bubba mentions something that I didn't think of: Passing objects. My rule is that I'd never pass a copy of a struct larger than about 16 bytes.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    I would also like to point out that any compiler generating the POP instruction to "clean up" the stack is either really old, or badly written. Data from local variables or arguments is cleared up by adding a constant to the stack-pointer. The actual cost of this is the same whether you clear up 4 bytes or 64K [aside from 1 byte extra once you get over 128 bytes or some such - but that's just code-space].

    As Bubba says, if the block is large enough, the time consumed for malloc and/or free vs. stack management is probably not worth worrying about. There are lower hanging fruit in the optimization tree. Of course, allocating blocks of 16 or 32 bytes is probably not a great idea - if you do that OFTEN, consider your own sub-allocator that allocates a block of x * size_of_your_data [as an array], and then doles that out in the smaller portions. Not only is this better from a "don't call malloc too often", but you also get more contiguous memory for the cache to look at, which improves performance overall. [Each malloc'd memory allocation contains some sort of header data that malloc itself needs to track the allocations. This may be 16-32 bytes itself. With that sort of overhead, small allocations become quite expensive].

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #9
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    I would also like to point out that any compiler generating the POP instruction to "clean up" the stack is either really old, or badly written. Data from local variables or arguments is cleared up by adding a constant to the stack-pointer. The actual cost of this is the same whether you clear up 4 bytes or 64K [aside from 1 byte extra once you get over 128 bytes or some such - but that's just code-space].
    Yes I failed to mention that compilers will do this and I did as well. If I remember correctly it was:

    Code:
    push ebp
    mov  esp,ebp
    ...
    ...
    sub esp,[total_local_alloc_size]
    pop ebp
    I think that is correct. My assembly is quite rusty. And I guess my real point is that there are much more things to worry about when it comes to performance than heap or stack allocations. Some are making a big to do over nothing or are pre-optimizing their code where they 'think, not know, it is slow. In my opinion using these things correctly and knowing when to and when not to utilize them sorta makes a person a programmer.
    Last edited by VirtualAce; 11-18-2007 at 11:36 AM.

  10. #10
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Absolutely. Allocating from the heap is not expensive in a bigger scheme of things, unless you do something else wrong [e.g. allocating tiny blocks lots and lots of times for example].

    Edit: And the stack works towards zero, so you subtract to add more space on it, and add to remove space.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Array of strings and memory allocation
    By maluyk in forum C Programming
    Replies: 7
    Last Post: 01-26-2009, 11:52 AM
  2. Mysterious memory allocation problem
    By TomServo1 in forum C Programming
    Replies: 7
    Last Post: 07-08-2007, 11:29 AM
  3. Finished Stack
    By the pooper in forum C Programming
    Replies: 11
    Last Post: 02-02-2005, 10:52 AM
  4. heap question
    By mackol in forum C Programming
    Replies: 1
    Last Post: 11-30-2002, 05:03 AM
  5. Stack and Heap
    By Barjor in forum A Brief History of Cprogramming.com
    Replies: 6
    Last Post: 01-29-2002, 09:11 AM