skip to content

A size-class allocator rounds every 3 KB request up to a 4 KB block; which fragmentation does that trade away, and what does it buy?

level: middleimportance: should knowfreq 48%

answer

  1. a conversion, not a deletion
  2. same shape means reusable
  3. the tail inside every block
  4. bounded by the class spacing
  5. finer classes, more idle reserve

basics

~20 s

It trades unbounded gap waste for bounded rounding waste. Within one class every free block fits every request of that class, so unusable gaps cannot form there; the price is 1,024 idle bytes per 3 KB request, a quarter of each block.

solid answer

~40 s

Rounding to classes is a deliberate exchange. Inside a class, every block has the same shape, so a freed block satisfies any future request of that class and free space there cannot decay into slivers — the gap waste that depends on allocation history largely goes away. In exchange you pay a **fixed, predictable** tail inside every block: 3,072 bytes in a 4,096-byte block wastes 1,024. The win is that the cost becomes something you can bound and budget. With power-of-two classes the worst case per block is just under half, when a request lands one byte above a class boundary. Finer class spacing shrinks that tail but multiplies the number of separate pools, each holding its own idle reserve that other sizes cannot borrow.

code

pseudocode · 10 lines
pseudocode
classes = [16, 32, 64, 128, ..., 4096]

function block_size_for(n):
    for each c in classes ascending:
        if c >= n:
            return c
    return round_up_to_page(n)      # above the top class

waste = block_size_for(3072) - 3072   # 4096 - 3072 = 1024
worst = block_size_for(2049) - 2049   # 4096 - 2049 = 2047

go deeper

for a junior

Remember that a request is served by a block at least as large as it asks for, and the difference is idle. Be able to compute it for a concrete pair of numbers.

for a middle

Explain the exchange: identical block shapes inside a class make freed blocks reusable, and the price is a bounded tail per block. Produce the worst case for power-of-two spacing without hesitating.

for a senior

Show that you would set class boundaries from a measured request-size histogram, and that you know finer classes move waste into per-class reserve rather than deleting it.

for a principal

Argue the risk shape, not the percentage: a predictable tax you can provision for beats a smaller expected cost with a tail that depends on allocation history.

## The exchange being made An allocator that hands out exactly the number of bytes requested has no rounding waste at all — and inherits the hardest possible free-space problem, because every freed region is a unique shape that only a matching future request can reuse. Rounding requests up to a small set of fixed sizes inverts that. Within one class, all blocks are identical, so any freed block satisfies any request of that class. Free space inside a class cannot decay into pieces that are individually too small, because there is only one piece size. The bill arrives as **internal fragmentation**: the unused tail inside every block. ## The arithmetic of the tail With power-of-two classes: | Request | Block | Wasted | Share of the block | |---|---|---|---| | 24 bytes | 32 bytes | 8 | 25% | | 3,072 bytes (3 KB) | 4,096 bytes (4 KB) | 1,024 | 25% | | 2,049 bytes | 4,096 bytes | 2,047 | just under 50% | | 4,096 bytes | 4,096 bytes | 0 | 0% | The worst case is a request one byte above a class boundary: it is pushed into the next class and wastes almost the whole of the new half. That is the bound a power-of-two scheme promises — **never more than just under half a block**, and typically far less. The average over a workload depends entirely on where its request sizes sit relative to the boundaries. ## Why a bounded waste is worth paying for The decisive property is not the size of the waste but its **shape as a risk**: - Rounding waste is **per block** and **bounded** by class spacing, so total waste scales with the live set, not with the program's allocation history. - Gap waste between blocks depends on the *order* in which mixed sizes were requested and released. Two runs of the same program with the same live set can end up with very different amounts. - Rounding waste is recovered in full when the block is freed; gap waste is recovered only when neighbours happen to merge or blocks are moved. A capacity plan can absorb a predictable 20% tax. It cannot absorb a number that depends on what the workload did yesterday. ## The cost of making classes finer The obvious move is more classes, spaced more tightly, so the tail shrinks. It works, with a second-order cost that surprises people: 1. Each class holds its **own** free blocks. Bytes idle in the 512-byte class cannot serve a request for 1,024 bytes without going back to a shared region and being re-carved. 2. A workload that uses only a few classes still pays for the reserve sitting in the ones it touched earlier. 3. Some waste therefore migrates rather than disappears: out of the block tails and into per-class idle reserve. So the design question is not simply how tight the classes are; it is how well the class boundaries match the workload's actual request-size histogram. A handful of classes placed where the mass of requests sits beats a long ladder of classes spread evenly. ## What this does not solve Class rounding tames free space *within* a class. It does not make the whole heap immune: - Regions dedicated to one class can sit nearly empty while another class is starved, which is gap waste at a coarser granularity. - Very large requests, above the top class, typically get an individually sized region and carry the general problem with them. - Rounding waste itself is unaffected by anything that merges or moves blocks, because it is a consequence of the block size chosen at allocation. ## The interview register The strongest answer states the trade in one sentence — unbounded, history-dependent gap waste exchanged for bounded, per-block rounding waste — then produces the arithmetic on demand, then names the second-order cost of finer classes. Candidates who describe classes as removing fragmentation outright have missed that the waste was converted, not deleted.

  • Why is a bounded internal waste often preferred to an unbounded external one in a long-running process?
    Because it can be sized. Rounding waste is per block and capped by the class spacing, so it scales with the live set and is recovered on free. Gap waste depends on the order of past requests and releases, so the same live set can cost wildly different amounts on different days — which is impossible to budget for.
  • With power-of-two classes, what is the worst-case rounding waste for a single block?
    Just under half the block. A request one byte above a class boundary is pushed into the next class: 2,049 bytes occupy a 4,096-byte block and waste 2,047, or 49.98%. The best case is zero, when the request size matches a class exactly.
  • How would you pick class boundaries for a workload you can measure?
    Build a histogram of request sizes and place boundaries just above the peaks, so the most common sizes land near the bottom of their class. Even spacing wastes classes on sizes nobody asks for, while a few well-placed boundaries capture most of the benefit at a fraction of the reserve cost.

saying these in an interview costs you the question

  • Says size classes eliminate fragmentation rather than convert one kind into another
  • Believes the rounding waste is unbounded rather than capped by class spacing
  • Assumes finer classes are free and always reduce total waste
  • Thinks a free block in one class can directly serve a request in another
  • Claims merging free neighbours reduces the waste inside a live block