first-fit / best-fit / next-fit placement

Suppose you run a parking lot with gaps of various widths, and a car arrives needing a space. Which gap do you put it in? You could take the first gap you find that is wide enough (quick, but maybe sloppy). You could survey the whole lot and pick the gap that fits most snugly, leaving the least leftover (tidy, but slow to decide). Or you could remember where you parked the last car and start searching from there. These are exactly the placement policies an allocator uses to choose which free block to satisfy a request from.

Walking through the three classic policies on a free list: first-fit scans the free list from the beginning and grabs the first block large enough — fast, simple, but it tends to chew up the blocks near the front of the list and can leave a litter of small leftovers there. Best-fit scans the entire list and chooses the smallest block that is still big enough, so the leftover sliver after splitting is as small as possible — this packs memory tightly and fights external fragmentation, but it must examine every free block (slow) and can produce many tiny, useless remainders. Next-fit is first-fit with a memory: it resumes scanning from where the previous search stopped, rather than always from the front, which spreads allocations around the heap and avoids re-walking the crowded front — usually faster than first-fit but often with somewhat worse fragmentation. (Worst-fit, choosing the largest block, exists too, on the theory that the leftover stays large enough to reuse, but it tends to perform poorly.)

Why it matters: the placement policy is the allocator's core decision and it directly shapes fragmentation versus speed. The honest, much-studied finding is that there is no universal winner — the best policy depends on the workload's pattern of sizes and lifetimes, and surprisingly, plain first-fit or next-fit on a good data structure often performs about as well as best-fit in practice while being much faster. This is exactly why modern allocators largely sidestep the question for small objects with size classes and segregated lists, where every block in a class is identical and there is no fit to choose at all.