Placement Strategies: First, Best, Worst

When the free list holds several blocks that could satisfy a request, which one do you take? That choice, the placement policy, is one of the oldest design questions in allocators (Knuth, The Art of Computer Programming, vol 1, section 2.5). After this lesson your allocator will take its policy as a setting, and you will be able to run the same workload under three policies and watch the heap come out differently.

The three policies

All three scan the free blocks whose payload is at least the request and differ only in which candidate they pick:

• First-fit takes the first candidate in address order and stops. It is the cheapest, because of the early exit. Its known side effect: small allocations pile up at the low addresses and leave a littered front of the heap.
• Best-fit examines every candidate and takes the one with the smallest payload, so the leftover is as small as it can be. The scan always runs to the end of the list, and the tight fits tend to leave tiny remainders that nothing can use.
• Worst-fit takes the largest candidate on the theory that the remainder will still be big enough to be useful. In practice it keeps carving up the largest blocks, so big requests fail sooner.

Ties matter and the exercise pins them down: when two candidates have the same payload, best-fit and worst-fit both take the one at the LOWER address. Written as a loop, that means replacing the current choice only on a strictly smaller (best) or strictly larger (worst) payload.

One request, three outcomes

Suppose the free blocks, in address order, have payloads 180, 400 and 120, and the request needs 100 bytes (HDR = 8, MINP = 16, split rule as in the splitting lesson):

Best-fit left no usable remainder at all, first-fit left a modest one, and worst-fit left a large one. Which is better depends entirely on what is requested next, which is why this was argued over for decades.

What the studies found

Knuth and the follow-up work (Wilson et al., 1995) found that first-fit and best-fit come out roughly equivalent in steady state on real workloads, and that worst-fit is consistently inferior. Best-fit's cost can be avoided with segregated free lists: one list per size class, so that "the smallest block that fits" is whatever sits at the head of the right list. The Size Classes lesson builds that. Production allocators lean on it: glibc's ptmalloc is best-fit within bins, and tcmalloc and mimalloc keep per-class lists with no placement search at all. Placement matters less than people once thought; segregation and coalescing matter more.

Common mistakes

• Using <= or >= in the comparison, so a tie goes to the later block. Best and worst both keep the first of equals.
• Choosing among ALL free blocks instead of only those that are big enough. A 64-byte block is not a "best" fit for a 100-byte request.
• Letting best-fit ignore remainders: when the tightest block's remainder is below MINP, the whole block is handed out.
• Treating the policy as a per-request setting. It is chosen once by INIT and applies to every ALLOC after it.

Your exercise

The starter is the full coalescing allocator from the last lesson with the choice of block left out. Implement pick, which returns the index of the block to use, according to the strategy given to INIT. The tests replay one workload under all three strategies, then probe ties and a request that does not fit anywhere.