Free preview

Contract checklist

Ask, one at a time — these are promises, and several force the design:

□ individual free?            NO — and no-free IS the feature (say why)
□ alignment guarantee         >= 8; caller may request larger power of two
□ exhaustion behavior         must not fail -> chained growth
□ oversized requests          must succeed -> dedicated spliced block
□ reset vs destroy            rewind-and-keep-warm  vs  actually release
□ threading                   single-threaded; idiom = one arena per thread
□ size profile                mostly small; plan for the outlier

The model

Block   base, cursor, end, next        (base <= cursor <= end, always)
Arena   head (chain), current, block_size (64 KiB)

alloc   aligned = (cursor + a-1) & ~(a-1); fit-check vs end; advance
slow    fits a slab -> chain fresh block, retry
        oversized  -> dedicated block sized to need, spliced; never current
reset   every cursor -> base; release NOTHING (warm reuse)
destroy walk chain, free each slab exactly once

Worked bump: cursor 0x5008, 40 bytes @ align 16 → (0x5008+15) & ~0xF = 0x5010, new cursor 0x5038, 8 bytes padding lost.

Invariants

- base <= cursor <= end, every block, always
- every returned pointer inside exactly one block, aligned as requested
- below cursor: caller-owned until reset/destroy; at/above: arena's
- reset rewinds all cursors, releases nothing
- destroy releases each slab exactly once

The lifetime argument (say it early)

Allocation lifetime == phase lifetime, so per-object bookkeeping is paying for a capability nobody uses. Deleting it is what makes alloc a pointer bump. Right tool when lifetimes are collective (request, frame, AST, per-thread scratch); wrong tool for independent unpredictable lifetimes.

Complexity facts

alloc     O(1) (arithmetic + compare); slow path amortized O(1)
reset     O(blocks)
destroy   O(blocks)
overhead  align padding (<= align-1 per alloc) + tail slack per block

What earns points, per report dimension

  • Requirements & interface — you asked the contract questions, and treated no-free as the feature, not a flaw; oversized and reset-vs-destroy pinned before design.
  • Core design & invariants — three-pointer blocks, chained growth, spliced oversized path, and the invariant list stated unprompted.
  • Extension probe — the round will stress the contract; points come from extending it with operations it already permits and naming exactly which invariant a proposal would break.
  • Complexity honesty — O(1) with its because; alignment waste and tail slack admitted, not hidden.
  • Communication — the lifetime argument stated up front; each line of the bump tied to the invariant it maintains.

Enjoying the preview?

Create a free account to unlock the rest of this course, the in-browser judge, and live AI mock interviews.

Sign up free to continue