Memory Layout: Stack vs Heap — CS50 Deep Dive

"You already learned how to measure how much memory an algorithm uses. Now let's see where that memory lives — and why the place matters."

You're coming from the Algorithm Efficiency unit where we analyzed time and space complexity and practiced recursive solutions. Good — because recursion and space complexity are the perfect launchpad for this: recursion lives on the stack, and dynamic data structures usually live on the heap. Understanding the physical memory layout will stop a lot of baffling bugs and make your programs more robust.

Why this matters (TL;DR)

• The stack is fast, structured, and scoped to functions — perfect for short-lived and small allocations (local variables, return addresses, parameters).
• The heap is flexible and large — perfect for variable-size and long-lived allocations using pointers (malloc/free in C).
• Mistakes cause common runtime errors: stack overflow, heap fragmentation, memory leaks, use-after-free, and dangling pointers.

If you enjoyed analyzing space complexity, consider this the physical reality check: Big-O tells you how much memory your algorithm needs; stack vs heap tells you where that memory will physically be allocated and what can go wrong.

The two neighborhoods of memory: quick tour

The Stack (the neat dormitory)

• What it is: A contiguous block of memory that grows/shrinks as functions are called/return.
• Allocations: Deterministic and automatic — local variables and function call metadata (return address, saved registers, etc.).
• Lifetime: Lifetime = scope. Once the function returns, the stack frame vanishes.
• Speed: Very fast (LIFO allocation) with little bookkeeping.
• Limitations: Size is limited (often a few MB for a program). Deep recursion or large local arrays can overflow it.

The Heap (the messy apartment complex)

• What it is: A larger region of memory for dynamic allocations. Managed by malloc/realloc/free in C (or new/delete in C++), or by the runtime/GC in managed languages.
• Allocations: Flexible size at runtime, but slower to allocate and free. Can become fragmented.
• Lifetime: Controlled by the programmer (or garbage collector). Survives after the allocating function returns.
• Limitations: Slower, requires explicit free in C, mistakes lead to leaks or invalid access.

Micro explanation: how a recursive function uses the stack

Imagine a recursive factorial function in C:

int factorial(int n) {
    if (n <= 1) return 1;
    int local = n; // stored on stack
    return local * factorial(n - 1);
}

Each call gets its own stack frame (parameters, return address, local local). If n is large (or recursion is deep), you create many frames until the stack limit — boom: stack overflow. This is a direct link to the Time–Space Trade-offs topic: recursion can be elegant but may blow the stack if not managed.

Example contrast: stack vs heap allocation in C

Local (stack) allocation:

void foo() {
    int arr[100000]; // large! may overflow the stack
    // arr is automatically freed on return
}

Heap allocation:

void bar() {
    int *arr = malloc(100000 * sizeof(int));
    if (!arr) return; // check for allocation failure
    // use arr
    free(arr); // programmer must remember this
}

When the array is big or you don't know the size at compile time (e.g., reading a file of unknown length), prefer the heap. When the data is small and short-lived, the stack is simpler.

Common real-world scenarios and pitfalls

• Stack overflow from recursion: Deep recursion (or accidentally infinite recursion) consumes stack frames until the program crashes. If you find recursion causing crashes in empirical benchmarking, consider iterative solutions or increase stack (not always safe).

• Buffer overflow on stack: Writing past the end of a local array overwrites the stack frame and can corrupt return addresses (security bug). Example: strcpy into a fixed-size char buffer without bounds checking.

• Memory leaks on heap: Forgetting to free memory after malloc means your program holds onto memory unnecessarily. In long-running programs (or during repeated empirical tests), leaks skew memory usage measurements.

• Use-after-free / Dangling pointers: Freeing memory and then still using the pointer is undefined behavior. Always set pointers to NULL after freeing when appropriate.

• Fragmentation: Frequent malloc/free of differently sized blocks can fragment the heap, causing allocations to fail even though total free memory would be enough.

File I/O + Memory: Why heap matters for files

When reading files, you often don't know the file size beforehand. You have choices:

• Read into a fixed-size stack buffer (risky for large files).
• Use the heap: allocate a buffer dynamically, possibly using realloc as you discover more bytes.

Example pattern in C:

char *buf = NULL;
size_t len = 0, cap = 0;
int c;
while ((c = fgetc(fp)) != EOF) {
    if (len + 1 >= cap) {
        cap = cap ? cap * 2 : 64;
        buf = realloc(buf, cap);
    }
    buf[len++] = c;
}
if (buf) buf[len] = '\0';
// ... use buf ...
free(buf);

This approach avoids stack overflow and supports arbitrarily large files (limited by memory), but remember to free the memory and check for allocation failure.

Quick diagnostics and tools

• Use valgrind (or ASAN) to detect memory leaks, invalid reads/writes, and use-after-free.
• During empirical benchmarking, track peak memory usage (resident set size) to see if heap grows unexpectedly.
• Print recursion depth or use a debugger to visualize stack frames for deep calls.

Pro tip: If your program crashes only on large inputs, ask "am I hitting stack limits?" before assuming it's an algorithm bug.

Comparison table (at-a-glance)

Key takeaways

• Stack = automatic, fast, limited, scoped. Great for small, short-lived data and for understanding recursion's cost in real memory.
• Heap = flexible, larger, slower, manual bookkeeping. Use when sizes are unknown at compile time or when data must outlive a function call.
• Always pair malloc with free in C; watch for leaks and use-after-free bugs.
• When profiling memory (empirical benchmarking), check whether memory growth comes from recursion (stack) or repeated heap allocations.

Final memorable insight

"Think of the stack as your desk where you do work — everything on it is temporary and neatly piled. The heap is the storage room — you can put stuff there for as long as you want, but you must remember where you put it and eventually clean it up. Lose track and the storage room becomes a hoarder’s nightmare."

If you want, I can give you a short hands-on lab: three small C programs demonstrating stack overflow, a safe heap-read file example, and a valgrind walkthrough — pick one and we'll code it together.