Your long-lived service must choose between one coalescing free list with best fit and segregated size classes; what evidence decides it?
answer
- decide from a profile, not folklore
- histogram of sizes by count
- worst case, not average, search
- measure the share of time allocating
- classes small, coalescing list large
basics
~20 sA histogram of request sizes decides it: a few dominant sizes make classes an easy win, a long irregular tail does not. Then check the worst-case allocation latency you must meet, and the cost of owning the design.
solid answer
~50 sGather three things before arguing. First, the **size profile**: a histogram of requests weighted by count, not by bytes — if a handful of sizes carry most allocations, classes turn the fast path into an index lookup. Second, the **latency requirement**: a single free list gives an unbounded search, so if a request must complete inside a fixed budget, no average makes that acceptable. Third, the **share of time spent allocating**, measured rather than assumed; if the allocator is invisible in a profile, this is not the decision to spend effort on. The answer that usually survives is a hybrid — indexed classes for the small, repeating sizes and a coalescing fit list underneath for the large, rare ones — and the thing to write down is the evidence that would send you back the other way.
go deeper
Recall that allocators differ in how they find a block, and that which one suits a program depends on the sizes that program actually asks for.
Explain the mechanics behind each candidate — a search with splitting and merging, against an index into per-class lists — so the trade can be discussed concretely.
Bring measurements: a size histogram by count, the share of time in the allocator, and the tail of allocation latency rather than its mean.
Commit to a design, name the number you are optimising and what you are spending to get it, and state the observation that would reverse the decision.
This is a design decision, not a preference, and it is settled by a profile of the workload rather than by reasoning about allocators in the abstract. The two candidates are a general **coalescing free list** with a placement policy such as best fit, and a **segregated** allocator with a free list per size class. Both are legitimate; they fail differently. ## What each design is actually good at | property | single coalescing list | segregated size classes | |---|---|---| | fast path | a search whose length depends on the list | index computation and a list-head pop | | worst-case allocation time | unbounded in the number of free blocks | bounded, except on a refill | | adapting to a changing size mix | good — memory is re-carved freely | depends on whether classes can refill by splitting | | per-block cost | a tag on every block | can be amortised over a run of same-class cells | | effort to own | small | larger: class spacing, refill policy, a path for large requests | ## The evidence to gather 1. **A request-size histogram by count.** This is the decisive input. A profile whose top handful of sizes covers most allocations is exactly what classes are for. A profile that is smeared across a wide range with no repeats gets much less from them, because most classes would hold one or two blocks. 2. **The distribution of block lifetimes.** Blocks that are created and released in waves leave a region that coalesces cleanly; blocks with wildly mixed lifetimes interleave long-lived and short-lived blocks, which is where a single list's large free regions stop reappearing. 3. **Allocation rate and the share of time in the allocator.** Measure it. A path that allocates rarely does not justify a bespoke design however elegant the argument. 4. **The latency requirement at the tail.** Ask what the *slowest* allocation may cost, not the mean. This is usually the argument that ends the discussion, because an unbounded search cannot be reconciled with a hard per-request budget. 5. **Who will own it in two years.** A segregated allocator has tuning knobs that encode assumptions about today's workload, and those assumptions decay silently. ## Reading the histogram | what the profile looks like | what it argues for | |---|---| | a few sizes carry most allocations | size classes, spaced to land on those sizes | | many distinct small sizes, none dominant | classes still help, with geometric spacing | | large, irregular, infrequent requests | a coalescing fit list; classes would be mostly empty | | the mix changes between phases of the service | a design where classes refill by splitting, not fixed runs | ## The hybrid, and why it usually wins Most mature designs stop choosing. Small sizes repeat, index well and dominate the count, so they get classes. Large sizes are rare and varied, so they get a coalescing free list underneath where a search is affordable precisely because it happens seldom. The class array's largest entry is the seam between the two. Presenting that as the answer is stronger than defending either extreme, provided you can say **where** you would put the seam and **why** — which brings the argument back to the histogram. ## Defending the decision A principal-level answer commits, and states the conditions under which it is wrong: - Name the number you are optimising — peak resident memory, allocation tail latency, or engineering time — and say which of the three you are choosing to spend. - State the falsifier: *if the size histogram flattens, or the share of time in the allocator drops below some threshold, the classes stop paying for themselves.* - Keep the change reversible for as long as you can. Both designs sit behind the same interface, so the first move is to measure with the simple one in place, not to rewrite. - Say what you will not do: adopting a more elaborate placement rule on a single list is rarely the lever, because measurement puts the classic policies close to each other once coalescing is present. ## The failure mode to avoid The common mistake is to choose on folklore — "classes are faster" — and to discover afterwards that the service's sizes were irregular, so most classes hold a block or two of idle reserve while the catch-all path serves nearly every request. The second mistake is the mirror image: keeping a single list on a latency-critical path and arguing from the average search length, until a long list produces a request that misses its budget.
- Why weight the size histogram by count rather than by bytes?The fast path is executed once per request, so what matters for the search is how many requests share a size. A byte-weighted view is dominated by a few large buffers and can hide the millions of small requests that actually set the allocator's cost. Byte weighting is the right view for a memory-footprint question; count weighting is the right view for a placement-policy question.
- What would make you keep the single coalescing free list?An irregular size profile with no dominant sizes, a low allocation rate, no hard per-request latency budget, and a small team. In that setting classes buy little, cost tuning attention, and leave idle reserve in classes nobody uses, while a coalescing list keeps memory fully re-carvable and is far less code to own.
- How would you place the seam between the classed region and the general list?Put it where the histogram stops repeating. Below that point sizes recur often enough that a class per size range pays for its idle reserve; above it, requests are rare and varied enough that a search costs less than an array of near-empty lists. Choose the boundary from the measured profile and revisit it when the profile changes.
saying these in an interview costs you the question
- Picks a design without profiling the request sizes at all
- Argues from the average search length on a latency-critical path
- Assumes size classes are faster for every workload
- Weights the size histogram by bytes rather than by request count
- Treats the choice as permanent instead of measuring behind one interface
- Spends effort on a cleverer placement rule instead of on segregation