a segregated free list

Imagine a hardware store that organises its returned screws not in one giant bin you have to dig through, but in many small bins labelled by size: a bin for tiny screws, one for medium, one for large. When a customer needs a particular size, you go straight to the right bin instead of rummaging through everything. A segregated free list does this for memory: instead of one free list holding blocks of every size, the allocator keeps an array of free lists, one per size category, so it can find a block of the size it needs almost instantly.

Concretely, the allocator defines a set of size classes — for example 16, 32, 48, 64, 80, ... bytes, or powers of two — and keeps a separate free list (often an array indexed by class) for each. To serve malloc(40), it rounds 40 up to its size class (say 48), goes directly to that class's list, and pops the first free block off the front. There is no scanning of mismatched sizes. To free a block, it computes the block's size class and pushes it back onto that one list. Because every block on a given list is the same size (or in the same small range), there is no fit search at all for the common small-allocation case: malloc and free become roughly constant-time list pop and push, instead of a linear walk.

This is why segregated storage is the backbone of every fast modern allocator (jemalloc, tcmalloc, mimalloc all use size-class segregation). The tradeoff is honest: rounding 40 up to 48 wastes those 8 bytes inside the block — that is internal fragmentation, the price of speed. There are also two flavors of the idea: simple segregated storage never splits or coalesces (each region only ever serves one size class), trading some memory for maximum speed; segregated fits keeps differently sized blocks and may still split a larger one, trading a little speed for tighter memory.