Real-World Allocators

Production allocators share one skeleton, and the cleverest of them still contain the pieces you just built. After this lesson you will know what each famous allocator is made of, when a specialised allocator beats a general one, and you will have written the specialised allocator that shows up most often in real code: the chunked arena.

Five allocators, one skeleton

Different code, same skeleton. Every one of them has per-thread caching for a lock-free fast path, size classes with tight spacing, coalescing at some granularity, page or slab level grouping for cache locality, and background reclaim that returns idle memory to the OS.

When a specialised allocator wins

General-purpose malloc is the DEFAULT, not the optimum. When the allocation PATTERN is known, a specialised allocator can win by an order of magnitude:

• Bump: one pointer, no individual free. For truly one-shot lifetimes: parse, use, exit.
• Arena / region: bump-style chunks with an explicit group lifetime. Allocate freely, then free EVERYTHING in one reset. Parsers, per-request server state, per-frame game scratch. Apache's pools and protobuf's arenas are this pattern industrialised.
• Slab / object pool: fixed-size slots for one type. The Linux kernel allocates every dentry and inode from a slab cache; real-time systems use pools for their worst-case guarantees.
• Thread-cached malloc (tcmalloc style): when the workload is general but heavily multi-threaded.

One correction to widespread folklore: alloca allocates on the STACK, automatic and gone when the function returns. The heap structure with stack discipline is the obstack. Arenas give the same lifetime shape with explicit control. And the rule of thumb is to profile first: if malloc is not hot, the default allocator is fine; if it is, match the LIFETIME pattern before reaching for a faster general-purpose malloc.

The chunked arena you will build

The bump allocator from lesson one had a fixed heap. A real arena grows by chunks:

• ARENA <chunk> creates an arena whose regular chunks are chunk bytes. No memory is reserved yet.
• Every request is rounded up to a multiple of 8 (a request of 0 counts as 1), the usual alignment of a pointer.
• ALLOC <n> bumps inside the current chunk. If the rounded size does not fit in what is left of it, the arena starts a NEW regular chunk and bumps there; the tail of the old chunk is abandoned as waste. The new chunk becomes current.
• A request larger than a whole chunk would never fit one, so it gets a dedicated chunk of exactly its rounded size, placed after the existing chunks. It does NOT replace the current chunk, so a later small request keeps filling the chunk it was filling before. A request exactly the size of a chunk is not "larger" and uses a regular chunk.
• The reply is <chunk>:<offset>: the chunk's index (0 for the first chunk created) and the byte offset inside it.
• RESET is the arena's only free. It releases every chunk except the first REGULAR chunk, which is kept (rewound to offset 0) so the next burst of work starts with memory already in hand; chunk numbering restarts from 0. If no regular chunk exists yet, nothing is kept.
• STATS prints chunks=<n> reserved=<bytes in all chunks> used=<sum of rounded request sizes handed out since the last reset> waste=<reserved - used>.

A short trace with a chunk size of 48:

ARENA 48
ALLOC 30   rounds to 32, new regular chunk 0         -> 0:0
ALLOC 20   rounds to 24 > 16 left, abandon 16, new chunk 1 -> 1:0
ALLOC 70   rounds to 72 > 48, dedicated chunk 2        -> 2:0
ALLOC 8    fits in chunk 1 (24 used, 24 left)           -> 1:24
STATS      chunks=3 reserved=168 used=136 waste=32

Common mistakes

• Skipping the rounding. ALLOC 1 then ALLOC 1 must give offsets 0 and 8.
• Letting an oversized request become the current chunk, which strands the rest of the previous chunk.
• Treating a request equal to the chunk size as oversized.
• Resetting by deleting everything. The first regular chunk survives, so chunk 0 exists again immediately after RESET and the next new chunk is number 1.

Your exercise

The starter reads the commands and prints replies; you maintain the chunk list. The tests cross chunk boundaries by exactly one byte, mix oversized and small requests, and reset an arena whose first chunk was oversized.