A heap allocator searching one free list can take the first block that fits or the smallest; what does each policy cost?

middlemust knowfreq 66%

answer

stop early versus scan everything
the leftover is the real output
remainders gather at the list head
split only above the minimum block
segregation beat both policies

basics

~20 s

First fit stops at the first adequate block, so the search is short but early splits leave small remainders near the list head. Best fit scans the whole list for the tightest block, paying a full walk to leave a smaller remainder.

solid answer

~50 s

First fit walks the free list from the head and takes the first block at least as large as the request. Its average search is short, but each split leaves a remainder behind, and those remainders accumulate where the search always starts, so later searches step over them. Best fit walks the entire list — unless the list is kept size-ordered — to find the smallest block that still fits; the remainder it leaves is as small as possible, which often means too small to be useful again. Both then split the winner only if the leftover is at least the minimum block size, otherwise they hand out the whole block. Measurements on real programs have repeatedly found the two close once coalescing is in place, which is why serious allocators invest in segregating by size rather than in a cleverer fit rule.

code

pseudocode · 18 lines

pseudocode

allocate(request):
    need = round_up(request + TAG_BYTES, ALIGNMENT)
    if need < MIN_BLOCK: need = MIN_BLOCK

    for each block in free_list:          # first fit: stop at the first candidate
        if block.size >= need:
            leftover = block.size - need
            unlink(block)
            if leftover >= MIN_BLOCK:
                rest = block + need
                write_tags(rest, leftover, free)
                push_free_list(rest)
                write_tags(block, need, used)
            else:
                write_tags(block, block.size, used)   # absorb the surplus
            return payload_of(block)

    return grow_region(need)

go deeper

for a junior

Recall that an allocator has to search for a free block, and that taking the first one that fits is not the same choice as taking the tightest one.

for a middle

Explain both searches, the split and its minimum-size guard, and what residue each policy leaves for the next request to walk over.

for a senior

Argue from worst case rather than average: an unbounded list walk on a latency-sensitive path is the real objection, and coalescing matters more to memory use than the choice of rule.

for a principal

Decide whether to spend engineering effort on the placement rule at all, given that measurement puts the two policies close and that segregating by size is the change that removes the search.

Imagine a hand-written allocator inside an embedded telemetry logger: one region of memory, one linked list of the free blocks in it, and a request for n bytes arriving. The allocator must choose a block from that list. The rule it uses to choose is the placement policy, and the two classic rules are first fit and best fit.

What each policy does

First fit starts at the head of the list and takes the first block whose size is at least the rounded-up request. The search stops as soon as a candidate appears, so on a list with many adequate blocks it inspects only a handful.

Best fit inspects every block and keeps the smallest one that is still large enough, stopping early only if it finds an exact match. On an unordered list that is a full traversal on every single request. If the list is instead kept sorted by size, best fit becomes the first adequate block in that order — but then every release must insert into a sorted structure, moving the cost from allocation to release rather than removing it.

A third rule, next fit, is first fit with a rover: the search resumes where the previous one stopped instead of returning to the head. It avoids re-walking the crowd of small remainders at the front, at the cost of scattering allocations across the whole region.

Splitting the winner

Whichever block is chosen, it is usually bigger than the request, and the allocator must decide what to do with the surplus:

Round the request up to satisfy alignment and to leave room for the block's own tag.
If the leftover would be at least the minimum block size — big enough to carry a tag and the free-list links — split the block: the low part becomes the allocation, the remainder gets its own tags and goes back on the free list.
If the leftover would be smaller than that, hand out the whole block. The few surplus bytes sit inside the allocation, unusable but also untracked.

That guard is what stops splitting from manufacturing blocks too small ever to be reused.

Comparing the rules

policy	search cost	remainder it leaves	characteristic residue
first fit	short; stops at the first candidate	whatever is left over, often large	small remainders pile up near the list head
next fit	short; no re-walk of the head	same as first fit	allocations spread across the whole region
best fit	full walk, or a sorted list to maintain	the smallest possible	many leftovers too small to reuse

What the measurements actually say

The intuitive story — best fit wastes less, first fit is faster — is only half right, and the half that is right matters less than it sounds. Studies of real program traces have repeatedly found that once coalescing is in place, first fit and best fit land close to each other in memory use, and that the differences between them are smaller than the differences between workloads. The reason is that merging on release keeps regenerating large blocks, so the policy's choice of which block to carve matters less than whether the region is being knitted back together at all.

What did move the needle was removing the search: keeping a separate free list per size class, so the allocator indexes straight to a list of blocks of about the right size and pops the head. Best fit then becomes approximate and nearly free, because everything on the chosen list already fits.

How to reason about it in an interview

Say what the search costs in the worst case, not just the average: a single free list gives an unbounded walk, and a telemetry logger that must answer within a fixed budget cannot accept that at any average.
Say what the policy leaves behind, because that is what the next request pays.
Note that a size-ordered list turns best fit into first fit over that order; it does not make best fit free, it relocates the cost.
Resist the claim that one policy is strictly better. The honest answer is that both are workable with coalescing, and that the structural fix is segregation, not a cleverer rule.

Imagine a hand-written allocator inside an embedded telemetry logger: one region of memory, one linked list of the free blocks in it, and a request for `n` bytes arriving. The allocator must choose a block from that list. The rule it uses to choose is the **placement policy**, and the two classic rules are first fit and best fit. ## What each policy does **First fit** starts at the head of the list and takes the first block whose size is at least the rounded-up request. The search stops as soon as a candidate appears, so on a list with many adequate blocks it inspects only a handful. **Best fit** inspects every block and keeps the smallest one that is still large enough, stopping early only if it finds an exact match. On an unordered list that is a full traversal on every single request. If the list is instead kept sorted by size, best fit becomes the first adequate block in that order — but then every release must insert into a sorted structure, moving the cost from allocation to release rather than removing it. A third rule, **next fit**, is first fit with a rover: the search resumes where the previous one stopped instead of returning to the head. It avoids re-walking the crowd of small remainders at the front, at the cost of scattering allocations across the whole region. ## Splitting the winner Whichever block is chosen, it is usually bigger than the request, and the allocator must decide what to do with the surplus: 1. Round the request up to satisfy alignment and to leave room for the block's own tag. 2. If the leftover would be at least the **minimum block size** — big enough to carry a tag and the free-list links — split the block: the low part becomes the allocation, the remainder gets its own tags and goes back on the free list. 3. If the leftover would be smaller than that, hand out the whole block. The few surplus bytes sit inside the allocation, unusable but also untracked. That guard is what stops splitting from manufacturing blocks too small ever to be reused. ## Comparing the rules | policy | search cost | remainder it leaves | characteristic residue | |---|---|---|---| | first fit | short; stops at the first candidate | whatever is left over, often large | small remainders pile up near the list head | | next fit | short; no re-walk of the head | same as first fit | allocations spread across the whole region | | best fit | full walk, or a sorted list to maintain | the smallest possible | many leftovers too small to reuse | ## What the measurements actually say The intuitive story — best fit wastes less, first fit is faster — is only half right, and the half that is right matters less than it sounds. Studies of real program traces have repeatedly found that once **coalescing** is in place, first fit and best fit land close to each other in memory use, and that the differences between them are smaller than the differences between workloads. The reason is that merging on release keeps regenerating large blocks, so the policy's choice of which block to carve matters less than whether the region is being knitted back together at all. What did move the needle was removing the search: keeping a separate free list per **size class**, so the allocator indexes straight to a list of blocks of about the right size and pops the head. Best fit then becomes approximate and nearly free, because everything on the chosen list already fits. ## How to reason about it in an interview - Say what the search costs in the worst case, not just the average: a single free list gives an unbounded walk, and a telemetry logger that must answer within a fixed budget cannot accept that at any average. - Say what the policy leaves behind, because that is what the *next* request pays. - Note that a size-ordered list turns best fit into first fit over that order; it does not make best fit free, it relocates the cost. - Resist the claim that one policy is strictly better. The honest answer is that both are workable with coalescing, and that the structural fix is segregation, not a cleverer rule.

What does next fit change about first fit, and what does it give up?
Next fit resumes the search where the last one stopped instead of restarting at the head, so it stops re-walking the small remainders that first fit accumulates at the front. The price is locality: successive allocations land wherever the rover happens to be, spreading related objects across the region instead of clustering them, and the region tends to be touched more evenly rather than densely at one end.
Why is best fit not free even when the free list is kept sorted by size?
A size-sorted list makes the search itself cheap — the first adequate block is the best fit — but every release must now insert the block at the right position in that order, and merging changes a block's size and so its position. The work moves from the allocation path to the release path; a balanced structure keeps it logarithmic rather than removing it.
Why does a split need a minimum-size guard at all?
A free block has to store its own tag and its free-list links inside itself, so a remainder below that size could not be represented as a free block. Splitting anyway would either corrupt the list or create blocks that can never be reused. Handing out the whole block instead loses a few bytes inside the allocation, which is recovered in full when the block is released.

saying these in an interview costs you the question

Says best fit is strictly better because it wastes less memory
Thinks first fit never splits blocks at all
Believes best fit picks the largest adequate block
Assumes a single free list gives a bounded worst-case search
Forgets that the remainder has to be big enough to be tracked
Treats the placement policy as the main lever on memory use

A heap allocator searching one free list can take the first block that fits or the smallest; what does each policy cost?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

What each policy does

Splitting the winner

Comparing the rules

What the measurements actually say

How to reason about it in an interview

▾common follow-ups3 questions

▾red flags6 flags

What each policy does

Splitting the winner

Comparing the rules

What the measurements actually say

How to reason about it in an interview

answer

go deeper