How do segregated free lists with size classes turn an allocation request from a list search into an index lookup?
answer
- one list per class, not one list
- index computed from the size
- membership already proves the fit
- exact classes small, geometric large
- refill by splitting or carving
basics
~20 sThe allocator keeps an array of free lists, one per size class. A request is mapped to a class index by arithmetic on its size, and the head of that list is popped — every block on it already fits, so nothing is searched.
solid answer
~40 sInstead of one free list holding every free block, the allocator holds an array of lists, each owning blocks of one size class. Small sizes usually get exact classes spaced by the alignment unit; larger sizes get geometrically spaced classes, so the number of classes stays modest. Computing the index is arithmetic — a rounding and a shift, or a small lookup table — after which the block is simply the head of `lists[index]`, with no comparison of sizes at all. Release runs the same mapping on the block's recorded size and pushes it back. The search has not become cheaper; it has been done in advance, by grouping blocks so that membership of a list already proves the block fits.
go deeper
Recall that free blocks can be grouped by size, and that grouping is what lets the allocator go straight to a block instead of hunting for one.
Explain the index computation, why popping the head needs no size comparison, how classes are spaced, and what happens when a class runs dry.
Show what the design costs in practice: reserve held per class, a catch-all path for large requests, and a class spacing that encodes assumptions about the workload's hot sizes.
Weigh a cheap fast path with permanently assigned runs against a design that can move memory back between classes, and decide which failure your service can afford.
A single free list makes every allocation a search, and the search cost grows with the number of free blocks. Segregation removes the search rather than speeding it up: if the allocator has already sorted free blocks into buckets by size, then picking a bucket picks a block. ## The structure The allocator holds an array of free-list heads. Each entry owns one **size class** — a range of block sizes that the allocator treats as interchangeable. Class spacing is the design's main knob: - **Exact classes for small sizes.** Below some threshold, every alignment-sized step gets its own class, so requests in the range most programs live in are served with no rounding beyond alignment. - **Geometric classes above it.** Each class is some fixed factor larger than the last, so the array covers a wide range with a bounded number of entries instead of one entry per possible size. - **A final catch-all.** The largest class usually holds everything above its boundary and is searched the old way, because very large requests are rare and varied. ## The allocation path 1. Round the request up for alignment and the block's tag. 2. Map that size to a class index — a shift and a subtraction in the geometric region, a direct division in the exact region, or a small precomputed table for the smallest sizes. 3. If `lists[index]` is non-empty, unlink its head and return it. No size comparison is needed, because every block on that list is already at least as large as the class boundary. 4. If it is empty, refill (below). Step 3 is why people describe such an allocator as constant time on the fast path. What made it constant is not a faster search but the invariant that list membership implies fit. ## Two families, and what separates them | design | splits and merges? | refill when a class runs dry | consequence | |---|---|---|---| | simple segregated storage | no | carve a fresh run of memory entirely into cells of that class | no tags needed per block; memory never moves back between classes | | segregated fit | yes | take a block from a larger class and split it | classes share memory; blocks still carry tags so they can merge | That difference is the real design decision. Simple segregated storage is the cheapest possible fast path — a run of memory belongs to one class, so the class can be recorded once for the whole run instead of per block — but a class that has grown large stays large even when the program's mix of sizes changes. Segregated fit keeps the allocator's ability to reclaim and re-carve, at the price of per-block tags and merge logic on release. ## Buddy splitting as a class scheme with a merge rule **Buddy allocation** is a segregated design whose classes are the powers of two. A request is rounded to the smallest power-of-two class that holds it; if that class is empty, a block from the class above is split into two equal halves, recursively, until the wanted size appears. The two halves produced by one split are **buddies**, and the design's payoff is that a block's buddy address can be computed directly from the block's own address and size, so on release the allocator can check in constant time whether the partner is free and, if so, merge and repeat upwards. The price is that every request is rounded up to a power of two, which is a coarse class spacing compared with a geometric scheme using a smaller factor. ## What segregation gives up - **More lists means more idle reserve.** Every class that has ever been used tends to hold some free blocks, and those blocks are not available to any other class unless the design splits and merges across classes. - **A class boundary is a policy decision that outlives you.** Once a program's hot sizes are known, the spacing can be tuned to them; once the spacing is baked in, a program with different hot sizes inherits someone else's tuning. - **The catch-all still searches.** Large, irregular requests fall outside the indexed region, so a segregated allocator normally keeps a coalescing free list underneath for them. The short version for an interview: a size class turns *which block fits* into *which list to look at*, and the interesting questions are all about how the classes are spaced and what happens when one runs dry.
- How does buddy allocation get constant-time merging out of its class structure?Its classes are the powers of two and every split halves a block, so each block has exactly one partner of the same size, at an address derivable from the block's own address and size. On release the allocator checks that one address: if the partner is free and the same size, the pair merges into the class above and the check repeats. The cost is rounding every request up to a power of two.
- What can the allocator do when the list for the requested class is empty?Two answers, and they mark the two families. A segregated-fit design takes a block from a larger class and splits it, so memory flows between classes in both directions. A simple segregated-storage design carves a fresh run of memory into cells of that class instead, which is faster and needs no per-block tag, but that run then belongs to the class permanently.
- Why does a segregated allocator usually still keep an ordinary coalescing free list?Indexed classes pay off where sizes repeat, which is the small end. Large requests are rare and irregular, so giving each of them a class would mean a huge array of mostly empty lists. Those requests instead go to a general free list that splits and merges, where a search is affordable precisely because it happens rarely.
A shoe shop with one shelf per size instead of one big pile. Nobody measures anything at the counter: you walk to the shelf your size names and take the box on top.
saying these in an interview costs you the question
- Thinks the class list is still searched for a block that fits
- Believes size classes remove the need for any general free list
- Says the index requires a lookup table for every possible size
- Assumes every segregated design splits and merges across classes
- Thinks blocks freed into a class become available to other classes automatically