Memory management

Program memory can be statically or dynamically allocated. The compiler can count all the variables and their sizes, and see when they go in and out of scope. The memory for these variables lives on “the stack.” It's called the stack because you have a contiguous region of allocated and free memory, and whenever you enter or exit a scope, you move the boundary accordingly, like pushing to and popping off a stack [2].

The compiler cannot know how much memory a program requires, since variable amounts of memory can be allocated during the runtime of the program, e.g. by a call to new.

int size = 100;
int * p = new int[size];

We know in advance how much memory is required by the pointer p itself, so p lives on the stack. But the array of 100 ints is dynamically allocated from “the heap” (or “the free store”). Because we cannot predict how much memory will be allocated and when it will be freed, and in what order, the heap is slower than the stack. When memory is requested, we have to find a contiguous chunk which is large enough, and when memory is freed, we have to update data structures which keep track of which memory is allocated.

There is no obvious connection to the data structure called a “heap.”