Heap Allocator

This project was my final assignment for Stanford CS107, where I built my own heap allocator from scratch. The goal was to implement core memory management functionality equivalent to malloc, free, and realloc, while balancing correctness, speed, and memory efficiency.

The assignment involved building two allocator designs: an implicit free list allocator and an explicit free list allocator. That made the project not just about getting something working, but about understanding the tradeoffs between different system designs and making implementation decisions that affected performance.

All quarter in CS107, I had been using the heap indirectly through dynamic memory allocation. This project flipped that perspective and forced me to go under the hood. Instead of treating memory allocation as a black box, I had to design the data structures and logic that make the heap usable in the first place.

The challenge was that a heap allocator has competing goals. It needs to be correct for arbitrary well-formed requests, compact in how it uses memory, and fast enough to serve allocations efficiently. Those goals naturally create tradeoffs, so the project became an exercise in systems thinking as much as implementation.

I approached the assignment by thinking carefully about allocator structure before writing code. For the implicit free list allocator, I focused on understanding block layout, header metadata, alignment, and traversal through contiguous memory. For the explicit free list allocator, I then extended that thinking to track free blocks more directly and improve efficiency.

A big part of the design process was reasoning about tradeoffs. An allocator can move quickly by doing less bookkeeping, but that often wastes memory. On the other hand, aggressively reusing and packing blocks can improve utilization while increasing implementation complexity. This project forced me to think about those tradeoffs in a very concrete way.

I implemented custom versions of malloc, free, and realloc, along with the supporting heap logic needed to manage block allocation, deallocation, splitting, reuse, and traversal. The project required handling well-formed request patterns while preserving consistency of the heap structure across many possible allocation sequences.

The explicit free list version pushed things further by tracking free blocks in a more structured way, which improved performance compared to a purely implicit scan. That progression made it easier to see how different allocator designs impact both runtime behavior and memory utilization.

This diagram captures the core mental model behind the project: memory blocks on the heap must be organized, tracked, and reused in a way that balances correctness with efficiency.

This assignment helped me appreciate how much complexity sits behind something as common as dynamic memory allocation. It strengthened my pointer skills, forced me to debug carefully, and made performance profiling feel much more meaningful because every design choice had a visible consequence.

More broadly, it brought together a lot of what I learned in CS107: reasoning about memory, designing around constraints, and thinking critically about efficiency. It was one of those projects that made systems programming feel much more real and much more rewarding.

What I liked most about this project was that it made tradeoffs feel tangible. You cannot optimize everything at once, so you have to reason about what matters most and why. That mindset applies far beyond allocators — it is really a broader lesson in engineering design.

It also made me more comfortable with lower-level programming. Building a heap allocator from scratch was difficult, but it gave me a much stronger intuition for how memory systems actually work and why careful systems design matters.