DEV Community

CharmPic
CharmPic

Posted on

What I Learned Building 12 Generations of Memory Allocators: Balancing Speed and Low RSS

#cpp #chatgpt

My personal research project, the Hakozuna memory allocator, has recently reached its 12th generation (HZ12).

Even though it doesn't make me a single dime, I somehow ended up building 12 different generations.
This time, I have published a paper on Zenodo that synthesizes the findings and designs of HZ10, HZ11, and HZ12.

Note: The Zenodo repository includes PDFs of both the English and Japanese versions of the paper.

What is Hakozuna?

Hakozuna is a family of memory allocators I developed to research various aspects of memory management, including malloc/free performance, RSS (Resident Set Size), remote free operations, and safety.

Each generation has a specific focus:

Generation Key Theme
HZ3 High-speed local-heavy allocation
HZ4 Remote-free / message-passing
HZ5 Descriptor-owned, low RSS
HZ6 Fail-closed route contracts
HZ8 Balanced allocator for general-purpose use
HZ10 Route, lifecycle, and measurement boundaries
HZ11 Ownerless, speed-first recycling
HZ12 Advisory ownership and bounded span reclamation

Currently, HZ8 is the recommended default allocator for general use.
On the other hand, the HZ10–HZ12 series represents a more research-oriented branch.

HZ11: Prioritizing a Fast Recycling Path

In HZ11, we explicitly avoided the design where the thread freeing an object must return it to its original owner thread on every single free call.

Instead, we introduced the following structure:

front cache ──> transfer cache ──> central spans ──> ownerless recycling
Enter fullscreen mode Exit fullscreen mode

By avoiding ownership checks during every free operation, we can significantly shorten the hot path.

In our remote/mixed benchmarks on Linux x86-64, HZ11 fine128 achieved the following throughput ratios compared to tcmalloc:

Workload HZ11 / tcmalloc Throughput Ratio
main_r50 1.853x
main_r90 2.346x
medium_r50 4.590x
medium_r90 6.097x

⚠️ Disclaimer: These results are highly specific to certain benchmarks, machines, and lanes. This does not imply that HZ11 is universally faster than tcmalloc.
For instance, in the Windows broad-MT balanced benchmark, HZ11 reached about 422M ops/s, which is roughly 81.7% of tcmalloc's performance. However, in larger_sizes, it achieved around 149%. There are very clear strengths and weaknesses.

The Weakness of Ownerless Recycling

While ownerless recycling is incredibly fast, it introduces a major challenge: when objects are scattered across multiple threads' caches or central structures, it becomes extremely difficult to determine if a specific span has become completely empty.

Fast recycling of objects 
   └── BUT ──> Hard to safely decommit entire spans
Enter fullscreen mode Exit fullscreen mode

Adding atomic counters or owner lookups to every free call would make tracking empty spans easier, but it increases the fixed overhead of malloc and free.

This trade-off is what led to the design shift in HZ12.

HZ12: Decoupling Ownership from Safety Guarantees

In HZ12, the ownership tag is no longer treated as the ultimate authority that guarantees the safety of a reclaim operation. Instead, it serves merely as a hint to find candidates.

  • Ownership token: A hint to narrow down candidate searches.
  • Reclaim authority: Decided by verifying multiple conditions on the cold path:
  • Complete-span snapshot
  • Inbox emptiness
  • State validation
  • Reclaim budget
  • Depot capacity

By validating these conditions on the cold path, we avoid putting any diagnostic, per-operation atomic accounting into the high-performance production hot path of malloc/free.

Bounded Span Reclamation

To ensure safety, HZ12 enforces a strict sequential contract during reclamation:

  1. Search for complete span candidates.
  2. Verify inbox and owner state.
  3. Check the reclaim budget.
  4. Pre-reserve depot capacity. (Crucial!)
  5. Detach the route.
  6. Decommit the payload.
  7. Roll back if any step fails.

If you decommit a span first and only then realize there is no space to store it, the span falls into a "limbo" state where it belongs to nowhere. To prevent this, depot capacity must be reserved prior to decommitting.

Reclamation Results on Linux

We measured owner turnover over 8 generations on Ubuntu/Linux x86-64.

  • Conditions: 64 spans per generation, 64-byte objects, RUNS=5.
Metric Result
retirement p50 1.089 ms
retirement p99 1.144 ms
retirement max 1.167 ms
reclaimed spans 512 total
discarded bytes 32 MiB total
limbo spans 0
peak RSS 7.56 MiB
post RSS 3.56 MiB

We successfully reclaimed all 64/64 spans across all 8 generations. More importantly, the number of limbo spans was exactly 0.

Platform-Specific Implementations over Unified Code

Instead of forcing a single implementation across operating systems, we separate the OS backing layers while sharing the core semantics.

  • Windows: Uses VirtualAlloc with decommit / recommit.
  • Linux: Uses mmap with madvise(MADV_DONTNEED).

What they share is not the code itself, but the contract:

  • Reclaim only complete spans.
  • Keep budget and depot bounded.
  • Roll back on failure.
  • Never create limbo spans.
  • Keep the speed lane and diagnostic lane strictly separated.

We believe implementing the same contract tailored to each OS is far cleaner than squeezing them into a single, highly abstracted codebase.

Documenting the Failures (The "NO-GO" Experiments)

In the Hakozuna project, we document not only the successful optimizations but also the experiments that ended up as "NO-GOs."

Experiment Decision Reason
Inbox capacity 2048/4096 CLOSED Expanding capacity violates our low RSS policy.
Per-operation atomic accounting NO-GO (Speed Lane) Introduces too much fixed overhead on the hot path.
Incomplete reclaim snapshot NO-GO Fails to serve as a reliable safety authority.
Depot reservation after decommit MUST FIX Creates dangerous "limbo" spans.
Lock-free per-free handoff OUT OF SCOPE Not the focus of the HZ12 architecture.

In allocator optimization, looking only at the "what went faster" results can easily lead to misinterpreting the actual design space. Documenting what we tried and why we rejected it is just as valuable a research contribution.

Roles of HZ8, HZ11, and HZ12

Here is how the current lineup is positioned:

  • HZ8: * General-purpose allocator.
  • Balanced throughput and low post-workload RSS.

  • Fail-closed ownership.

  • HZ11: * Ownerless, speed-first baseline.

  • Built for throughput research.

  • HZ12: * Advisory ownership and bounded span reclamation.

  • Built for researching the trade-offs between speed and RSS.

HZ12 is not an absolute upgrade to HZ11. Managing ownership and lifecycles always introduces some overhead; for purely speed-oriented workloads, HZ11 may still have the upper hand. Additionally, we are not claiming that HZ12 replaces HZ8 at this stage.

Conclusion

The core question we wanted to answer with HZ10–HZ12 was:

How far can we balance the speed of ownerless recycling with efficient span reclamation, without adding owner lookups or diagnostic atomic operations to the malloc/free hot path?

Our current answer is:

  • Hot path: Keep it short and completely ownerless.
  • Cold path: Narrow down candidates using advisory ownership, verify safety using complete-span validation, and cap the reclamation volume using a bounded budget and depot.

We haven't built a "silver bullet" allocator that completely replaces tcmalloc across the board. However, we have gained deep, practical insights into how to trade off speed, RSS, safety, and complexity within a unified allocator design.

For a deeper dive into the architectural details and comprehensive benchmark data, please check out our paper and repository!

Top comments (0)