skip to content

Why can no allocator that never relocates a block promise to keep total memory within a constant factor of its live set?

level: seniorimportance: nice to knowfreq 22%

answer

  1. worst case, not typical case
  2. quantified over every placement policy
  3. adversarial free-every-second-block sequence
  4. scales with the size ratio's logarithm
  5. escape by moving or by restricting sizes

basics

~10 s

Because placement alone cannot defeat an adversarial request order. A classical worst-case result shows required memory grows with the live set times the logarithm of the largest-to-smallest request size ratio, for every fixed-placement policy.

solid answer

~50 s

If a block can never move, where it goes is decided the moment it is allocated, using no knowledge of what comes next. An adversary exploits that: allocate many small blocks, free alternating ones, then request a size that fits in none of the holes, and repeat the trick at each size scale. A classical result — usually attributed to Robson — shows the worst-case memory needed grows in proportion to the peak live bytes multiplied by the **logarithm of the ratio between the largest and the smallest request size**. No placement policy escapes it, because the bound is proved over all of them; better policies only match it up to a constant. The practical reading: gap waste is structural to *varied sizes plus fixed placement*, not an implementation defect. Narrow the size ratio, or move blocks, or reclaim regions wholesale.

go deeper

for a junior

The takeaway is simple: free space breaking into unusable pieces is a consequence of varied sizes plus blocks that never move, not a sign that someone wrote a bad allocator.

for a middle

Be able to sketch the adversary — many small blocks, free every second one, then ask for something that fits in none of the holes — and say what the factor depends on.

for a senior

Use it to redirect a design argument: since no placement rule bounds the waste by a constant, discuss the three escapes and their prices instead of hunting for a smarter fit.

for a principal

Treat it as a risk statement. Decide how far your workload sits from adversarial, what the size ratio actually is, and whether narrowing that ratio is cheaper than adopting relocation or a phase structure.

## What the bound actually says For an allocator that never relocates an allocated block, there exist request sequences on which the memory it must hold is proportional to ``` M x log(n) ``` where **M** is the peak number of bytes simultaneously live, and **n** is the ratio between the largest and the smallest request size the workload uses. The result is usually attributed to Robson. Read the quantities carefully, because the direction of each one matters: - It is a statement about the **worst case** over request sequences, not about typical behaviour. - It applies to **every** fixed-placement policy, which is why it cannot be answered with a cleverer choice of where to put the next block. - It grows with the **size ratio**, not with the number of requests or the number of threads. - The log factor is modest: a workload spanning 16 bytes to 16 KB has a ratio of 1,024, so the factor is around ten, not thousands. ## The idea of the adversary The argument does not need the proof, only the shape of the attack, which is what an interviewer wants: 1. Fill a region with many blocks of the smallest size. 2. Free every second one. Half the bytes are now free, in holes of exactly one small block each. 3. Request a block of twice that size. It fits in none of the holes, so fresh space must be used. 4. Repeat at the next scale, and the next. Every step leaves behind free bytes that the following step cannot use, and each doubling of the size adds another layer of stranded space. The number of scales available is what the logarithm counts. ## Why placement cannot rescue it A fixed-placement allocator commits a block's address with no knowledge of the future. Whatever rule it uses, the adversary picks the sequence afterwards. This is the part candidates most often get backwards: they propose a policy as the answer to a bound that is quantified over all policies. Policies still differ enormously in practice — and some that look appealing on average have notably worse worst cases than the simple ones — but the existence of *some* bad sequence is not a policy question. ## The three genuine escapes | Escape | What it changes | What it costs | |---|---|---| | Narrow the size ratio | Shrinks the log factor towards one; with a single size the problem essentially vanishes | Rounding waste inside blocks, plus per-class idle reserve | | Relocate live blocks | Placement is no longer permanent, so contiguity can be restored | Every reference to a moved block must be updated, which requires indirection or exact knowledge of every reference, and a pause or a barrier | | Reclaim a region wholesale | Free space returns as one piece by construction | Nothing is reclaimed before the boundary, so the program must have a phase structure to reset at | Notice that two of the three do not make the heap tidier at all; they change the *question* the allocator is asked. That is the deeper lesson. ## What the bound does not claim This is where an overconfident answer goes wrong: - It does **not** say real programs suffer the worst case. Measured overheads for well-designed allocators on realistic workloads are a modest fraction, not a logarithmic blow-up, because real request sequences are nothing like the adversary's. - It does **not** rank policies. It bounds all of them from below in the worst case and says nothing about which is better on a given workload. - It does **not** concern the waste inside a block. Rounding waste is a separate quantity with its own, much simpler bound. - It does **not** imply that growing the heap is a fix; growth is what the bound is measuring. ## Why it is worth knowing It reframes gap waste from a bug to be fixed into a property to be engineered around. Once you accept that no placement rule bounds it by a constant, the design conversation moves to the three escapes and their prices, and the measurement conversation moves to how far a given workload sits from the worst case — which is an empirical question about the request-size histogram, not a theoretical one.

  • What does this result NOT say?
    It does not say ordinary programs pay that cost; the bound is over adversarial sequences, and measured overhead on realistic workloads is far smaller. It also does not rank placement policies against each other, and it says nothing about the waste inside a block, which has its own separate and simpler bound.
  • How does a design that relocates live blocks escape the bound?
    The bound is proved for allocators whose placement is permanent. If blocks can move, contiguity can be restored after the fact, so the argument no longer applies. The price is that every reference to a moved block must be updated, which demands either indirection through a handle or exact knowledge of where every reference lives.
  • Why does the bound depend on the size ratio rather than the number of requests?
    The adversary works scale by scale, stranding free space at each size before moving to a larger one. The number of usable scales is the logarithm of the largest-to-smallest ratio, so that is what the factor counts. Making more requests at the same sizes does not add scales.

saying these in an interview costs you the question

  • Answers a bound quantified over all policies by proposing a better placement policy
  • Reports the worst case as what typical workloads actually pay
  • Thinks the factor grows with request count or thread count rather than the size ratio
  • Believes the result also bounds the rounding waste inside blocks
  • Claims a sufficiently large heap makes the result irrelevant