Size-Class Segregation and Fit Policy in the Heap

A single free list forces every allocation to answer a search question: which of these blocks is large enough, and of those, which is the best choice. When the list is long, the answer costs time proportional to its length, and the choice made has consequences that persist for the life of the heap. Segregated storage replaces that search with arithmetic. Requests are rounded to a size class, the class names a list, and the allocation is the first block on that list. The design question moves from “which block” to “how many classes, and what sizes”.

Class boundaries determine waste

Two costs pull in opposite directions. More classes mean less rounding waste per allocation, since a request lands closer to the next boundary. Fewer classes mean shorter lists and less bookkeeping, and a simpler mapping from request size to class index. The extremes show the trade: a class per byte eliminates rounding entirely but multiplies the number of lists and the metadata, while a single class of “everything” is a free list again.

Practical designs use a geometric progression for large sizes and a linear progression for small ones. Consecutive small classes often differ by a fixed quantum, typically 16 bytes to match the alignment rule, so a 40-byte request goes to the 48-byte class and wastes 8 bytes. Beyond a threshold, the ratio between neighbouring classes is held roughly constant, at values like 1.125 or 1.25, so waste is a bounded fraction of the request rather than a bounded number of bytes. With a ratio of 1.25, the worst-case rounding waste is 20% of the request; with 1.125, about 11%, at the cost of roughly twice as many classes over the same range.

The mapping itself is usually a table lookup for small sizes and a bit-shift for large ones, since a geometric sequence can be computed from the position of the highest set bit in the size. Class selection then costs a handful of instructions with no branch on list length, which is a large part of why segregated allocators are fast.

Regime	Class spacing	Waste at worst	Typical use
Small	fixed quantum, e.g. 16 B	up to one quantum	objects up to a few hundred bytes
Large	ratio, e.g. 1.125–1.25	11–20% of request	up to the page or chunk threshold
Huge	page multiples	alignment slack only	served outside the size classes

Large requests are usually not served from classes at all. A request above a threshold, commonly one page or a few pages, goes to a separate path that obtains whole pages, because rounding a 5 KiB request up to a class boundary and then splitting it out of a page-sized block costs more bookkeeping than asking the kernel directly.

Exact-fit lists and the return of splitting

Segregation alone does not solve the leftover problem. If every class holds blocks of exactly its size, then a freed 4 KiB block cannot satisfy a 3 KiB request even though it is large enough, and the heap accumulates blocks that only their own class can use. Two strategies address this.

The first is to let classes hold ranges rather than exact sizes and to split on allocation: take a block from the smallest class that can hold the request, carve out the requested amount, and return the remainder to the appropriate class. This is best-fit at class granularity, and it preserves large extents for later large requests. The cost is that allocation is no longer a pop from a list; it is a pop, a split, and an insertion.

The second is to keep the class lists exact and rely on coalescing to rebuild larger blocks. A freed block merges with free neighbours and, once merged, moves to the class for its new size. This works only if the heap is contiguous and boundary tags are available, as described in the coalescing design. In a page-based heap where each page serves one class, coalescing across pages is not possible and the exact-fit model dominates.

Many real heaps mix the two: small classes are exact and never split, because the objects are small enough that a split would produce a sub-minimum remainder; large classes hold ranges and split. The boundary between the regimes is a deliberate choice, and it usually sits where the class spacing switches from linear to geometric.

Fit policy inside a class

Even with classes, a class that holds variable-size blocks needs a policy. Within a range-based class the natural orders are by address and by size.

Address-ordered lists make coalescing cheap, because a freed block’s neighbours are adjacent in the list, so finding them is a constant-time step from the insertion point. They also tend to preserve large extents: first-fit over an address-ordered list consumes the low end of the heap first and keeps the high end free, so a later large request finds a large untouched region. The measured behaviour of address-ordered first-fit is consistently better than unordered first-fit in the allocation literature, and the mechanism is this preservation of contiguity rather than anything about the fit test itself.

Size-ordered lists make the fit test cheap, since the first block is the smallest that fits, but insertion requires a search, and coalescing requires locating a neighbour by address in a list ordered by size, which is not a constant-time operation without an auxiliary index.

Free-list insertion order matters too. LIFO insertion gives the best cache behaviour for an allocate-free-allocate pattern, because the most recently freed block is the one most likely to be in cache, and it keeps hot objects hot. It also increases the chance that a block is reused immediately, which reduces the working set of pages the heap touches. FIFO insertion spreads reuse across the heap, which helps when the goal is to let old pages become fully free so they can be returned to the operating system. This is the same tension that governs when the heap shrinks: reuse locality versus the ability to release pages.

Fragmentation measured honestly

Two quantities are routinely conflated. Internal fragmentation is the difference between the bytes requested and the bytes consumed, caused by rounding to a class and by minimum block sizes. It is bounded by construction and can be computed exactly: with 16-byte classes and 16-byte alignment, a request of size s consumes round_up(s, 16), so the waste is at most 15 bytes, and as a fraction it is worst for the smallest requests.

External fragmentation is the inability to satisfy a request from free space that exists in aggregate. It has no closed form, because it depends on the request sequence. A useful proxy is the ratio of the largest free extent to the total free bytes: a heap with 1 MiB free in one block can serve any request up to 1 MiB, while the same megabyte spread over 256 blocks of 4 KiB cannot serve a 5 KiB request. Size classes attack external fragmentation by keeping the small-block population in separate pages from the large-block population, so small churn cannot shatter a large extent.

The converse failure is worth naming: segregating by class can strand memory. If a page is dedicated to one class and that class’s population shrinks, the page holds free blocks that no other class can use. Returning such a page requires that all its blocks be free, which requires knowing the page’s occupancy, the bookkeeping that slab caches add explicitly. Without it, a heap can hold many nearly-empty pages indefinitely.

The request-size cliff

Because class boundaries are fixed, performance is not smooth in request size. A program that allocates 48-byte objects consumes 48 bytes each; one that allocates 49-byte objects consumes the next class, which may be 64. Nothing about the extra byte is expensive; the boundary is. This produces cliffs in footprint that surprise people profiling memory, and it is why object layouts are sometimes padded to just under a class boundary.

A second cliff appears at the threshold where requests stop being served from classes. A request just below the threshold is carved from a page with class bookkeeping; a request just above it takes the large-object path with different metadata and, often, a different lock. Crossing the threshold in either direction can change both the latency and the fragmentation behaviour of an otherwise identical workload.

The class table is also a target for arithmetic bugs. Computing the index from the size requires a division or a shift, and the edge cases are the exact boundaries: a size equal to the top of a class must not be rounded into the next one, and the largest class must reject sizes above its range rather than wrap. In an allocator where the class index selects a list head from an array, an off-by-one index reads a neighbouring array slot and returns a block of the wrong size. That bug corrupts memory silently and is not reproducible under a different request pattern.