ZHeap

Oct 2001 – Nov 2001 · age 19

What it was

A compacting memory allocator in one C++ class and a console test. The heap took one large allocation and carved it into three regions: a table of cells, a hash from handle ids to cells, and the data arena. Callers never held pointers. They held integer handles and asked the heap for the current address each time. Allocation was a bump pointer, freeing left holes, and when a request would not fit and something had been freed since the last pass, the heap slid every live block down with memmove and rewrote the table so every handle still resolved. The test filled six blocks with letters, freed one, printed the arena, compacted and printed it again so the shift was visible by eye. A benchmark against malloc and new was written, then commented out, and never run in the last build.

Wins, for the age

• At nineteen, Jeff rediscovered the handle-based design of the classic Macintosh Memory Manager of 1984, working from the problem rather than the literature: if nobody holds a pointer, everything can move.
• Freeing a handle also overwrote the caller's copy of it with an invalid sentinel, so a stale handle could not be reused. A small, correct touch.
• Laid table, hash and arena inside a single buffer, so the whole heap was one contiguous object that could in principle be saved or mapped.
• Wrote the comparison harness before it was needed. The run was the part that got skipped, but the instinct to measure was already there in a mammal who had just turned nineteen.

What it taught

• The invariant of a compacting allocator: only the allocator may hold addresses, and callers must re-resolve after any allocation. Without an explicit pin, any get followed by a request may be reading moved memory.
• Build the small model of a big-system technique and measure it. That reflex recurs for decades.
• Keep the previous design in the source when there is no version control, so the rewrite can be compared.
• Demo code hides failure paths: a request that printed "Heap Full" still handed back a handle that resolved to the wrong cell.

Genealogy

Ancestors: Zenerd: the engine library whose handle-based heap this experiment isolated and tested. Descendants: Adama Caravan: bytes in one pre-sized heap, metadata held separately, two decades later.

Epitaph

Here lies ZHeap, which learned that if nobody holds a pointer, everything can move, and proved it once with six blocks of letters.