Stack vs heap

A value read back wrong after the function that owned it returned. A crash that says “stack overflow” with no obvious recursion anywhere. Both are the same misunderstanding about where a thing lives and how long it is allowed to live there. Both trace to the same fork in how a program is allowed to ask for memory — and once you see the fork, both stop being mysterious.

Why the stack is one instruction#

Every thread gets its own stack — a fixed region of memory handed to it at creation, not shared with any other thread. Call a function, and the compiler already knows, at compile time, exactly how much room its local variables need: it wrote the function, it counted the bytes. So a call does not search for space; it moves the stack pointer down by that known amount, and the moved-to region is the new frame. Return, and the pointer moves back up by the same amount. That is the entire allocation and the entire deallocation, and it is why “stack allocation is free” is close to true rather than a slogan — on most architectures it is one arithmetic instruction adjusting a register, and while the exact instruction count is not architecture-independent, the shape of the cost is the same everywhere: no search, no bookkeeping, no decision.

Nothing on the stack can leak, and this is the mechanism, not a design promise someone has to keep. A frame’s memory is reclaimed the moment its function returns, unconditionally — there is no code path where the pointer fails to move back, no object to forget to release. The trade for that guarantee is that the frame’s lifetime is fixed the moment the function is called: it cannot outlive the call, no matter what the function does inside it.

What the heap buys with that search#

The heap exists for exactly the case the stack cannot cover: a value whose lifetime is not known until the program is running — decided by user input, by how long a connection stays open, by whichever caller happens to hold onto it longest. Since the compiler cannot work that lifetime out in advance, it cannot just move a pointer by a fixed amount and call the space claimed. Something has to track which regions of the heap are currently free, find one that fits the request, and mark it used. That something is the allocator, and the cost of a heap allocation is really the cost of whichever allocator is running underneath it.

That cost is not one number. A bump allocator that never frees individual objects is almost as cheap as a stack push. A size-class allocator keeps separate free lists per size band, so a common-sized request is close to a lookup, not a scan. What does real work is a general-purpose allocator juggling many live, differently sized objects at once — walking or indexing a free list to find a block that fits, sometimes splitting a larger block to make one, sometimes discovering that nothing fits even though the total free space would be enough, because it is scattered into pieces too small individually. That scattering is fragmentation, and it is a cost the stack structurally cannot incur, because nothing on the stack is ever freed out of order. The layout you hand the allocator is also a choice, not a given — a deque’s fixed-size blocks are a concrete case of choosing a memory layout for the access pattern instead of one contiguous array, so the structure asks the allocator for many small, uniform pieces instead of one that grows and gets copied.

Freeing has the mirror problem. Someone has to decide when a heap value’s lifetime is over. In C that someone is you, explicitly, and forgetting is a leak — memory the allocator still considers used, forever, because nothing ever told it otherwise. A garbage collector changes who makes that call and when, tracing what is still reachable and reclaiming the rest, but it changes only the “who frees” question. The value still lives on the heap for exactly the same reason it always did: its lifetime outruns any single function’s frame, and a collector does not move it onto the stack just because it is now the one doing the bookkeeping.

Picking one on purpose#

The failure that actually reaches production is a function that returns a pointer or reference to one of its own local variables. It compiles, and it can even seem to work the first few times you call it, which is what makes it dangerous. The moment the function returns, its frame is gone — the stack pointer has already moved back, and that memory is not reserved for anyone. The very next call, from anywhere in the program, gets a frame that overlaps the same addresses, and writes its own locals into them. Read through the old pointer after that and you get whatever the next call happened to leave there: sometimes a plausible-looking number, sometimes garbage, sometimes — if the layouts line up unluckily — the value you actually wanted, which is the worst outcome of all, because it means the bug passed your test.

This is why the bug is so hard to pin down: it does not depend on the value being wrong in some obvious way, it depends on the exact sequence of calls that happens to run after the dangling pointer is created. Change what gets called next — add a log line, reorder two functions, run the test suite in a different order — and a different frame lands on that memory, so the garbage you read back changes or disappears entirely. A bug that reproduces on Tuesday and not on Wednesday, with no code change in between, is worth checking for exactly this before anything more exotic.

The same ceiling that makes the stack fast is also the one hard limit it has: it is a fixed region, and a function that recurses too deep, or keeps too large a local buffer, runs off the end of it and crashes rather than growing to fit. One traversal order rewrites its recursive call as an explicit stack on the heap, because the call stack has a ceiling and a heap-backed one does not.