The Stack & The Heap

in reviewThis lesson is complete and being validated before release - details may still change.

The stack and the heap

Loading interactive demo…

The map is the program's memory, 32 words with address 0 at the bottom left: the code and static data at the bottom, the heap growing up from them, the stack growing down from the top. A frame is marked with its depth, a heap block with its name, and the words an operation just touched are ringed. Tap a word to ask what owns it. The strips below list the frames and the heap blocks.Take the tour, or press and explore. Legend:

The panel beside the stage is the real ProcessMemory class from the published library executing in your browser, with the current line highlighted.

The words the current operation touched, and the frame or block it acted on.
A stack frame; alternate frames are shaded apart.
An allocated heap block.
A hole: freed heap waiting to be reused, or a fault.
The code and static data, and the unused gap between heap and stack.

frames is the stack's depth, stack and heap the words each has taken, in holes the free heap words that cannot be given back, and largest hole the biggest request they could still serve.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

Two lifetimes. A program's memory holds things with two kinds of lifetime. A local variable lives exactly as long as the call that declares it, and calls nest: the newest call always ends first. A block the program asks for by size, to hold a string or a list it will keep, lives until the program says otherwise, in any order at all. Nested lifetimes get a stack; arbitrary lifetimes get a heap; and the layout every compiler uses puts the code and static data at the bottom, the heap above them growing up, and the stack at the top growing down, so that neither needs a fixed size until they meet.

The stack. A call pushes a frame: the return address, so the callee knows where to go back to, and room for its locals. The stack pointer, a register, moves down by the frame's size, and that is the whole allocation: $O(1)$ , no search, no bookkeeping. A return moves it back up, and the frame is gone. The tiny CPU's JUMP into a subroutine would need exactly this to return. Recursion is calls nesting deeper, one frame per level, which is why the recursion script's stack grows four frames and shrinks four frames, and why recursion without a base case ends in a stack overflow: the frames reach the heap.

The heap. An allocation of $s$ words searches the free list for a hole of at least $s$ . First fit takes the first one, splitting off what is left; if none fits, the heap grows into the gap toward the stack. A free marks the block as a hole and merges it with any free neighbour, so that two adjacent holes become one. Both operations walk the list: $O(\text{blocks})$ , against the stack's $O(1)$ , and real allocators keep holes binned by size to make that fast.

Fragmentation. The default script frees $B$ between $A$ and $C$ , leaving a four-word hole, then asks for six words. The hole is too small, so the heap grows, and the four words sit idle: free memory the program cannot use because it is in the wrong place. That is external fragmentation, and Knuth's analysis says an allocator settles into having about half as many holes as blocks. The merge on free is what keeps holes from multiplying: freeing $A$ and then $E$ turns three small regions into one of eight, which the request for $F$ fits exactly.

Running out. The leak script allocates without freeing until the heap top would pass the stack top: out of memory with words to spare, had any been freed. The overflow script calls without returning until the stack would pass the heap top. Same wall, two sides. Garbage collectors, two lessons on, free blocks the program has forgotten; nothing frees a stack that never returns. And the 32 words here are the memory the program sees, not the memory that exists: the next lesson puts a page table between the two.

Where a variable lives. A compiler puts a value on the stack when its lifetime is a call's and it cannot escape, and on the heap when it must outlive the call, is too large, or is shared. The two strips on the stage are the two answers to the question every language runtime asks about every value.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

call is two subtractions and a push, and pop is their undoing; neither looks at any other frame. That asymmetry with the heap methods is the lesson in code.
The heap is a list of blocks in address order, allocated or free, so a hole is a block with no id and merging is a splice over neighbours. Real allocators thread the free blocks together and keep boundary tags to find a neighbour in constant time.
alloc searches before it grows, and reports which holes it looked at and whether it split, so the stage can say why a request skipped a hole.
A hole at the top of the heap is given back to the gap, which is how heapTop can fall as well as rise; most allocators only release memory to the system in large pieces.
Faults are reported, not thrown, as in the CPU, and the run stops at the first; a bad free or an extra return is a fault too, the way a double free is a bug in C.
The static region is a size, not content: the lesson is about the two regions that move.

The stack as a way to run a program came from compiling arithmetic: Friedrich Bauer and Klaus Samelson patented a push-down store for evaluating expressions in 1957, and Edsger Dijkstra's ALGOL 60 compiler of 1960 put every procedure's variables in a frame on one, which is what made recursion cheap and routine. The heap is older and messier: John McCarthy's LISP of 1960 handed out cells from a free list and collected them with a garbage collector, Donald Knuth analysed first fit and best fit in 1968, and the C language made the free list the programmer's own problem, which it has stayed.

1957Friedrich Bauer and Klaus Samelson - Patent the Kellerspeicher, a push-down store for translating and evaluating expressions: the stack as a machine component.source
1960Edsger Dijkstra - Recursive Programming describes keeping each procedure activation's variables in a frame on a stack, the scheme ALGOL 60 compilers and every language since use for calls.source
1960John McCarthy - LISP allocates list cells from a free list and reclaims the unreachable ones with a garbage collector, the first managed heap.source
1968Donald Knuth - The Art of Computer Programming analyses dynamic storage allocation: first fit against best fit, boundary tags for merging, and the fifty percent rule for how many holes to expect.source
1978Brian Kernighan and Dennis Ritchie - The C Programming Language ends with a free-list allocator written in C itself: the malloc and free that this stage imitates.source
1987Doug Lea - dlmalloc, the allocator behind many C libraries for decades, binning free blocks by size to make first fit fast.source

Used today

Every running program - Locals, arguments, and return addresses live on the stack; everything that outlives a call, from strings to objects, lives on the heap.
Language design - Garbage collectors, reference counting, and ownership systems are all answers to the question of who frees a heap block and when.
Security - A frame overrun that overwrites a return address is the classic exploit, and a heap allocator's metadata is the modern one.

program

frames: 1
stack: 3 words
heap: 8 words
in holes: 0
largest hole: 0

process-memory.ts

import type { Tracer } from "../trace";/** The words a process gets; the picture is small enough to read every one. */export const MEMORY_SIZE = 32;export const MAX_OPERATIONS = 48;/** What a script asks the memory to do, one operation at a time. */export type MemoryOperation =  | { kind: "call"; name: string; locals: number }  | { kind: "return" }  | { kind: "alloc"; id: string; size: number }  | { kind: "free"; id: string };export interface Frame {  name: string;  /** The frame's lowest address; it holds the return address and the locals above it. */  base: number;  size: number;}export interface HeapBlock {  /** Null for a free block. */  id: string | null;  address: number;  size: number;}export interface MemoryReport {  operations: number;  frames: Frame[];  heap: HeapBlock[];  stackTop: number;  heapTop: number;  /** Why the script stopped early, or null. */  fault: string | null;  /** Free heap words as a share of the heap's reach; blocks too small for the next request are what fragmentation means. */  freeWords: number;  largestFree: number;}/** * The memory of one running program, as every C compiler lays it out: * the code and the static data at the bottom, a heap above them that * grows upward as the program asks for blocks, and a stack at the top * that grows downward one frame per call. A call pushes a frame of the * return address plus the callee's locals and a return pops it, so the * stack is free of charge and never fragments. The heap is a first-fit * free list: an allocation takes the first free block big enough, * splitting off the rest, and a free gives the block back and merges * it with free neighbours. Blocks freed in a different order from * their allocation leave holes, and a request can fail with enough * free words in total but none in one place. When the stack reaches * the heap, the program has run out of memory. * * Time: O(blocks) per heap operation, O(1) per stack operation. * Space: MEMORY_SIZE words. */export class ProcessMemory {  private readonly frames: Frame[] = [];  private heap: HeapBlock[] = [];  private heapTop: number;  private stackTop = MEMORY_SIZE;  private operations = 0;  private fault: string | null = null;  constructor(    /** Words taken by the code and the static data at the bottom. */    readonly staticWords: number,    private readonly tracer?: Tracer,  ) {    if (!Number.isInteger(staticWords) || staticWords < 0 || staticWords >= MEMORY_SIZE) throw new RangeError(`static words must be in [0, ${MEMORY_SIZE})`);    this.heapTop = staticWords;  }  /** The owner of a word: "static", a frame by index, a heap block id, "free" inside the heap, or null in the gap. */  owner(address: number): string | null {    if (address < this.staticWords) return "static";    const frame = this.frames.findIndex((f) => address >= f.base && address < f.base + f.size);    if (frame !== -1) return `frame ${frame}`;    const block = this.heap.find((b) => address >= b.address && address < b.address + b.size);    if (block) return block.id ?? "free";    return null;  }  /** Applies the script in order, stopping at the first fault. */  run(script: readonly MemoryOperation[]): MemoryReport {    if (script.length > MAX_OPERATIONS) throw new RangeError(`${script.length} operations exceeds ${MAX_OPERATIONS}`);    for (const operation of script) {      if (this.fault) break;      this.apply(operation);    }    return this.report();  }  apply(operation: MemoryOperation): void {    this.operations++;    switch (operation.kind) {      case "call":        return this.call(operation.name, operation.locals);      case "return":        return this.pop();      case "alloc":        return this.alloc(operation.id, operation.size);      case "free":        return this.free(operation.id);    }  }  /** Pushes a frame: the return address and the locals, growing the stack downward. */  private call(name: string, locals: number): void {    const size = locals + 1;    const base = this.stackTop - size;    if (base < this.heapTop) {      this.fail(`stack overflow: ${name} needs ${size} words and only ${this.stackTop - this.heapTop} lie above the heap`);      return;    }    this.stackTop = base;    const frame: Frame = { name, base, size };    this.frames.push(frame);    // ▸ a call pushes a frame below the stack top: the return address and the callee's locals    this.tracer?.emit("call", { name, base, size, depth: this.frames.length, stackTop: this.stackTop, heapTop: this.heapTop });  }  /** Pops the top frame; the words are free again at no cost. */  private pop(): void {    const frame = this.frames.pop();    if (!frame) {      this.fail("return with no frame on the stack");      return;    }    this.stackTop = frame.base + frame.size;    // ▸ a return pops the top frame; its words are free again with no bookkeeping at all    this.tracer?.emit("return", { name: frame.name, base: frame.base, size: frame.size, depth: this.frames.length, stackTop: this.stackTop });  }  /** First fit: the first free block that is big enough, split if larger; otherwise grow the heap toward the stack. */  private alloc(id: string, size: number): void {    if (!Number.isInteger(size) || size < 1) throw new RangeError(`block ${id} must be at least one word`);    if (this.heap.some((block) => block.id === id)) throw new RangeError(`block ${id} is already allocated`);    const searched = this.heap.filter((block) => block.id === null).map((block) => block.size);    const index = this.heap.findIndex((block) => block.id === null && block.size >= size);    let block: HeapBlock;    let split = false;    if (index !== -1) {      const hole = this.heap[index]!;      const freeBlock = this.heap[index]!;      block = { id, address: hole.address, size };      block = { id, address: freeBlock.address, size };      const rest: HeapBlock[] = hole.size > size ? [{ id: null, address: hole.address + size, size: hole.size - size }] : [];      const rest: HeapBlock[] = freeBlock.size > size ? [{ id: null, address: freeBlock.address + size, size: freeBlock.size - size }] : [];      split = rest.length > 0;      this.heap.splice(index, 1, block, ...rest);    } else {      if (this.heapTop + size > this.stackTop) {        this.fail(`out of memory: ${id} needs ${size} words, ${this.freeWords()} are free in holes too small, and ${this.stackTop - this.heapTop} lie below the stack`);        return;      }      block = { id, address: this.heapTop, size };      this.heap.push(block);      this.heapTop += size;    }    // ▸ take the first hole that fits, splitting off the rest, or grow the heap toward the stack    this.tracer?.emit("alloc", { id, address: block.address, size, searched, reused: index !== -1, split, heapTop: this.heapTop, freeWords: this.freeWords() });  }  /** Marks a block free and merges it with free neighbours, so holes do not multiply. */  private free(id: string): void {    const index = this.heap.findIndex((block) => block.id === id);    if (index === -1) {      this.fail(`free of ${id}, which is not allocated`);      return;    }    const block = this.heap[index]!;    let start = index;    let end = index;    if (this.heap[index - 1]?.id === null) start--;    if (this.heap[index + 1]?.id === null) end++;    const merged = this.heap.slice(start, end + 1);    const neighboursJoined = this.heap.slice(start, end + 1);    const hole: HeapBlock = { id: null, address: merged[0]!.address, size: merged.reduce((sum, b) => sum + b.size, 0) };    const freeBlock: HeapBlock = { id: null, address: neighboursJoined[0]!.address, size: neighboursJoined.reduce((sum, b) => sum + b.size, 0) };    this.heap.splice(start, merged.length, hole);    this.heap.splice(start, neighboursJoined.length, freeBlock);    // A hole at the top of the heap gives the words back to the gap.    if (this.heap.at(-1)?.id === null) {      this.heapTop = this.heap.at(-1)!.address;      this.heap.pop();    }    // ▸ give the block back and merge it with any free neighbour, so holes do not multiply    this.tracer?.emit("free", { id, address: block.address, size: block.size, mergedWith: merged.length - 1, holeSize: hole.size, heapTop: this.heapTop, freeWords: this.freeWords() });    this.tracer?.emit("free", { id, address: block.address, size: block.size, mergedWith: neighboursJoined.length - 1, holeSize: freeBlock.size, heapTop: this.heapTop, freeWords: this.freeWords() });  }  private fail(message: string): void {    this.fault = message;    // ▸ the stack met the heap, the heap met the stack, or a return or free had nothing to act on    this.tracer?.emit("fault", { message, stackTop: this.stackTop, heapTop: this.heapTop, depth: this.frames.length });  }  private freeWords(): number {    return this.heap.filter((block) => block.id === null).reduce((sum, block) => sum + block.size, 0);  }  report(): MemoryReport {    const holes = this.heap.filter((block) => block.id === null);    return {      operations: this.operations,      frames: this.frames.map((frame) => ({ ...frame })),      heap: this.heap.map((block) => ({ ...block })),      stackTop: this.stackTop,      heapTop: this.heapTop,      fault: this.fault,      freeWords: this.freeWords(),      largestFree: holes.reduce((max, block) => Math.max(max, block.size), 0),    };  }}

operations =: 12
fault =: none

12 operations done: 1 frame left on the stack, 8 heap words in use with 0 free in holes, the largest hole 0.

import type { Tracer } from "../trace";/** The words a process gets; the picture is small enough to read every one. */export const MEMORY_SIZE = 32;export const MAX_OPERATIONS = 48;/** What a script asks the memory to do, one operation at a time. */export type MemoryOperation = | { kind: "call"; name: string; locals: number } | { kind: "return" } | { kind: "alloc"; id: string; size: number } | { kind: "free"; id: string };export interface Frame { name: string; /** The frame's lowest address; it holds the return address and the locals above it. */ base: number; size: number;}export interface HeapBlock { /** Null for a free block. */ id: string | null; address: number; size: number;}export interface MemoryReport { operations: number; frames: Frame[]; heap: HeapBlock[]; stackTop: number; heapTop: number; /** Why the script stopped early, or null. */ fault: string | null; /** Free heap words as a share of the heap's reach; blocks too small for the next request are what fragmentation means. */ freeWords: number; largestFree: number;}/** * The memory of one running program, as every C compiler lays it out: * the code and the static data at the bottom, a heap above them that * grows upward as the program asks for blocks, and a stack at the top * that grows downward one frame per call. A call pushes a frame of the * return address plus the callee's locals and a return pops it, so the * stack is free of charge and never fragments. The heap is a first-fit * free list: an allocation takes the first free block big enough, * splitting off the rest, and a free gives the block back and merges * it with free neighbours. Blocks freed in a different order from * their allocation leave holes, and a request can fail with enough * free words in total but none in one place. When the stack reaches * the heap, the program has run out of memory. * * Time: O(blocks) per heap operation, O(1) per stack operation. * Space: MEMORY_SIZE words. */export class ProcessMemory { private readonly frames: Frame[] = []; private heap: HeapBlock[] = []; private heapTop: number; private stackTop = MEMORY_SIZE; private operations = 0; private fault: string | null = null; constructor( /** Words taken by the code and the static data at the bottom. */ readonly staticWords: number, private readonly tracer?: Tracer, ) { if (!Number.isInteger(staticWords) || staticWords < 0 || staticWords >= MEMORY_SIZE) throw new RangeError(`static words must be in [0, ${MEMORY_SIZE})`); this.heapTop = staticWords; } /** The owner of a word: "static", a frame by index, a heap block id, "free" inside the heap, or null in the gap. */ owner(address: number): string | null { if (address < this.staticWords) return "static"; const frame = this.frames.findIndex((f) => address >= f.base && address < f.base + f.size); if (frame !== -1) return `frame ${frame}`; const block = this.heap.find((b) => address >= b.address && address < b.address + b.size); if (block) return block.id ?? "free"; return null; } /** Applies the script in order, stopping at the first fault. */ run(script: readonly MemoryOperation[]): MemoryReport { if (script.length > MAX_OPERATIONS) throw new RangeError(`${script.length} operations exceeds ${MAX_OPERATIONS}`); for (const operation of script) { if (this.fault) break; this.apply(operation); } return this.report(); } apply(operation: MemoryOperation): void { this.operations++; switch (operation.kind) { case "call": return this.call(operation.name, operation.locals); case "return": return this.pop(); case "alloc": return this.alloc(operation.id, operation.size); case "free": return this.free(operation.id); } } /** Pushes a frame: the return address and the locals, growing the stack downward. */ private call(name: string, locals: number): void { const size = locals + 1; const base = this.stackTop - size; if (base < this.heapTop) { this.fail(`stack overflow: ${name} needs ${size} words and only ${this.stackTop - this.heapTop} lie above the heap`); return; } this.stackTop = base; const frame: Frame = { name, base, size }; this.frames.push(frame); // ▸ a call pushes a frame below the stack top: the return address and the callee's locals this.tracer?.emit("call", { name, base, size, depth: this.frames.length, stackTop: this.stackTop, heapTop: this.heapTop }); } /** Pops the top frame; the words are free again at no cost. */ private pop(): void { const frame = this.frames.pop(); if (!frame) { this.fail("return with no frame on the stack"); return; } this.stackTop = frame.base + frame.size; // ▸ a return pops the top frame; its words are free again with no bookkeeping at all this.tracer?.emit("return", { name: frame.name, base: frame.base, size: frame.size, depth: this.frames.length, stackTop: this.stackTop }); } /** First fit: the first free block that is big enough, split if larger; otherwise grow the heap toward the stack. */ private alloc(id: string, size: number): void { if (!Number.isInteger(size) || size < 1) throw new RangeError(`block ${id} must be at least one word`); if (this.heap.some((block) => block.id === id)) throw new RangeError(`block ${id} is already allocated`); const searched = this.heap.filter((block) => block.id === null).map((block) => block.size); const index = this.heap.findIndex((block) => block.id === null && block.size >= size); let block: HeapBlock; let split = false; if (index !== -1) { const hole = this.heap[index]!; const freeBlock = this.heap[index]!; block = { id, address: hole.address, size }; block = { id, address: freeBlock.address, size }; const rest: HeapBlock[] = hole.size > size ? [{ id: null, address: hole.address + size, size: hole.size - size }] : []; const rest: HeapBlock[] = freeBlock.size > size ? [{ id: null, address: freeBlock.address + size, size: freeBlock.size - size }] : []; split = rest.length > 0; this.heap.splice(index, 1, block, ...rest); } else { if (this.heapTop + size > this.stackTop) { this.fail(`out of memory: ${id} needs ${size} words, ${this.freeWords()} are free in holes too small, and ${this.stackTop - this.heapTop} lie below the stack`); return; } block = { id, address: this.heapTop, size }; this.heap.push(block); this.heapTop += size; } // ▸ take the first hole that fits, splitting off the rest, or grow the heap toward the stack this.tracer?.emit("alloc", { id, address: block.address, size, searched, reused: index !== -1, split, heapTop: this.heapTop, freeWords: this.freeWords() }); } /** Marks a block free and merges it with free neighbours, so holes do not multiply. */ private free(id: string): void { const index = this.heap.findIndex((block) => block.id === id); if (index === -1) { this.fail(`free of ${id}, which is not allocated`); return; } const block = this.heap[index]!; let start = index; let end = index; if (this.heap[index - 1]?.id === null) start--; if (this.heap[index + 1]?.id === null) end++; const merged = this.heap.slice(start, end + 1); const neighboursJoined = this.heap.slice(start, end + 1); const hole: HeapBlock = { id: null, address: merged[0]!.address, size: merged.reduce((sum, b) => sum + b.size, 0) }; const freeBlock: HeapBlock = { id: null, address: neighboursJoined[0]!.address, size: neighboursJoined.reduce((sum, b) => sum + b.size, 0) }; this.heap.splice(start, merged.length, hole); this.heap.splice(start, neighboursJoined.length, freeBlock); // A hole at the top of the heap gives the words back to the gap. if (this.heap.at(-1)?.id === null) { this.heapTop = this.heap.at(-1)!.address; this.heap.pop(); } // ▸ give the block back and merge it with any free neighbour, so holes do not multiply this.tracer?.emit("free", { id, address: block.address, size: block.size, mergedWith: merged.length - 1, holeSize: hole.size, heapTop: this.heapTop, freeWords: this.freeWords() }); this.tracer?.emit("free", { id, address: block.address, size: block.size, mergedWith: neighboursJoined.length - 1, holeSize: freeBlock.size, heapTop: this.heapTop, freeWords: this.freeWords() }); } private fail(message: string): void { this.fault = message; // ▸ the stack met the heap, the heap met the stack, or a return or free had nothing to act on this.tracer?.emit("fault", { message, stackTop: this.stackTop, heapTop: this.heapTop, depth: this.frames.length }); } private freeWords(): number { return this.heap.filter((block) => block.id === null).reduce((sum, block) => sum + block.size, 0); } report(): MemoryReport { const holes = this.heap.filter((block) => block.id === null); return { operations: this.operations, frames: this.frames.map((frame) => ({ ...frame })), heap: this.heap.map((block) => ({ ...block })), stackTop: this.stackTop, heapTop: this.heapTop, fault: this.fault, freeWords: this.freeWords(), largestFree: holes.reduce((max, block) => Math.max(max, block.size), 0), }; }}