programmingconcepts

§ 5.1 · Memory

Stack vs heap

Two places a running program keeps data: the stack holds each call's own variables and is freed when the call returns; the heap holds data that has to outlive a call.

The stack and the heap are two areas of memory. The stack holds each function call's parameters and local variables, and it is freed automatically when the call returns, which makes it fast. The heap holds data that must outlive a call or whose size isn't known in advance; it is freed by a garbage collector, an owner, or free().

Stack
One frame per call, freed on return
Heap
Lives while something refers to it
Stack speed
Allocate by moving one pointer
Typical stack size
1–8 MB per thread
Requires
RecursionArrays
def build(n):
    nums = [0] * n
    for i in range(n):
        nums[i] = i * i
    return nums


def demo(count):
    squares = build(count)
    alias = squares
    alias[0] = 99
    return squares

Call demo(3). It gets a frame on the stack, and its parameter count = 3 is stored right inside it.

step 0 / 0running framereference usedjust written

Fig. 5.1. Stack frames on the left, newest on top; objects on the heap on the right. An arrow is a reference. The outlined frame is running, blue marks a reference being followed, and orange is a value just written.

Intuition

Think of a desk and a warehouse. Each time you start a task you put a fresh sheet of paper on top of a pile on your desk and scribble the task’s notes on it. When the task is done, you throw away the top sheet. That pile is the stack: fast, tidy, and everything on a sheet disappears with it.

Some things are too big for a sheet, or need to stay around after the task ends: a list of a million names, an object you’ll hand to someone else. Those go in the warehouse, and your sheet just notes the shelf number. That’s the heap, and the shelf number is a reference (a pointer).

How it works

When a function is called, the program pushes a stack frame holding the call’s parameters and local variables. When the function returns, the frame is popped and all of it is gone at once. Nothing has to be cleaned up one variable at a time, which is why the stack is so cheap.

When code creates something that must outlive the call, or whose size isn’t known in advance, it is allocated on the heap. The variable on the stack holds a reference to it. Several references can point at the same object, and the object stays alive while at least one does.

In the figure:

  1. demo(3) runs with count in its frame.
  2. Calling build(count) pushes a new frame and copies the number into n.
  3. [0] * n creates a list on the heap; nums only holds a reference to it.
  4. build returns. Its frame is popped, but the list survives because squares now refers to it.
  5. alias = squares copies the reference, so a change through alias shows up in squares too.

Stack vs heap at a glance

Aspect Stack Heap
Holds Parameters, locals, return addresses Objects that outlive a call or vary in size
Lifetime Until the function returns Until nothing refers to it (or it is freed)
Allocating Move the stack pointer: almost free Ask the allocator to find a free block
Freeing Automatic on return Garbage collector, owner, or free()
Size Small and fixed: about 1–8 MB per thread Up to the machine’s memory
Goes wrong as Stack overflow from deep recursion Leaks, fragmentation, use after free

In each language

Language What goes where
Python Every value is an object on the heap; frames hold references. The garbage collector (reference counting plus a cycle finder) frees objects.
JavaScript Objects and arrays live on the heap; engines keep small numbers inline. A garbage collector frees what is unreachable.
Go The compiler decides by escape analysis: a slice returned from a function escapes, so it goes on the heap. A slice variable is a small header (pointer, length, capacity) that points at its array.
Rust Vec, Box and String put their data on the heap. Each value has one owner, and the memory is freed when the owner goes out of scope; there is no garbage collector.
C malloc gives you heap memory and free gives it back. Forgetting free leaks; using memory after free is undefined behaviour.
Java Objects are on the heap; local primitives (int, double) and references live in the frame.

Common mistakes

  1. Thinking assignment copies a list. b = a copies the reference; use a.copy() (Python), [...a] (JavaScript) or slices.Clone (Go) for a separate list.
  2. Returning a pointer to a local in C. The local’s frame is gone after the return, so the pointer dangles.
  3. Huge arrays as locals. A 10 MB local array overflows a 1 MB stack. Put it on the heap.
  4. Blaming the heap for slowness. Allocation is slower than the stack, but rarely the bottleneck. Measure before rewriting.

Check yourself

Check yourself

After build returns, why is the list still there?

Check yourself

b = a where a is a list, then b[0] = 5. What is a[0]?

Sources

  • Randal E. Bryant and David R. O’Hallaron, Computer Systems: A Programmer’s Perspective, 3rd ed., chapters 3.7 (procedures and the run-time stack) and 9.9 (dynamic memory allocation).
  • The Go FAQ, “How do I know whether a variable is allocated on the heap or the stack?”
  • The Rust Programming Language, chapter 4, “Understanding Ownership”.

Newsletter

One new concept each week, by email.

Signup opens soon.