Appearance
3.4 — Memory in Languages
3.3 settled what a value is. This chapter settles where it lives and who cleans it up — a question with more practical consequence than almost any other in language design. It determines whether your program can crash in bizarre ways, whether it pauses unpredictably, whether it leaks memory over days of uptime, and how hard it is to write correct concurrent code.
You already have the foundation. 2.2 showed every process's memory divided into stack and heap; 2.5 showed the OS handing out pages and a user-space allocator carving them into small pieces. What Part 2 didn't answer is the language-level question: when your code creates an object, which region does it go in, and — the hard part — when is it safe to free it? Getting that wrong causes the two most notorious bug classes in software history. This chapter builds the three families of answer — manual management, reference counting, and tracing garbage collection — plus the newer fourth way, Rust's ownership, which solves it at compile time with no runtime cost at all.
1. Stack vs heap: two regions, two lifetimes
Recall the process memory layout from 2.2. Two regions hold your data, and the difference is not arbitrary — it follows from how long the data needs to live.
The stack holds data whose lifetime is tied to a function call. Every time a function is called, a stack frame is pushed containing its parameters and local variables; when the function returns, that frame is popped and the space is instantly reclaimed. This is why the stack is so fast: allocation is just moving a pointer down, deallocation is moving it back up — a single instruction each, no bookkeeping, and the memory is always hot in cache (1.6) because you keep reusing the same region. But it comes with two hard constraints: the size must generally be known at compile time, and the data cannot outlive the function that created it — once the frame pops, that memory belongs to the next call.
The heap exists for everything that can't obey those constraints: data whose size is decided at runtime (a list that grows), or whose lifetime must outlast the function that created it (an object you build in one function and return for use elsewhere). The heap is a large pool from which you request arbitrary-size blocks at arbitrary times, managed by the allocator (2.5). That flexibility costs: allocation must search for a suitable free block, blocks scatter (hurting locality), and — crucially — nothing automatically reclaims heap memory when you stop using it. Someone must decide when it's free. That decision is the entire subject of this chapter.
2. Manual management, and the two catastrophes
The original approach, still used by C and C++, is simply: you decide. You call malloc (or new) to allocate and free (or delete) when you're finished. Maximum control, zero overhead, completely predictable — and the source of two of the worst bug classes in computing history, because getting it exactly right across a large program is genuinely beyond human reliability.
Free too late (or never) → a memory leak. You allocate but never free. Each leak is small, so nothing breaks immediately — but a server running for weeks accumulates them until it exhausts memory and either crashes or drives the machine into thrashing (2.5). Leaks are insidious precisely because the program passes every test; the failure emerges only under sustained uptime.
Free too early → a dangling pointer and use-after-free. You free memory while some other part of the program still holds a pointer (1.6) to it. That pointer now references memory the allocator considers free and may hand to someone else. Reading it returns garbage; writing to it silently corrupts whatever now lives there. The bug typically manifests far away, much later, as inexplicable corruption — a debugging nightmare. Worse, it's a security catastrophe: use-after-free is one of the most exploited vulnerability classes in the world, because an attacker who can control what gets allocated into the freed slot may hijack the program's behaviour (Part 8). Freeing the same pointer twice (a double free) corrupts the allocator's own bookkeeping similarly.
Microsoft and Google have each reported that around 70% of their serious security vulnerabilities stem from memory-safety errors of this kind. That figure is why the industry cares so much about the alternatives below, and why the US government has publicly urged migration to memory-safe languages. The problem was never that C programmers are careless; it's that manual memory management asks humans to maintain a global invariant across every path in a large program — and humans reliably fail at that.
3. Reference counting: free it when nobody's looking
The first automatic approach is delightfully simple. Give every heap object a counter recording how many references point to it. Increment when a new reference is made, decrement when one goes away, and when the count hits zero, nothing can reach the object, so free it immediately. This is reference counting, used by Python (as its primary mechanism), Swift (as ARC — Automatic Reference Counting), and C++'s shared_ptr.
Its virtues are real: reclamation is immediate and deterministic (memory is freed the instant the last reference drops — no waiting), the cost is spread evenly with no long pauses, and the implementation is simple to reason about.
But it has one famous, fatal flaw: reference cycles. Suppose object A holds a reference to B, and B holds a reference back to A — a parent pointing to a child that points back to its parent. Now remove every external reference to both. They're unreachable — no code can ever touch them again — yet each still has a count of 1, because they reference each other. Neither count reaches zero, so neither is ever freed: a permanent leak that the mechanism cannot detect by construction.
There are two responses. Ask the programmer to break cycles manually using weak references (a reference that does not increment the count — used for back-pointers precisely to avoid cycles; Swift takes this route). Or add a second, cycle-detecting collector that occasionally scans for unreachable groups — which is exactly what Python does: reference counting handles the common case immediately, plus a generational cycle collector cleans up the rest. Reference counting also carries a quieter cost: every reference assignment must update a counter, and in multithreaded code those updates must be atomic (2.4), which is genuinely expensive — a significant part of why Python's Global Interpreter Lock has been so hard to remove.
4. Tracing garbage collection: find what's reachable, sweep the rest
The dominant approach in Java, C#, Go, and JavaScript attacks the problem from the opposite direction. Rather than tracking counts continuously, a tracing garbage collector periodically asks a global question: which objects can the program still reach?
It starts from the roots — the places a program can begin any access: local variables on the stack, global variables, CPU registers. From these it traverses every reference, marking each object it can reach, then every object those reference, and so on — a graph traversal (Chapter 4.19). Anything still unmarked at the end is, by definition, unreachable by any possible execution, and is therefore garbage that can be freed. This is the classic mark-and-sweep algorithm: mark everything reachable, sweep (free) everything else.
Notice the crucial property this buys: reachability is the correct definition of "still needed," and it handles cycles automatically. Our A↔B cycle is simply never reached from the roots, so it's never marked, so it's swept. That's why tracing GC displaced reference counting as the default for major runtimes.
Two refinements make it practical:
The generational hypothesis. Empirically, most objects die young — a huge share of allocations (temporary strings, intermediate results, short-lived request objects) become garbage almost immediately, while objects that survive a while tend to keep surviving. So a generational collector splits the heap into a small "young" region and a larger "old" one. It collects the young region frequently and cheaply (it's small, and nearly everything in it is already dead, so there's little to copy), and promotes the rare survivors to the old region, which is collected rarely. This exploits a statistical regularity to make the common case cheap — the same instinct as caching (1.6).
Compaction. Many collectors, while collecting, also move surviving objects together to eliminate the gaps left by freed ones. This defeats fragmentation (heap free space broken into unusable slivers) and, as a bonus, improves locality — objects allocated together end up adjacent, so they share cache lines (1.6). It's why allocation in a compacting GC can be faster than malloc: with a contiguous free region, allocating is just bumping a pointer.
The cost — and it is the defining cost — is the stop-the-world pause. To trace the object graph safely, the collector must (at least briefly) stop the program, or the graph would change beneath it. A pause of a few milliseconds is invisible in a web service; a pause of hundreds of milliseconds is a disaster for a trading system, a game frame, or a latency-SLA API. Decades of engineering have gone into shrinking these pauses — concurrent collectors that do most work alongside the running program, incremental collectors that work in small slices, and modern low-latency collectors (Java's ZGC and Shenandoah, Go's concurrent collector) that keep pauses under a millisecond even on huge heaps. The trade-off is that pause-free collection costs throughput and complexity: you can optimise for latency or for total work, rarely both.
5. Ownership: solving it at compile time
Rust took a genuinely different path, and it's the most interesting development in this area in decades: what if the compiler could prove, without any runtime mechanism, exactly when each value should be freed?
Rust's ownership system rests on three rules enforced entirely at compile time (3.3's type checker doing heavy lifting):
- Every value has exactly one owner (a variable).
- When the owner goes out of scope, the value is dropped (freed) — automatically, at a point the compiler knows statically.
- Ownership can be moved to a new owner, or temporarily borrowed as a reference — and the borrow checker enforces that you may have either many simultaneous read-only borrows or exactly one mutable borrow, never both, and that no borrow may outlive the value it points to.
The consequences are remarkable. Because the compiler knows precisely where each value dies, it inserts the free automatically — no garbage collector, no reference counts, no runtime overhead whatsoever, and performance fully comparable to manual C. Yet the two catastrophes of section 2 become impossible: a use-after-free would require a reference outliving its value, which the borrow checker rejects at compile time, and double-frees can't happen because there's exactly one owner. Rust gets manual-management performance with automatic-management safety.
The price is real and worth stating plainly: the borrow checker imposes a genuine learning curve (the famous "fighting the borrow checker" phase), and some legitimate patterns — especially graph-like structures with cycles — become awkward, requiring explicit escape hatches (Rc for shared ownership, unsafe blocks for cases the compiler cannot verify). This is precisely 3.3's undecidability lesson in action: the checker must be conservative, so it rejects some correct programs. The bet Rust makes — that this upfront cost is worth eliminating an entire class of vulnerability and unpredictable pauses — has proven compelling for systems software, and its rules have the elegant side effect of also preventing data races (2.4), since "one mutable borrow at a time" is exactly the discipline shared-memory concurrency needs.
6. The expert lens
Memory management is a four-way trade between safety, performance, predictability, and how pleasant it is to use — you cannot maximise all four. Manual (C/C++): peak performance and full predictability, at the cost of safety and heavy cognitive burden. Reference counting (Python/Swift): deterministic and simple, but leaks cycles and taxes every assignment. Tracing GC (Java/Go/JS): safe and pleasant to use — you simply never think about it — at the cost of pauses, memory overhead (a GC heap typically needs ~2× the live data to run efficiently), and unpredictability. Ownership (Rust): safe and fast and predictable, paid for in learning curve and expressiveness. Every choice is a defensible point in that space, and the right one depends on whether your constraint is developer velocity, tail latency, memory budget, or attack surface. That framing — rather than "GC bad, Rust good" — is what a senior engineer brings to the question.
Garbage collection doesn't prevent memory leaks — it only prevents one kind. This surprises many engineers and is a genuine production trap. A GC frees unreachable objects, so if your program keeps a reference to something it no longer needs, it stays reachable and therefore never collected. The classic instances: an unbounded cache or map that only ever grows; an event listener or callback registered and never removed (the listener keeps the whole object graph alive); a long-lived collection accumulating request data. These are logical leaks — the memory is "in use" by the GC's definition but useless by yours, and the symptom is a service whose memory climbs steadily until it is OOM-killed (2.5/2.8). The diagnostic tool is a heap dump showing which objects dominate and — decisively — what still references them. So "we use a GC language, we can't leak" is false; you can't leak unreachable memory, which is a different and smaller promise.
The stack/heap decision is a performance lever you control. Because stack allocation is nearly free and heap allocation costs real work (allocator search, later collection, worse locality), reducing heap traffic is one of the most reliable optimisations in GC languages: fewer allocations means fewer collections, shorter pauses, better cache behaviour. This is why performance-sensitive Go and Java code cares about escape analysis (the compiler proving a value doesn't outlive its function, so it can live on the stack instead of the heap), why object pooling and reusing buffers appear in hot paths, and why value types (structs) versus reference types matters. Recognising "this hot loop allocates per iteration" is a high-value habit — it connects 1.6's locality lesson directly to language choice.
Next chapter: we've covered how programs are translated, typed, and how their memory is managed — the machinery. Chapter 3.5 turns to how programs are organised: the paradigms (imperative, object-oriented, functional, declarative) that shape how you decompose a problem in the first place.
Recall
- The stack holds call-scoped data: push/pop with each call, instant and cache-friendly, but fixed-size and cannot outlive its function. The heap holds data of runtime-decided size or longer lifetime — flexible, but someone must decide when to free it.
- Manual (C/C++): free too late → memory leak; free too early → dangling pointer/use-after-free (a top security-vulnerability class — ~70% of serious CVEs at Microsoft/Google are memory-safety bugs).
- Reference counting (Python, Swift ARC) frees the instant the count hits zero — deterministic and pause-free, but cannot reclaim reference cycles (fixed by weak references or an added cycle collector) and taxes every assignment (atomically, in threaded code).
- Tracing GC (Java, C#, Go, JS) traverses from roots to find reachable objects and frees the rest (mark-and-sweep) — cycles handled automatically. Refined by generational collection (most objects die young) and compaction (defeats fragmentation, improves locality). Cost: stop-the-world pauses and memory overhead.
- Ownership (Rust) proves lifetimes at compile time: one owner, freed at scope end, with a borrow checker allowing many readers or one writer. Result: no GC, no overhead, and use-after-free/double-free are impossible — paid for in learning curve and rejected-but-valid programs.
Self-test: Why is stack allocation so much cheaper than heap allocation? Name the two failure modes of manual memory management and their consequences. Why can't reference counting free a cycle, and how does tracing GC handle it? What does "most objects die young" buy a collector? Why can a garbage-collected program still leak memory?
Quiz Bank
FoundationalWhat is the difference between the stack and the heap, and when does data go on each?
The stack stores data tied to a function call: each call pushes a stack frame of parameters and locals, popped automatically on return. It's extremely fast (allocation = moving a pointer; always cache-hot) but the size must generally be known at compile time and the data cannot outlive its function. The heap stores data whose size is decided at runtime or whose lifetime must exceed the creating function (objects you return or share). It's flexible but slower (the allocator must find a block), fragments, hurts locality — and critically, nothing reclaims it automatically, so the language must define who frees it.
FoundationalWhat are the two failure modes of manual memory management?
Freeing too late or never → a memory leak: allocated memory is never returned, so a long-running process steadily consumes more until it exhausts memory, crashes, or drives the machine into thrashing. Insidious because tests pass; failure needs uptime. Freeing too early → a dangling pointer / use-after-free: memory is freed while another pointer still references it; reading gives garbage, writing corrupts whatever occupies that space now, and the symptom appears far from the cause. It's also a top security-vulnerability class (an attacker controlling the reused allocation can hijack execution). Freeing twice (double free) similarly corrupts allocator bookkeeping. Roughly 70% of serious vulnerabilities at Microsoft and Google trace to memory-safety errors like these.
AppliedHow does reference counting work, and what is its fatal flaw?
Each heap object carries a count of how many references point to it; the count increments when a reference is created and decrements when one goes away, and the object is freed the moment the count hits zero. Advantages: immediate, deterministic reclamation and no long pauses (Python, Swift ARC, C++ shared_ptr). The fatal flaw is reference cycles: if A references B and B references A, then after all external references are dropped both remain unreachable yet each keeps the other's count at 1, so neither is ever freed — a leak the mechanism cannot detect by construction. Remedies: weak references (don't increment the count — used for back-pointers) or a supplementary cycle-detecting collector (Python's approach). A further cost is that every reference assignment updates a counter — atomically in multithreaded code, which is expensive.
AppliedHow does a tracing garbage collector decide what to free, and why does it handle cycles?
It periodically determines reachability. Starting from the roots (stack locals, globals, registers), it traverses every reference, marking each object it can reach, then everything those reach, transitively. Anything unmarked cannot be accessed by any future execution, so it's garbage and is swept (freed) — the mark-and-sweep algorithm. Cycles are handled automatically because reachability, not counting, is the criterion: an isolated A↔B cycle is simply never reached from the roots, so it's never marked and gets collected. This correctness advantage is why tracing GC became the default in Java, C#, Go, and JavaScript.
InterviewWhat is generational garbage collection and what observation motivates it?
It's motivated by the generational hypothesis: empirically, most objects die young — the large majority of allocations (temporaries, intermediate results, per-request objects) become garbage almost immediately, while objects that survive tend to keep surviving. So a generational collector splits the heap into a small young generation and a larger old one. The young generation is collected frequently and cheaply (it's small and nearly everything in it is already dead, so little must be copied), and rare survivors are promoted to the old generation, which is collected infrequently. This makes the common case cheap by exploiting a statistical regularity — the same instinct as caching. Most collectors also compact survivors together, eliminating fragmentation and improving locality.
InterviewExplain Rust's ownership model and what it eliminates.
Rust enforces memory safety entirely at compile time via three rules: (1) every value has exactly one owner variable; (2) when the owner leaves scope the value is dropped (freed) at a point the compiler knows statically; (3) ownership may be moved, or the value temporarily borrowed — with the borrow checker permitting either many simultaneous immutable borrows or exactly one mutable borrow, and forbidding any borrow that outlives its value. Because lifetimes are known statically, the compiler inserts frees automatically: no garbage collector, no reference counts, no runtime overhead, with C-comparable performance — while use-after-free and double free become impossible to express. The same "one writer or many readers" rule also prevents data races. Costs: a real learning curve, and some valid patterns (notably cyclic/graph structures) are rejected and need escape hatches (Rc, unsafe) — the conservatism every type checker must have.
StaffA Java service's memory climbs steadily over days until it's OOM-killed, yet it uses a garbage collector. How is this possible and how would you diagnose it?
It's possible because a GC only reclaims unreachable objects — it does not know what you no longer need. If the program retains a reference to something useless, it stays reachable and is never collected: a logical leak. The usual culprits: an unbounded cache or Map that only grows (no eviction/TTL — 1.6); listeners/callbacks registered and never deregistered (each keeps its whole captured object graph alive); a long-lived static collection accumulating per-request data; or ThreadLocals in a pooled-thread environment never cleared. Diagnosis: (1) confirm the pattern — monitor heap after full GC over time; a rising floor (not just sawtooth) means genuine retention, not normal churn; (2) take a heap dump at a high point and analyse it (Eclipse MAT, VisualVM) — look at the dominator tree to find which few objects retain the most memory, then examine the GC roots path showing what still references them, which usually names the offending cache/listener directly; (3) corroborate with allocation profiling if the growth is churn-driven.
Fixes follow from the cause: bound the cache with a size limit/eviction policy or TTL, deregister listeners (or use weak references so the registry doesn't retain), clear thread-locals, and add a regression test or a memory alert. The staff framing to state explicitly: "we use a GC" guarantees you cannot leak unreachable memory — a much narrower promise than "we cannot leak," and unbounded retention is a design bug the collector is powerless to fix.
Flashcards
FlashStack vs heap in one line each
Stack: call-scoped, push/pop, instant and cache-hot, can't outlive its function. Heap: runtime-sized or longer-lived, flexible but must be explicitly reclaimed.
FlashMemory leak vs use-after-free
Leak = freed too late/never (memory grows until exhaustion). Use-after-free = freed too early while a pointer remains (corruption; major security vulnerability class).
FlashReference counting's fatal flaw
Reference cycles: A↔B keep each other's count at 1 though unreachable, so they're never freed. Fixed by weak references or a cycle collector.
FlashMark-and-sweep
Trace from the roots (stack, globals, registers) marking everything reachable; free everything unmarked. Handles cycles automatically.
FlashGenerational hypothesis
Most objects die young — so collect a small young generation often and cheaply, promoting rare survivors to a rarely-collected old generation.
FlashStop-the-world pause
The GC must briefly halt the program to trace safely; pause length is the defining cost, attacked by concurrent/incremental collectors (ZGC, Shenandoah, Go).
FlashRust ownership rules
One owner per value; dropped at scope end; borrow as many readers OR one writer, never outliving the value. Compile-time safety with zero runtime cost.
Scenario Drill
DrillYou're choosing a language for (a) a high-frequency trading engine with a hard 1 ms latency budget, and (b) a typical CRUD web API. Use this chapter to justify different answers.
The decisive factor is whether unpredictable pauses are tolerable, which is exactly the axis memory management sits on. (a) Trading engine: a hard 1 ms budget makes a tracing GC risky — even well-tuned collectors can introduce stop-the-world pauses, and a pause exceeding the budget is a failure, not a slowdown; worse, pauses are load-dependent, so they strike hardest under exactly the volatile conditions that matter. That argues for Rust (ownership: no GC, no pauses, C-level performance, and memory safety retained — the reason it's increasingly used in this space) or C++ (peak control, accepting the memory-safety burden and its ~70%-of-vulnerabilities risk). If the team is committed to the JVM, the honest path is a low-latency collector (ZGC/Shenandoah, sub-millisecond pauses)
plus allocation discipline — minimising heap churn, pooling/reusing buffers, and using escape analysis and value types so hot paths allocate little — because the cheapest collection is the one you never trigger. (b) CRUD API: latency budgets are tens of milliseconds and the bottleneck is I/O (network, database — 2.7), not CPU or GC. A few milliseconds of GC pause is invisible against a 20 ms database round-trip, so the tracing GC languages (Java, C#, Go, TypeScript/Node) are ideal: you trade an irrelevant amount of latency for a large gain in developer velocity and memory safety — no manual lifetimes, no borrow checker, faster iteration, a bigger hiring pool, and richer web ecosystems. The staff framing:
pick the memory-management model by your latency and safety constraints, not by fashion — GC's cost is real but usually irrelevant next to I/O, while for hard-real-time paths that same cost is disqualifying. Note too that (b) still requires vigilance about logical leaks (unbounded caches), which no collector prevents.