How do you choose among size classes, neighbour coalescing, relocation and per-phase region reset when designing for a mixed-size, long-running workload?
answer
- measure first, then match
- each fix targets one waste
- some fixes constrain the program
- adjacency versus arbitrary relocation
- order by blast radius, not benefit
basics
~20 sMatch each mitigation to the waste it can actually address, then pick by price. Size classes bound rounding waste, coalescing rebuilds runs from adjacent neighbours, relocation restores contiguity but must update references, and a region reset returns everything at a phase boundary.
solid answer
~40 sStart by measuring which waste you have: `occupied - requested` for rounding, and `total_free` against `largest_run` for gaps. Then match. **Size classes** make blocks interchangeable within a class and charge a bounded tail per block. **Coalescing neighbours** rebuilds large runs, but only where free blocks are physically adjacent — one live block in the middle keeps two runs apart. **Relocation** restores contiguity regardless of adjacency, and charges the heaviest price: every reference to a moved block must be updated, which needs indirection or exact reference knowledge, plus a pause or barriers. **Region reset** returns everything at once and needs a phase boundary to reset at, reclaiming nothing before it. Prefer the reversible, local choices first; adopt relocation or a phase structure only when the size distribution or the latency budget forces it.
go deeper
Learn that each fix targets a specific waste: rounding is attacked by choosing better block sizes, and gaps are attacked by merging or moving. No single move addresses everything.
Be able to state what each mitigation requires and what it charges, and to explain why merging free neighbours cannot help across a live block.
Show the diagnostic path: which counters you collect, what each rules in or out, and which mitigation you would trial first given a measured request-size histogram.
Own the decision's blast radius. Two of the four options constrain the program rather than the allocator, so argue the order of adoption, the latency shape of each price, and when buying headroom beats changing the design.
## Decide what you have before deciding what to do Every mitigation addresses one of the two wastes and is useless against the other, so the first move is measurement, not design: - **`occupied - requested`** over a request trace gives the rounding waste inside blocks. - **`total_free` against `largest_run`**, measured after adjacent free blocks are merged, gives the gap waste between them. - A **request-size histogram** tells you which sizes matter and how wide the largest-to-smallest ratio really is. A design argument that starts before these three numbers exist is an argument about taste. ## The four moves and their prices | Mitigation | Waste it addresses | What it requires | What it costs | |---|---|---|---| | Size classes | Gaps, within a class: identical blocks are interchangeable | Nothing from the program | A bounded tail inside every block, plus idle reserve held per class | | Coalescing neighbours | Gaps, where free regions are physically adjacent | Adjacency bookkeeping on blocks | Work on the free path; cannot merge across a live block | | Relocating live blocks | Gaps, regardless of adjacency | Every reference must be findable and updatable | Indirection or exact reference maps, plus a pause or barriers on access | | Resetting a whole region | Both, at once | A phase boundary in the program's structure | Nothing is reclaimed before the boundary; retention is bounded only by phase length | Two of these change the allocator. Two of them change the **program**: relocation constrains how references may be held, and a phase reset constrains how work is structured. That is the real axis of the decision. ## The drivers that actually decide it 1. **The size distribution.** Narrow ratio, a few clustered sizes: classes and fixed-shape reuse do almost all the work, and nothing heavier is justified. Wide ratio with occasional very large requests: gap waste is structural, and no placement rule bounds it — the choice narrows to relocation or restructuring. 2. **Phase structure.** If work arrives as bounded units — a request, a batch, a frame — a region reset is by far the cheapest complete answer, because contiguity is restored by construction. Without such a boundary, it is not on the table at all: unbounded retention until a reset that never comes is worse than the fragmentation it was meant to fix. 3. **Reference discipline.** Relocation is only possible if every reference to a block can be found or indirected. Whether that is available is usually decided by something far above the allocator, and it is rarely worth changing for fragmentation alone. 4. **The latency budget.** Steady overhead against episodic pauses is the classic exchange. A bounded rounding tax is paid uniformly; a relocation step concentrates its cost into a moment. Which is acceptable depends on what the service promises at the tail, not on which total is smaller. 5. **Headroom.** Often the honest answer is the fourth option: accept a bounded waste and provision for it. Where the waste is predictable, buying memory is cheaper and far less risky than changing the program's reference or phase structure. ## The order to try them in 1. Measure both wastes and the size histogram. 2. Place class boundaries against the histogram's peaks — cheap, local, reversible. 3. Ensure adjacent free regions are merged, and confirm the metric is computed after merging. 4. Only then consider the moves that constrain the program: a phase reset if the workload already has boundaries, relocation if it does not and the size ratio leaves no alternative. The ordering is by **blast radius**, not by expected benefit. The first two can be reverted by changing a table; the last two are architectural commitments. ## The mistakes that show up in this conversation - Reaching for relocation when the measured waste is rounding waste, which relocation cannot touch. - Expecting coalescing to produce a large run when a single live block is stranded in the middle of the region. - Adopting a phase reset for a workload with no phase, so that nothing is ever released until the process restarts. - Comparing mitigations by average bytes saved when the requirement is expressed at the tail. ## What is being assessed Not a ranking. The interviewer wants to hear the mapping from measured waste to candidate mitigation, an honest price for each, the recognition that two of the four are program decisions rather than allocator decisions, and a stated order of adoption that puts the reversible choices first.
- Why can merging free neighbours fail to produce a large run even when most of the region is free?Because it merges only regions that are physically adjacent. A single live block stranded in the middle of an otherwise free region splits it into two runs, and no amount of merging joins them. Restoring one run there requires moving that block, which is a different and much more expensive mechanism.
- What would you measure before committing to any of these?Three things: occupied minus requested for the waste inside blocks, total free against the largest contiguous run for the waste between them, and a histogram of request sizes. The first two say which waste you have, and therefore which mitigations could possibly help; the third says how wide the size ratio is.
- When is accepting the waste the right decision?When it is bounded and predictable — typically rounding waste under well-placed size classes — and the headroom is affordable. Provisioning for a known tax is cheaper and far less risky than changing how the program holds references or structures its work, and it is reversible if the workload changes.
- Why is a per-phase region reset not simply the best option whenever it is available?Because nothing inside the region is reclaimed before the boundary, so peak footprint is set by the longest phase rather than by the live set. It also forces every allocation in that phase to share one lifetime, which quietly turns any value that must outlive the phase into a copy or a leak.
saying these in an interview costs you the question
- Proposes relocation for waste that sits inside allocated blocks
- Expects neighbour merging to join free space across a live block
- Adopts a phase reset for a workload that has no phase boundary
- Ranks mitigations by average savings when the requirement is a tail latency
- Skips measurement and argues from a preferred allocator design
- Treats extra headroom as never an acceptable answer