skip to content

Why can an allocator's total free bytes overstate what it can actually hand out, and which second number corrects it?

level: seniorimportance: should knowfreq 45%

answer

  1. a sum assumes the pieces combine
  2. one request, one run
  3. largest run bounds a single allocation
  4. one minus largest over total
  5. merge neighbours before measuring

basics

~20 s

A request needs one contiguous run, but total free bytes sums runs that may be scattered. The largest contiguous free run is the corrective number: it, not the total, bounds the biggest single request that can be placed.

solid answer

~40 s

Free bytes are only usable together if they are adjacent. Total free is a sum over every free run in the heap; a request is served from **one** run, so the **largest contiguous free run** is the real ceiling on a single allocation. A heap with 400 MB free and a largest run of 2 MB can place nothing above 2 MB. The usual summary is the ratio `1 - largest_run / total_free`: near 0 means free space is effectively one region, near 1 means it is shattered — the 400 MB example scores 0.995. Measure it *after* adjacent free blocks are merged, or you are measuring bookkeeping rather than capacity. And read it against the request-size distribution: a ratio of 0.9 is harmless if every run still dwarfs the largest request.

code

pseudocode · 18 lines
pseudocode
total_free  = 0
largest_run = 0
i = 0

while i < block_count:
    if block[i] is free:
        run = 0
        while i < block_count and block[i] is free:
            run = run + block[i].size
            i = i + 1
        total_free = total_free + run
        if run > largest_run:
            largest_run = run
    else:
        i = i + 1

if total_free > 0:
    ratio = 1 - largest_run / total_free

go deeper

for a junior

Hold on to one fact: an allocation has to fit in a single unbroken piece of free space, so the total amount free is not the same as the biggest thing that can be allocated.

for a middle

Be able to state the ratio, its denominator, and what values near zero and near one mean. Work a concrete pair of numbers through it without hesitating.

for a senior

Demonstrate measurement judgment: coalesce before measuring, keep the definition of free stable, and interpret the ratio against a request-size histogram and a trend rather than a single sample.

for a principal

Decide what the fleet-wide metric should be and what it will trigger. A scalar is cheap to collect and easy to misread; say what second signal must accompany it before anyone is allowed to act on it.

## Why a sum is the wrong shape of number An allocation must be placed in one **contiguous** run of free bytes. Total free is a sum over every free run in the heap, and addition quietly assumes the pieces can be used together. They cannot. The number answers a question nobody asked: how many bytes are unowned. The question that matters is: how large is the biggest piece. That is why total free can be simultaneously true and misleading. It is not wrong about the bytes; it is wrong about capacity. ## The corrective number and the ratio Record two figures over the heap, after adjacent free blocks have been merged: - **`total_free`** — the sum of all free bytes. - **`largest_run`** — the size of the biggest contiguous free region. `largest_run` bounds the largest single request that can be placed without growing the heap. The conventional one-number summary is ``` fragmentation_ratio = 1 - largest_run / total_free ``` with the convention that it is undefined when `total_free` is zero. It reads as *the share of free space that is not in the single biggest piece*: | total_free | largest_run | ratio | Reading | |---|---|---|---| | 400 MB | 400 MB | 0.000 | Free space is one region | | 400 MB | 300 MB | 0.250 | Mildly broken up | | 400 MB | 40 MB | 0.900 | Many runs, still large ones | | 400 MB | 2 MB | 0.995 | Shattered into small pieces | The 400 MB heap with a 2 MB largest run can place a 2 MB request and nothing bigger, even though it holds two hundred times that in free bytes. ## Two ways to compute it wrongly 1. **Measuring before merging neighbours.** If the accounting walks a free list that still records adjacent regions separately, `largest_run` reflects how the allocator has chosen to record free space, not how much contiguous space exists. Scan the heap in address order and coalesce runs while measuring. 2. **Counting reserved-but-untouched space as free.** Address ranges that have been set aside and never used are contiguous and enormous, which flatters the ratio. Decide whether the metric describes the region the allocator already manages or everything it could grow into, and keep that choice fixed. ## The ratio alone does not decide anything The ratio is a property of free space only. It becomes actionable only next to the **request-size distribution**: - A ratio of 0.9 is harmless if the smallest run comfortably exceeds the largest request the workload ever makes. Many small runs are exactly what a workload of many small requests wants. - A ratio of 0.3 is alarming if the workload periodically needs a single region larger than `largest_run`. - The right companion metric is therefore a **histogram of free-run sizes** against a histogram of request sizes — not a single scalar. It is also an instantaneous reading. One sample says nothing about direction; a ratio that climbs steadily across a long run is a different story from one that oscillates around a stable value as the workload breathes. ## Where the two wastes appear in the accounting The pair is blind to rounding waste, symmetrically to how a requested-versus-occupied table is blind to gaps. Bytes idling inside a live block are *occupied*, so they never enter `total_free` at all. A complete picture needs both pairs of numbers: - `occupied - requested` for the waste inside blocks; - `total_free` against `largest_run` for the waste between them. ## What an interviewer is checking That you reach for contiguity rather than volume, that you know the ratio's denominator and what a value near each end means, that you would coalesce before measuring, and that you would not act on the ratio without knowing what sizes the workload actually asks for. The weak answer treats a large free total as proof of health; the strong one asks which piece the next request has to fit into.

  • When is a high fragmentation ratio harmless?
    When the runs are still bigger than anything the workload asks for. A ratio of 0.9 over runs that are all several megabytes is fine for a workload whose largest request is a few kilobytes. The ratio describes free space alone; only the request-size distribution makes it good or bad news.
  • What does a single ratio reading hide?
    Direction and distribution. One sample cannot distinguish a stable value the workload oscillates around from one climbing across a long run, and a scalar collapses the whole free-run histogram into its largest element — so it cannot tell a heap with one huge run plus dust from one with many medium runs.
  • Why measure after coalescing adjacent free blocks?
    Because before merging, the figure reflects how the allocator happens to record free space rather than how much contiguous space exists. Two adjacent free blocks recorded separately understate the largest usable run and make the heap look far more broken than it is.

Twelve empty single seats scattered around a cinema add up to more than a row of four, but a family of four can only sit in the row. Capacity depends on the biggest contiguous piece, not the total count.

saying these in an interview costs you the question

  • Treats total free bytes as the largest request that can be served
  • Reports the ratio without first merging adjacent free neighbours
  • Reads a high ratio as a problem without knowing the request sizes
  • Counts reserved-but-untouched address space as free contiguous room
  • Expects the total-free and largest-run pair to reveal rounding waste inside blocks