8.2The stack and the heap

Last updated June 12, 2026

Lesson 7.7 left a promissory note: every unfinished function call holds a small "ledge of memory" until it returns, and "the full story of the stack, with diagrams, is lesson 8.2." This is lesson 8.2, and the ledges are about to get their proper name. It's also the floor plan that makes the rest of the chapter mean something, because "ownership" is a system for managing memory, and you can't appreciate the management until you've seen the property.

You already have two pieces of the picture. Lesson 1.3 said memory is an enormous row of numbered boxes. Lesson 2.1 said the machinery tracking function-call bookmarks is called the call stack, and lesson 3.5 let you watch it in a debugger. Today the two pieces connect: the call stack is a region of those numbered boxes, run with a very particular discipline.

A stack, the data structure

Forget memory for a moment. In programming, a stack is anything you use the way a cafeteria uses a stack of plates. The plates are heavy and stacked, so there are only three things you can reasonably do:

1. Look at the top plate.
2. Take the top plate off.
3. Put a new plate on top.

No reaching into the middle, no pulling from the bottom. Adding is called a push, removing is called a pop, and the discipline means the last thing pushed is always the first thing popped. Trace it once: push a red plate, push a blue plate, push a green plate; now pop three times and they come back green, blue, red. That reversal is the whole trick, and it happens to be exactly the shape of function calls: the most recently called function is always the one that finishes first.

The call stack

When your program starts, the operating system reserves a fixed-size run of memory boxes for it: the call stack (in this context everyone just says "the stack"). Picture it as a long column of boxes with a sticky-note marker on the first unused one.

Calling a function pushes a stack frame (7.7's "ledge of memory," under its proper name): a contiguous chunk at the marker holding everything that call needs:

• the return bookmark, lesson 2.1's word for "where to resume when this function finishes",
• one box each for the function's parameters,
• one box each for its local variables.

Then the marker moves up past the frame, ready for the next push. When the function returns, the frame is popped: the marker simply moves back down to where it was. That's the entire transaction.

Notice what isn't in that description: no searching for room, no asking anyone's permission, no cleaning. Pushing a frame is "write a few values, move the marker." Popping is "move the marker back." (The popped frame's boxes aren't even erased; they're just declared meaningless, ready to be overwritten by the next push.) This is why the stack is fast, and why your locals have never needed any cleanup ceremony: a function's variables live in its frame, and the frame evaporates on return. The debugger view from lesson 3.5 was literally this column, one row per frame, growing and shrinking as you stepped.

The stack is fast because it's rigid

The price of that speed is two hard limits.

First, the compiler must know each variable's size at compile time to lay out the frame. Every type from chapter 4 qualifies: an i32 is always 4 bytes, a char always 4, an f64 always 8, a tuple is the sum of its parts. The frame's layout is settled before the program runs.

Second, the whole stack is fixed-size (commonly 8 MB for the main part of your program). Frames normally come and go far below that ceiling, but lesson 7.7's recursion is the famous way to hit it: every call pushes a frame, and if calls keep nesting without returning, the column fills. Let's do it on purpose:

use std::io;

fn nested(depth: u64) -> u64 {
    if depth == 0 {
        0
    } else {
        nested(depth - 1) + 1
    }
}

fn main() {
    println!("How deep?");
    let mut depth = String::new();
    io::stdin()
        .read_line(&mut depth)
        .expect("failed to read input");
    let depth: u64 = depth.trim().parse().expect("not a number");

    println!("{}", nested(depth));
}

Fed a polite 1000, it prints 1000 after quietly pushing and popping a thousand frames. Fed 10000000, ten million frames don't fit:

How deep?

thread 'main' (2267504) has overflowed its stack
fatal runtime error: stack overflow, aborting

That crash is lesson 7.7's stack overflow again, this time produced with a tape measure in hand rather than a missed base case. Note what kind of failure it is: not a compiler error and not an ordinary panic, but the program being stopped at runtime for running out of its fixed-size column. (Why ask the user for the depth instead of writing nested(10000000) directly? The same reason as lesson 4.4: this compiler is sharp enough to evaluate constants ahead of time, and we want a genuine runtime demonstration, not a compile-time argument.)

The misfit

Now line up the rules of the stack against a type you know:

• A frame needs every variable's size known at compile time.
• A String's text grows at runtime, to whatever length the user types (lesson 5.3).

A String's text cannot live in a stack frame. Neither can anything else whose size only becomes known while the program runs. So machines give programs a second region of memory with the opposite discipline: the heap.

The heap is the "ask at runtime" region. When a program needs room for, say, the text of a String, it asks the allocator (the system that manages the heap) for a block of the right size. The allocator finds one, marks it as taken, and hands back its address: the box number where the block starts. The order of requests doesn't predict where blocks end up; you take what the allocator finds.

Each piece of that flexibility costs something the stack never pays. Finding a block takes bookkeeping work, so heap allocation is slower than moving a marker. The address arrives only at runtime, so the program reaches heap data by following an address rather than knowing the spot in advance. And, the point the whole chapter turns on: nothing about the heap is automatic. Frames pop themselves; a heap block stays taken until someone explicitly tells the allocator to take it back.

What a String actually is

So where does that leave let name = String::from("Ada")? Split across both regions, and the split is worth memorizing:

        a stack frame                      the heap
  +---------------------+
  | name:               |          +-----+-----+-----+
  |   address ────────────────────▶|  A  |  d  |  a  |
  |   length:   3       |          +-----+-----+-----+
  |   capacity: 3       |
  +---------------------+

In the frame sits the String itself: a small, fixed-size handle of three values. The address of a heap block, the length in use (exactly what len() has been reporting since lesson 5.3), and the capacity: how big the block is. The text lives in the heap block. The handle is always the same size no matter how long the text is, which is what makes String legal in a stack frame at all.

The capacity field also demystifies growth: push_str writes into spare room while length < capacity, and when the block runs out, the String asks the allocator for a bigger one, copies the text over, and releases the old block. Growable, as advertised, with the growing happening on the heap where runtime-sized things belong.

Stack vs heap

The scorecard, which is also a fair summary of the lesson:

That last cell is the cliffhanger. The frame pops automatically, taking the handle with it, but the heap block doesn't free itself, and lesson 8.1 catalogued what happens when giving-it-back goes wrong. So: who gives the block back, and when? In C, you do, by hand. In Java, the garbage collector does, eventually. Rust's answer is lesson 8.3, and it's already hiding in the ownership rules.

Quiz time

Question #1

For each value, stack frame or heap: a) the i32 local in fn main(); b) the text of a String holding user input; c) the String handle itself (address, length, capacity); d) the bool parameter of a function.

Question #2

In your own words: why can't the text of a String live in a stack frame?

Question #3

A program calls nested(n) from this lesson, and n arrives from user input. One run prints a number; another run dies with fatal runtime error: stack overflow. Explain the difference, and say why the compiler couldn't have caught the second run at compile time.

Next lesson, the cliffhanger pays off in one word, and lesson 2.4 gets the sequel it ordered: what happens to the value when its variable's scope ends.