HyperMalloc

What I Built

HyperMalloc is a custom dynamic memory allocator built from first principles in C on Linux. The project was designed to understand what happens underneath malloc(), free(), and realloc() rather than treating memory allocation as a black box.

The allocator manages its own heap using sbrk() and implements the core mechanisms required for dynamic memory management, including block metadata, segregated free lists, block splitting, coalescing, realloc, pointer validation, and heap consistency checking.

Allocator Architecture

Each allocation contains metadata describing the block and its relationship to neighboring blocks. The allocator maintains a physical heap structure for adjacency and separate free-list structures for efficiently locating reusable memory.

From O(N) Lookup to Constant-Time Recovery

The first major performance problem appeared in free() and realloc(). The initial implementation searched the physical heap to rediscover the block associated with a user pointer. With 100,000 allocations, this created an expensive O(N) traversal for individual operations.

Because the allocator controls the relationship between the block header and user payload, the header could be recovered directly from the pointer. This changed block lookup from a full heap traversal into constant-time header recovery plus validation.

Segregated Free Lists

I also introduced segregated free lists so that free blocks could be organized into size classes rather than searched as one large list.

A bitmap tracks which size classes currently contain free blocks, allowing the allocator to skip empty classes rather than repeatedly traversing them.

Memory Management

HyperMalloc implements block splitting to prevent large free blocks from being unnecessarily consumed by small allocations. It also coalesces adjacent free blocks to reduce fragmentation and recover larger contiguous regions of memory.

realloc() supports in-place expansion when adjacent free memory is available and falls back to allocating, copying, and freeing when the existing block cannot grow in place.

Debugging and Heap Integrity

As the allocator became more sophisticated, bugs could corrupt multiple linked-list structures at once. I used GDB and heap consistency checks to investigate memory corruption, invalid accesses, double frees, and linked-list/coalescing errors.

The debugging process centered on allocator invariants rather than simply reacting to crashes. I verified block metadata, physical links, free-list links, allocation state, and heap boundaries to determine which invariant had been violated.

Performance Results

I benchmarked 100,000 allocations, reallocations, and frees against glibc's allocator.

Free performance was within approximately 24% of glibc in the benchmark, while the optimized implementation dramatically reduced the pathological realloc and free behavior observed in the initial design.

Engineering Lessons

HyperMalloc taught me that the performance of a systems operation is often determined by the data structures surrounding it. realloc() itself was not the fundamental problem in the initial implementation; the expensive O(N) block lookup behind it was.

The project also reinforced the importance of measuring before optimizing. Establishing a benchmark made it possible to identify pathological behavior, redesign the relevant data structures, and verify that the changes actually improved the system.