Two kinds of fragmentation, named carefully
In guide 1 you met fragmentation as a single villain. To control it you must split it into its two distinct forms, because they pull in opposite directions and you cannot beat both at once. Internal fragmentation is the waste inside a block you handed out: ask for 24 bytes, get a block of 32, and 8 bytes are paid for but unusable. External fragmentation is the waste between blocks: the heap holds plenty of free bytes in total, but they are scattered in small holes, so no single contiguous run is large enough for the next big request. malloc() can return NULL with megabytes free.
The tension is exact and worth holding in your head. If you serve every request from an exactly-sized block, internal waste is zero — but you end up with countless distinct sizes scattered everywhere, and the heap fragments externally. If instead you round every request up to one of a few fixed bucket sizes (the move this guide is built around), external fragmentation almost vanishes because freed blocks are interchangeable — but each block now carries a little internal slack. Real allocators do not eliminate fragmentation; they choose where to spend it, trading a controlled, bounded amount of internal waste to make the far nastier external kind manageable.
Alignment: the offsets the hardware insists on
Before size classes make sense you need alignment, a constraint that comes not from the allocator but from the CPU and the ABI underneath it. A type with alignment A must live at an address that is a multiple of A. On a typical 64-bit machine an int wants a 4-byte-aligned address, a pointer or double wants 8, and the safe default malloc() must satisfy is the alignment of the largest standard type — commonly 16 bytes — so that whatever type you cast the result to, it lands legally. That is why malloc() never returns an odd address: the low bits are always zero.
Why does the hardware care? A misaligned access can cost extra: the CPU may have to issue two memory transactions and stitch the pieces together, and on some architectures a misaligned load is not slow but illegal — it traps. The C standard agrees: reading an object through a misaligned pointer is undefined behavior, which means the optimizer is free to assume it never happens, so the bug may run fine at -O0 and silently miscompile at -O2. This is exactly the honest danger of UB you met earlier: not "it depends on the platform," but "the compiler is allowed to pretend the unaligned case is impossible."
Because the required alignment is always a power of two, rounding up is one cheap bit trick rather than a division. To round a size n up to a multiple of A (with A a power of two), the allocator computes (n + A - 1) & ~(A - 1): adding A-1 pushes you past the next boundary, and masking off the low bits with ~(A - 1) snaps you back down onto it. The same identity that let the allocator steal a block's low bits for flags in guide 1 — every aligned size has its low bits zero — is the identity that makes alignment rounding a single AND. When you genuinely need stronger alignment than malloc() gives (say a 64-byte cache line), C gives you alignas and alignof, and that deliberate request for more than the default is called over-alignment.
round n up to a power-of-two alignment A:
aligned = (n + A - 1) & ~(A - 1)
example, A = 16 (so A - 1 = 0x0F, ~(A-1) = ...0xF0):
n = 24 -> (24 + 15) & ~15 = 39 & 0xFFFFFFF0 = 32
n = 32 -> (32 + 15) & ~15 = 47 & 0xFFFFFFF0 = 32
n = 33 -> (33 + 15) & ~15 = 48 & 0xFFFFFFF0 = 48Size classes: a few buckets instead of every size
Now the central idea. Instead of tracking blocks of every possible size, the allocator rounds each request up to one of a small, fixed set of size classes — say 16, 32, 48, 64, 80, 96, ... bytes — and only ever hands out blocks of those exact sizes. A malloc(24) and a malloc(30) both become a 32-byte block. The payoff is huge: because every block in a given class is identical, a freed 32-byte block is interchangeable with every other, so the allocator never needs to search for a block of the right size — it just pulls the head of that class's list. The O(n) free-list walk from guide 1 collapses to O(1).
This is the segregated free list: not one list but an array of lists, indexed by size class. malloc(n) rounds n up, indexes straight into the array, and pops the first block off that list; free(p) reads the block's size class from its header and pushes it back onto the matching list. There is no scanning and no placement policy to agonize over within a class — every block fits exactly by construction. Notice too that size classes make splitting and coalescing nearly unnecessary: you do not carve a big block down because you already have a list of exactly-right blocks, and you do not merge because all blocks in a class are the same size. The bookkeeping from guide 1 gets dramatically simpler.
The price, of course, is internal fragmentation, and the spacing of the classes is exactly the knob that sets it. If classes jump by powers of two (16, 32, 64, 128), the rounding can waste up to nearly half a block in the worst case — a malloc(65) lands in the 128 class. Real allocators use a finer schedule: small sizes spaced linearly (16, 32, 48, 64) so the waste is at most one step, with the spacing widening only for large sizes where a few percent overhead is negligible. tcmalloc, which guide 5 dissects, uses roughly 80-90 size classes tuned so the worst-case internal waste per object is bounded — often capped near 12.5%. The whole design is a deliberate, measured trade: a bounded sliver of internal waste bought in exchange for O(1) speed and near-zero external fragmentation.
Placement, blowup, and the limits of size classes
Size classes do not abolish placement policy — they relocate it. Within a class the choice is trivial (any block fits), but two new placement questions appear above. First, where does a fresh class list get its blocks from? An allocator carves them in bulk from a larger run — a page or a span — so one system call yields many same-size blocks at once. Second, when does a mostly-empty span get returned to the OS? Reclaiming too eagerly thrashes; too lazily leaks memory back to the program's peak. These are the real placement decisions of a modern allocator, and they are about spans of pages, not individual bytes.
Size classes also introduce a failure mode worth naming honestly: blowup. Because blocks of one class cannot satisfy a request in another, memory freed in class 32 sits idle and cannot be reused for a flood of class-64 requests, even though the bytes are right there. A program whose allocation sizes shift in distinct phases — first millions of small nodes, then millions of larger ones — can hold far more memory than its live set, because each class hoards its own freed blocks. This is the segregated allocator's characteristic weakness, the mirror image of the external fragmentation it cured, and a place where measuring real workloads matters.
- Round the request up. Add header/alignment overhead, then snap up to the nearest size class with one mask: this both aligns the block and picks its class in a single step.
- Index, do not search. Use the class number as an array index into the segregated free lists, jumping straight to the right list with no walk.
- Pop or refill. If that list is non-empty, pop its head in O(1); if it is empty, carve a fresh run of same-size blocks from a larger span and thread them on.
- On free, push back by class. Read the block's class from its metadata and push it onto the front of that class's list — no coalescing, no boundary tags needed within a class.
Where this points next: per-thread and per-node
Size classes solved speed and external fragmentation for a single thread, but they expose the next problem squarely. The segregated lists are shared state, and real programs allocate from many threads at once. If every malloc() and free() must lock the same per-class list, that lock becomes a queue and your O(1) allocator stalls under contention. The standard cure, which guide 5 makes concrete, is a thread-local cache: give each thread its own small set of per-class free lists, served without any lock, and only reach for the shared central lists when a thread's cache runs empty or overflows. Most allocations then touch nothing but thread-local memory.
There is a subtler reason thread caches matter that ties back to alignment and size classes: false sharing. Two threads touching two different objects that happen to land in the same 64-byte cache line will ping that line back and forth between their cores, murdering performance even though the objects never logically overlap. Size-class layout and per-thread arenas help by keeping each thread's objects clustered on its own lines. On big machines there is one more axis: memory is physically attached to particular CPU sockets, and reaching another socket's memory is slower, so a serious allocator does NUMA-aware placement — keeping a thread's allocations on the memory node closest to the core running it.
Step back and see the shape of the whole rung. Guide 1 gave you the free list and its O(n) weakness; this guide rounded requests into a handful of aligned size classes to make the common case O(1) and to trade controlled internal waste for vanishing external fragmentation. What remains is concurrency and reclamation at scale — the per-thread caches, the central heaps, the span management, and the careful tuning that separate a textbook allocator from jemalloc, tcmalloc, and mimalloc. You now hold every primitive those production allocators are built from; guide 5 simply shows how they assemble them.