Implement an Arena Allocator for Bulk Deallocation

Topic Overview

Bulk Free With One Reset

Arena allocators (also called region allocators) hand out slices from growing blocks and free everything when the arena resets. LLVM's BumpPtrAllocator, Rust's bumpalo, and many compilers use arenas per function or per compilation unit.

Block Chaining

When the current block fills, allocate a larger block, link it, and continue bumping. Reset walks blocks or reuses the first chunk.

cCopy
Loading…

• Great for AST nodes created during parse and thrown away after codegen
• Thread-local arenas avoid synchronization on bump path
• Do not store arena pointers past reset
• Combine with a malloc fallback for rare huge allocations

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

• Trace first: walk one failing input step by step
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will implement a multi-block arena with reset and measure allocation throughput. This exercise requires using the arena for a batch of objects then reclaiming all with one reset call.

Your Task

An arena is a bump allocator that never runs out: when the current block is full it chains a new, larger block, and everything is freed at once when the arena is destroyed. Add temporary scopes (save a position, then roll back everything allocated after it, including whole blocks) and clear (keep the first block for reuse). Track exactly where bytes are wasted.

Input

cCopy
Loading…

Rules

• Allocate from the current block at round_up(offset, ALIGN). If it does not fit, start a new block of size max(2 * current block size, SIZE) and place the allocation at its offset 0 (block bases are page-aligned). The unused tail of the old block is lost.
• temp begin saves (block, offset, bytes used), up to 8 deep. temp end restores the latest save, frees every block created after it, and reports the bytes released.
• clear keeps only block 0, empty. destroy frees every block and starts again with a fresh first block. Every allocation made so far is freed at once.
• stats: blocks, reserved bytes (the sum of block sizes), bytes used by live allocations, and bytes lost to alignment padding and abandoned block tails (reserved − used − the free space left in the current block).
• Errors: arena: 16..1048576 bytes, alloc NAME: bad size or alignment, alloc NAME: too many blocks (32 at most), temp: too deep, and temp end: no temp scope.

Output

cCopy
Loading…

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Grow geometrically (doubling), so the number of blocks stays logarithmic in the total size.
2. Implement temp scopes by restoring saved positions and dropping later blocks. Individual allocations are never tracked.

Hidden tests cover an allocation bigger than twice the current block (it gets its own oversized block), nested temp scopes, a temp scope that stays inside one block, large alignments, clear followed by reuse, and invalid sizes, alignments and scopes.