The stack and the heap are two abstractions of memory where programs can allocate memory. The stack is generally used for automatic memory allocation while the heap is generally used for dynamic memory allocation. The stack is related to the data structure with the same name, and is conceptually similar in its function, but is a distinctly different concept.
The stack
The stack is a conceptual area of memory where automatic memory management is the primary way of allocation. It is built like the stack data structure, and is of a limited size, usually of the order of 1 - 4 MB.
Exceeding this size causes the error ‘stack overflow’, which is notably where the website name comes from. This type of error often occurs either because of an excess of recursive calls (if they’re not tail recursive/ optimized) or excessively large local variables, like in the case of a buffer overflow.
Implementation
The program stack is managed by the system at a low level, typically as a contiguous block of memory that grows and shrinks automatically with function calls and returns.
At the assembly level, it is generally composed of stack frames, that represent each individual function call. Stack frames and their relation to procedures is explained in more detail in the procedure article.
As an overview, each stack frame is generally composed of the following:
- Local variables
- Return address
- Parameters
At the very least. This is in top to bottom order, where the stack usually grows downwards into memory addresses (the larger the stack the lower the address).
Use
The stack is mostly used automagically by automatic memory management. Each function call creates a stack frame that holds local variables, arguments, and return information. When the function returns, its frame is removed from the stack, automatically freeing that memory.
The excess memory allocated each stack frame in recursive calls is often what causes stack overflow. This can be optimized with tail recursion, in certain cases.
The Heap
The heap is called the heap not because of a relation to the heap data structure, but rather in C and C++ because it is more similar to a heap of clothes, a big pool of memory to use at runtime.
When using the heap, it is programmer controlled as opposed to compiler controlled, the programmer explicitly requests and frees memory using functions like malloc and free, or new/delete in C++. Unlike the stack, memory on the heap is not automatically reclaimed, it persists until explicitly freed or until the program terminates.
This is the cause of many memory management errors including memory leaks.
The heap under the hood uses a variety of different allocation methods that vary by implementation, like free lists, buddy allocators, arenas etc. In C and C++ programmers interface with those system level allocators using malloc and free.
The heap is significantly larger than the stack, and since the lifetime of its objects is controlled by the programmer, it is generally more flexible. However, it is also slower to access and manage, and comes with many risks.
Many of these risks have been attempted to be minimized with the use of garbage collection or/and smart pointers.