Size Classes

Every allocator you have built so far walks a list, which is O(n) in the number of blocks. Real programs allocate millions of times per second, so production allocators cannot afford the walk. After this lesson your allocator will answer a request by arithmetic and a list head instead of a search: it rounds the size up to one of a few fixed classes and takes a block from that class's own free list.

Segregated free lists

Declare a fixed set of size classes up front and keep one free list per class:

classes:   16    32    64      128    256    512    1024
free:     [ ]   [ ]   [a,b]    [ ]    [c]    [ ]    [ ]

ALLOC n rounds n UP to the smallest class that holds it and pops that class's list. FREE pushes the block back onto its class's list. Neither touches any other class, and neither searches. Segregation is the backbone of tcmalloc, jemalloc and mimalloc, and it is what makes best-fit affordable: within one class every block has the same size, so "best" is whatever sits at the head.

The rounding rule and its boundaries

"Smallest class greater than or equal to the request" has edges worth spelling out for this table of classes:

Real allocators send oversized requests around the class system entirely: glibc hands anything over 128 KB straight to mmap. A zero-byte request is legal and gets the smallest class, because malloc(0) must still return a unique pointer.

What rounding costs

The gap between the request and the class is waste inside the block, internal fragmentation. With power-of-two spacing the worst case is just under 50%: a 65-byte request occupies 128 bytes and wastes 63. That is why production allocators space their classes tighter, jemalloc uses 16, 32, 48, 64, 80 and so on, subdividing each power of two into four steps to cap the waste near 25% at the price of more lists. The seven classes here keep the model readable; the Fragmentation lesson makes you measure the waste exactly.

This lesson's bookkeeping

For each class the allocator tracks two counters: blocks currently ALLOCATED to callers, and blocks sitting on the class's FREE list.

• ALLOC n: find the class. If its free list is non-empty, REUSE a block from it: free count down by one, alloc count up by one. Otherwise mint a new block: alloc up by one. Either way print class=<c>; print TOO_LARGE and change nothing when there is no class.
• FREE c: c is a class, the way a real allocator can recover a block's class from its address. If that class has a block allocated, move it from alloc to free and print OK. Otherwise print BAD, including when c is not one of the seven classes at all.
• CLASS n: print the class a request would get, or TOO_LARGE, without allocating anything.
• STATS: all seven classes in ascending order, every time, zeros included, as <c>:alloc=<a>:free=<f>.

Bonwick's slab allocator, two lessons ahead, pushes segregation one step further: a pool per object TYPE rather than per size, with no rounding waste at all for the type it serves.

Common mistakes

• Comparing with > instead of >= when choosing the class, so a request of exactly 16 lands in 32.
• Always minting on ALLOC and never checking the free list. After ALLOC 16, FREE 16, ALLOC 16 the class must show alloc=1 free=0, not alloc=1 free=1.
• Counting a TOO_LARGE request as an allocation.
• Accepting FREE 24. Only the seven classes exist, and a class with nothing allocated answers BAD as well.

Your exercise

The starter reads the commands and prints STATS; you write the class lookup and the ALLOC and FREE accounting. Test the boundaries with CLASS first, because every other command depends on it.