Placement Strategies: first-fit, best-fit, worst-fit

When the free list contains several blocks large enough for a request, which do you pick? The choice — the placement policy — is one of the oldest design decisions in allocator design (Knuth, The Art of Computer Programming, vol 1, §2.5).

First-fit

Walk the list; take the first free block large enough. Fast — early exit.

Downside: small allocations tend to cluster at the start, fragmenting the low addresses.

Best-fit

Walk the entire list; pick the SMALLEST free block that satisfies the request. Minimizes immediately-wasted space.

Downside: O(n) per allocation, and it tends to leave a sea of tiny unusable remainders.

Worst-fit

Take the LARGEST free block. The reasoning: the leftover remainder is more likely to be useful for a future request.

In practice, worst-fit usually loses — it splits the biggest blocks, so large future requests fail more often.

Empirical results

Knuth and follow-up studies (Wilson et al., 1995) found:

• First-fit and best-fit are roughly equivalent in steady state on real workloads.
• Worst-fit is consistently inferior.
• Best-fit's slowness can be amortized via segregated free lists — one list per size class makes best-fit O(1) per class.

What modern allocators use

• glibc ptmalloc2: best-fit within size-class bins.
• jemalloc: deterministic placement within run-class slabs.
• tcmalloc / mimalloc: thread-cached size classes; placement is per-class.

The placement policy matters less than people once thought. Segregation (size classes) and coalescing matter more.

Implementation

This lesson lets you toggle between FIRST, BEST, WORST on the same heap and observe how the free list evolves under each policy.