The stack and the heap
A running program keeps its memory in two places. The call stack holds one frame per running call: its parameters, its local names and where to go back to. The heap holds the objects themselves, which can outlive the call that made them. Step through a short Python program and watch frames get pushed and popped, names point to objects on the heap, a list survive its function, and memory get freed; then see a stack overflow and how C makes you manage the heap by hand.
5 quick questions
Pick an answer to see why. Your score saves with your progress.
01What is pushed onto the call stack when a function is called?
Each call gets its own frame on top of the stack. When the call returns, its frame is popped and the program carries on in the frame below.
02In Python, after x = [1, 2] , where is the list itself?
Every Python value is an object on the heap. A name in a frame only refers to it, which is why two names can refer to the very same list.
03def make(): return [0] then a = make() . What happens to the list when make returns?
return hands back a reference. make's frame is popped, but the list lives on the heap as long as something, here a, refers to it.
04A function calls itself with no base case. What happens in Python?
Every running call holds a frame. Python limits the depth (sys.getrecursionlimit() is 1000 by default) and raises RecursionError: a stack overflow.
05In C, you call malloc but never call free. What is the result?
C does not track references for you. Memory from malloc stays taken until free hands it back; forgetting free leaks it.
Glossary
- Call stack
- The pile of frames for the calls that are running now. The newest call is on top; frames are popped in last-in, first-out order.
- Stack frame
- The block of memory for one call: its parameters, its local names, and a link back to where the caller continues.
- Heap
- A large area of memory for objects that are made on request and may outlive the call that made them.
- Reference
- What a Python name holds: a pointer to an object on the heap, drawn as an arrow. Two names can refer to the same object.
- Reference counting
- How CPython knows when to free an object: it counts the references to it and frees it when the count drops to zero.
- Stack overflow
- Running out of stack because too many calls are waiting, usually from recursion with no base case. Python raises RecursionError.
- malloc and free
- C's functions to take a block of heap memory and to hand it back. The programmer must call free; forgetting it leaks memory.
Notes and sources
- The drawing shows one block per running call. In CPython each call gets a frame; frame.f_back links it to the caller’s frame, which remembers where it paused. In machine code, as compiled from C, the call itself pushes a return address on the stack.
- CPython makes small ints, from -5 to 256, once and shares them, so the 3 and 4 already exist before the call.
- CPython frees an object as soon as its reference count drops to zero; a separate collector finds groups of objects that only refer to each other. Other Pythons may free later.
- The recursion limit protects Python itself. sys.setrecursionlimit can raise it, with care: too high a limit can crash the interpreter.
- A C compiler may keep a local variable such as p in a CPU register instead of the stack frame.
- In C a runaway recursion has no friendly limit: it uses up the stack and the program usually crashes.
- Python/C API: Memory management (the private heap)
- Python reference: Objects, values and types
- Python reference: Frame objects
- Python reference: Naming and binding
- Python reference: The del statement
- Python library: sys.getrecursionlimit
- Python library: RecursionError
- cppreference: malloc (C)
- cppreference: free (C)
- Bryant and O'Hallaron, Computer Systems: A Programmer's Perspective (3.7 Procedures, 9.9 Dynamic Memory Allocation)
- Downey, Think Python 2e, 3.9 Stack diagrams
Quiz Unlocks after the last step.