Storage Allocation Strategies
A storage allocation strategy decides when and where storage for a data object is created and freed. The three classic strategies map to the static, stack, and heap areas of run-time memory.
What is a Storage Allocation Strategy?
Definition. A storage allocation strategy is a rule the compiler and run-time system use to decide when storage for a data object is allocated and freed, and where in memory that storage lives.
Every variable, constant, and object needs space at run time. The compiler does not pick one scheme for the whole program — it chooses per object, based on how long the object must live and whether its size is known ahead of time.
There are three classic strategies, one for each area of the run-time memory layout:
| Strategy | Memory area | Decision made at |
|---|---|---|
| Static | Static data | compile time |
| Stack | Control stack | call / return |
| Heap | Heap | arbitrary run time |
Static Allocation
Definition. In static allocation, storage for a data object is bound at compile time to a fixed address that does not change for the entire run of the program. No allocation or freeing happens while the program executes.
Because the address is fixed, the compiler can plug it directly into the generated code. This is the simplest and fastest scheme — there is zero run-time cost for allocation.
Properties / limitations:
- The size of every object must be known at compile time.
- Recursion is not supported — a recursive procedure would need many live copies of its locals, but static allocation gives each name exactly one fixed slot.
- Objects live for the whole run, even if used only briefly.
Typical uses: global variables, C static locals, string and numeric constants.
int counter = 0; // global → static address
void tick() {
static int calls = 0; // 'static' local → one fixed slot,
calls = calls + 1; // value survives between calls
}Both counter and calls get a single fixed address chosen by the compiler, so calls remembers its value across every call to tick.
Stack Allocation
Definition. In stack allocation, storage for one activation of a procedure is allocated on the control stack when the procedure is called, and freed when it returns. Allocation is last-in, first-out (LIFO).
Each call pushes a fresh activation record (stack frame) holding that call's parameters and local variables. This is what makes recursion work: every active call has its own record with its own copy of the locals, so the calls do not clobber each other.
Consider the running program:
While fib(3) is evaluating fib(2), two fib activations are live, each with its own n:
When fib(2) returns, its record is popped and the space is reused for the next call, fib(1). (See the control stack topic for how these records are linked.)
Heap Allocation
Definition. In heap allocation, storage is allocated and freed at arbitrary times, independent of procedure call and return. An object on the heap may outlive the activation that created it.
The stack cannot hold data that must survive past the call that made it — a returning procedure pops its frame. When a value must live longer (or its size is decided at run time), it goes on the heap, managed by a memory manager.
Heap storage is freed either:
- explicitly by the programmer (
freein C,deletein C++), or - automatically by a garbage collector (Java, Go, Python).
Typical uses: malloc / new blocks, objects returned from a function, dynamic data structures like linked lists and trees.
int* makeArray(int len) {
int* a = malloc(len * sizeof(int)); // heap-allocated
return a; // survives this call!
}
// ... later, when done:
// free(a);The block returned by makeArray lives on after the function returns, which a stack local could never do — that is exactly why it lives on the heap.
Comparing the Three Strategies
| Static | Stack | Heap | |
|---|---|---|---|
| When allocated | Compile time (fixed address) | On procedure call | At any run time (malloc/new) |
| Lifetime | Whole program run | Until procedure returns | Until explicitly freed or GC'd |
| Supports recursion? | No | Yes | Yes |
| Freed by | Never (never reclaimed) | Automatically on return (pop) | free/delete or garbage collector |
| Typical use | Globals, static, constants | Locals, parameters | Dynamic objects, linked lists, trees |
The three are complementary, not competing: a single program uses all three at once — a global counter (static), the fib parameter n (stack), and a malloc'd array (heap).
Key Points
- A storage allocation strategy decides when and where an object's storage is allocated and freed; the choice is made per object.
- Static: bound at compile time to a fixed address, lives the whole run, no recursion, zero run-time cost.
- Stack: allocated on call, freed on return, LIFO; each activation gets its own record, which is what enables recursion.
- Heap: allocated/freed at arbitrary times; objects can outlive their creating activation; freed by
free/deleteor a garbage collector. - The danger spots: static wastes space for rarely-used data; heap can suffer fragmentation and leaks if not freed.