a size class
If a clothing store sold a different garment for every exact body measurement, the stockroom would be chaos. Instead, stores use sizes — S, M, L, XL — and round each customer up to the nearest one. A garment may fit a touch loose, but stock and handling become simple. A size class does the same for memory requests: rather than serve every exact byte count individually, the allocator rounds each request up to one of a fixed set of standard sizes, and manages memory in terms of those sizes.
Here is how it is used. The allocator defines a sorted list of size classes — a typical scheme is fine spacing for small sizes (8, 16, 24, 32, 48, 64, 80, 96, ...) widening to roughly geometric steps for larger ones (so the wasted fraction stays bounded). A request for, say, 50 bytes is rounded up to the next class, 64, and the allocator then deals only in 64-byte blocks for it: it keeps a segregated free list per class, so all the bookkeeping (free lists, slabs, thread caches) is organised by class. Because every block within a class is identical in size, allocation needs no fit search — it just pops the class's list — and a freed block is instantly reusable for any same-class request, so there is no external fragmentation within a class.
Size classes are the organising principle of every fast modern allocator: jemalloc, tcmalloc, and mimalloc all carve allocations into size classes and then segregate, thread-cache, and reclaim per class. The cost is internal fragmentation — the gap between your request and the class you were rounded into (the 14 bytes wasted when 50 becomes 64). Allocator authors tune the class table to balance two evils: too few classes means lots of rounding waste; too many means more lists, more metadata, and worse cache locality. The art is choosing class boundaries so per-block waste stays small (often capped around 10-15 percent) while the number of classes stays manageable.
/* a small slice of a size-class table; round the request UP to a class */ /* classes: 8, 16, 24, 32, 48, 64, 80, 96, 112, 128, ... */ size_t round_to_class(size_t n) { /* 50 -> 64 (wastes 14 bytes of internal fragmentation) */ return next_class_ge(n); }
Every request is rounded up to a standard class size; the gap is internal fragmentation, the price of fast segregated lists.
Rounding to a size class always rounds up, never down — you must get at least what you asked for. Smaller spacing wastes less per block but multiplies the number of lists and metadata to manage.