Heap Allocation: Dynamic Memory Management

Introduction to Heap Memory

Think of the heap as a large warehouse where your program can rent storage space of any size, at any time, and keep it for as long as needed. Unlike the stack — which works like a neat pile of trays where you can only add or remove from the top — the heap is more like a parking lot where cars can arrive and leave in any order, and you need a system to track which spaces are occupied.

In compiler design, understanding heap allocation matters because the compiler must generate code that correctly manages dynamically allocated memory. When you write int *arr = malloc(100 * sizeof(int)) in C, the compiler generates instructions to call the runtime memory allocator, which finds a suitable block in the heap and returns its address. The compiler must ensure that every allocation is eventually paired with a deallocation, or provide automatic garbage collection.

Why We Need the Heap

The stack is fast and automatic, but it has critical limitations. Stack memory is tied to function lifetimes — when a function returns, all its local variables disappear. But what if you need data to outlive the function that created it? What if you do not know the size at compile time? What if you need to share data between unrelated parts of your program?

Consider this scenario: a function reads a file and returns its contents. The file could be 100 bytes or 100 megabytes — you cannot allocate a fixed-size array on the stack. You need dynamic allocation:

How Heap Allocation Works Internally

When your program calls malloc(n), the memory allocator must find a contiguous block of at least n bytes in the heap. The allocator maintains metadata about which regions are free and which are occupied. Common allocation strategies include:

First Fit: Scan the free list from the beginning and use the first block large enough. Fast but can lead to fragmentation at the start of the heap.

Best Fit: Search the entire free list and use the smallest block that fits. Reduces wasted space but is slower and can create many tiny unusable fragments.

Worst Fit: Use the largest available block. Counterintuitively, this can reduce fragmentation by leaving larger remaining pieces that are still usable.

Here is a simplified view of heap operations over time:

Manual Memory Management (C/C++)

In languages like C, the programmer is responsible for both allocation and deallocation:

Manual management gives maximum control but introduces dangerous bugs:

Memory Leak — Forgetting to call free(). The memory remains allocated but inaccessible, slowly consuming available heap space until the program crashes or the system runs out of memory.

Use-After-Free — Accessing memory after calling free(). The memory might have been reassigned to another allocation, leading to data corruption that is extremely difficult to debug.

Double Free — Calling free() twice on the same pointer. This corrupts the allocator's internal data structures, potentially allowing security exploits.

Buffer Overflow — Writing beyond the allocated size. This corrupts adjacent heap blocks, causing seemingly random crashes elsewhere in the program.

Automatic Memory Management (Garbage Collection)

Languages like Java, Python, Go, and JavaScript use garbage collection to automatically reclaim unused memory. The programmer only allocates — deallocation happens automatically when objects become unreachable:

Garbage Collection Algorithms

Reference Counting

Each object maintains a counter tracking how many references point to it. When the counter drops to zero, the object is immediately freed.

Advantage: Immediate reclamation, predictable pauses. Disadvantage: Cannot handle circular references. If A references B and B references A, both have refcount of 1 even when neither is reachable from the program.

Mark-and-Sweep

This algorithm works in two phases. First, starting from root references (global variables, stack variables), it traverses all reachable objects and marks them. Then it sweeps through the entire heap, freeing any unmarked objects.

Advantage: Handles circular references correctly. Disadvantage: Requires "stop-the-world" pauses during collection.

Generational Garbage Collection

Based on the empirical observation that most objects die young (the "generational hypothesis"), this approach divides the heap into generations:

This is the approach used by the JVM (Java), .NET (C#), and V8 (JavaScript). It dramatically reduces GC pause times because most collections only scan the small young generation.

Fragmentation and Compaction

Over time, repeated allocation and deallocation creates fragmentation — scattered small free blocks that individually are too small to satisfy large requests, even though their total size would suffice:

Compaction solves this by moving live objects together, creating one large contiguous free region. However, compaction requires updating all pointers to moved objects, which adds complexity.

Compiler's Role in Heap Management

The compiler generates code to interact with the heap allocator. For new or malloc expressions, it emits a function call to the runtime allocator. For garbage-collected languages, the compiler also inserts write barriers — small code snippets that notify the GC when a reference field changes, enabling efficient generational collection.

The compiler must also ensure that object sizes and layouts are correctly computed, accounting for alignment requirements (many architectures require data to be stored at addresses that are multiples of 4 or 8 bytes).

Key Takeaways

Heap allocation provides the flexibility that stack allocation cannot — dynamic sizes, arbitrary lifetimes, and shared ownership. However, this flexibility comes with costs: slower allocation, potential fragmentation, and the burden of memory management (either manual or through garbage collection). Understanding these tradeoffs helps you appreciate why different languages make different choices, and why the compiler must generate careful code to manage the heap correctly throughout program execution.