Stack

A range of memory that the operating system has pre-allocated for the program. If a program modifies memory of another program’s allocated memory, this is a Segmentation Fault and the program is killed by the OS.

Properties, Pros and Cons

Properties	Implication
Data is added and removed using a stack data structure	🚫 Single-threaded. Cannot share memory between concurrent executions
Data is stored in a compact fashion	✅ Saves space, by avoiding memory fragmentation ✅ Improved performance with caches1
Variable sizes need to be known ahead of time	Is needed for handling the return value of function calls and local data ✅ Fast allocation times 🚫 No dynamic-type sizes are allowed
Size is pre-allocated and fixed2	🚫 Stack overflow may occur with large data or heavy recursion

Iterative vs Recursive Solutions

Stacks are vulnerable to overflowing with recursive solutions if:

• there is no base case (infinite recursion)
• it takes too many stacks to end the recursion³

Stack size determination

This is usually determined by the operating system with a default value, but it can be configured during compilation time.

Terminology

Terminology	Description
Stack origin	Pointer to the starting address of a program’s stack
Stack frames	A concept which allows programs to group data in memory based on the execution context
Stack pointer	A pointer to the end of occupied memory in a program’s stack
Stack register	A modern hardware feature to quickly keep track of a stack pointer’s value. This allows for much faster execution than storing the pointer in memory.
Return links	A pre-allocated memory address in the stack for the return value of a function call. This is why functions need to have known, fixed-length return types.

Footnotes

1. this is because caches are a range in memory. The more things are stored within that range, the more likely for a cache hit to occur ↩

2. In most programming languages ↩

3. an exception to this is an optimization known as end-tail recursion. ↩