Memory Management §

Stack vs. heap: stack allocation is $O(1)$ (move a pointer); heap allocation is $O(1)$–$O(n)$ depending on the allocator. Stack memory is automatically reclaimed when the function returns; heap memory must be explicitly freed (or collected).

Tail call optimization (TCO): if a function’s last action is a call to another function, the current frame can be reused. $f(n) = n == 0 ? 0 : f(n-1) + 1$ cannot be TCO’d (the +1 is pending); $f(n, acc) = n == 0 ? acc : f(n-1, acc+1)$ can.

Stack smashing: writing past the end of a local array overwrites the return address. See Security for exploit mitigations.

The physical layout of the stack within the process address space (text, data, heap, stack, mmap regions) is described in Memory Hierarchy.

Allocators:

• First fit: scan from the start, allocate the first block that fits.
• Best fit: allocate the smallest block that fits.
• Buddy allocator: split/merge power-of-2 blocks; $O(\log n)$.
• Slab allocator: pre-allocate pools of fixed-size objects; reduces fragmentation.
• Arena/bump allocator: allocate by moving a pointer; free all at once. Fast but no individual deallocation.

Fragmentation: external (free blocks too small to use) and internal (allocated block larger than needed). The coalescing step in free merges adjacent free blocks.

Memory alignment and padding: the CPU requires certain types to start at specific addresses (e.g., a 64-bit integer at a multiple of 8). The compiler inserts padding bytes between struct fields so each member is aligned. A cache line is typically 64 bytes; aligning a hot struct to a cache-line boundary avoids false sharing (two cores writing to different fields of the same cache line). Misalignment can cause a hardware fault on some architectures (ARM) or a performance penalty on others (x86).

Memory-mapped I/O (mmap): the OS maps a file or device into the process address space, so the program accesses file contents through ordinary pointer dereferences. The kernel pages data in on demand. This is a distinct allocation strategy: the “heap” is the file, and the OS manages the virtual-to-physical mapping.

Rust’s ownership model: each value has exactly one owner; the borrow checker enforces ownership and borrowing rules at compile time. See Security for the full safety guarantees.

Mark-and-sweep: two phases. Mark: traverse from roots, mark reachable objects. Sweep: free unmarked objects. $O(n)$ where $n$ is the number of objects. Pauses the application (stop-the-world).

Copying GC (semi-space, generational): divide the heap into generations. Young generation (frequently allocated, short-lived) is collected by copying live objects to a new space. Old generation (long-lived) is collected less frequently. Reduces pause time.

Generational hypothesis: the vast majority of objects die young (commonly cited as 80–95% depending on workload). The young generation is collected by a minor GC (fast, $< 10$ ms); the old generation by a major GC (slow, $100$–$1000$ ms).

Reference counting (Objective-C, Swift ARC, Python): each object has a count; increment on reference, decrement on dereference; free at zero. Fast (no pauses) but fails on cycles (A → B → A). Python uses a cycle detector as a fallback.

Memory leaks: objects that are reachable but no longer needed (e.g., a global cache that grows unbounded). Not a GC bug; a program design issue.

The heap is exactly 64,000 bytes (1000 × 64). After all 1000 objects are allocated, the heap is full.

After freeing odd-indexed blocks (indices 1, 3, 5, …, 999), 500 blocks of 64 bytes are free, but they are scattered:

| A | F | A | F | A | F | A | F | ... | A | F | A |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |   | 998| 999|1000|

(A = allocated/live, F = free). No two free blocks are adjacent, so no coalescing is possible.

Without coalescing: the largest free block is 64 bytes. A 320-byte allocation fails despite 32,000 bytes being free (external fragmentation).

With coalescing: the freed blocks are at positions 1, 3, 5, …, 999 (0-indexed). No two freed blocks are adjacent (they alternate with live blocks), so no coalescing occurs. The result is the same: the largest free block is 64 bytes, and the allocation fails.

This illustrates why buddy allocators and slab allocators are preferred: they reduce fragmentation by design.