skip to content

In an allocator that puts a size tag on every block, what does that metadata cost a workload of millions of small records?

level: seniorimportance: nice to knowfreq 30%

answer

  1. charged per block, not per byte
  2. worst where the blocks are smallest
  3. a footer doubles the tag
  4. minimum block size for the links
  5. record the class once per run

basics

~20 s

A per-block tag is a flat tax paid once per block, so it is worst where blocks are smallest: an eight-byte tag beside a 24-byte record is a third of the payload again, and a quarter of everything the allocator holds for it.

solid answer

~50 s

Every block an allocator tracks individually needs somewhere to record its size and state, and that space is proportional to the *number* of blocks, not to their total size. A telemetry logger allocating millions of 24-byte records through an allocator with an eight-byte tag pays 8 bytes per record — a third as much again as the payload, and one quarter of the 32-byte block. Keeping a footer as well on allocated blocks doubles the tag to 16 bytes, two thirds of the payload. A minimum block size makes it worse for tiny requests, because a free block must be able to hold its own list links. The structural fix is to stop tagging individual blocks: record the size class once for a whole run of same-class cells, so the metadata is amortised across the run.

go deeper

for a junior

Recall that a block costs more memory than the bytes you asked for, because the allocator has to store the size somewhere.

for a middle

Explain the components — tag, alignment rounding, minimum block size — and why the cost is charged once per block rather than per byte.

for a senior

Do the arithmetic on a real profile: live blocks times per-block tag against bytes requested, and recognise that the fix is fewer separately tracked blocks, not a setting.

for a principal

Judge whether to buy density by fixing a run of memory to one size class, giving up the ability to re-carve it, and say what would make you reverse that.

Allocator overhead is usually discussed as a percentage of the heap, which hides the thing that actually bites: per-block metadata is charged **per block**, so its relative cost is set entirely by how small the blocks are. A workload of a few large buffers barely notices it. A telemetry logger that allocates millions of small fixed-shape records notices nothing else. ## What sits beside a block - **The header.** One word recording the block's size plus a few flag bits. It has to exist because the release path is given only a payload address and must recover the block's size from it. - **The footer**, where boundary tags are used, repeating the size so the block above can step backwards. Many designs keep it only in free blocks and carry a previous-block-is-free bit in the header instead, halving the tag on allocated blocks. - **Alignment padding.** The payload must start on an aligned address and the block must be a multiple of the alignment unit, so the tag plus payload is rounded up to that unit. - **A minimum block size.** A free block must store its free-list links inside itself, so no block can be smaller than a tag plus those links, however small the request was. ## The arithmetic, done honestly Take 24-byte records and an eight-byte tag, aligned to 8: 1. The block is 24 + 8 = **32 bytes**. 2. The tag is 8 / 24 = **one third** of the payload, expressed as extra. 3. The tag is 8 / 32 = **one quarter** of what the allocator actually holds for that record. 4. Ten million live records therefore carry **80 MB** of tags on 240 MB of payload. Now keep a footer on allocated blocks too. The tag becomes 16 bytes, which is 16 / 24 = **two thirds** of the payload — not half, a mistake that is easy to make and easy to catch by doing the division. This is exactly why the previous-block-is-free bit exists: it buys back an entire word on every live block. | per-block tag | block for a 24-byte record | tag as share of payload | tag as share of block | |---|---|---|---| | 8 bytes, header only | 32 bytes | 33% | 25% | | 16 bytes, header and footer | 40 bytes | 67% | 40% | | none, class recorded per run | 24 bytes | 0% | 0% | ## Why the tax does not amortise Most overheads shrink as a program gets bigger, because they are fixed costs spread over more work. This one does not: doubling the number of records doubles the number of tags. That makes it a **design** problem rather than a tuning problem. You cannot configure it away; you can only change how many separately tracked blocks exist. It also has a second-order cost. Tags are interleaved with payloads, so a scan over many small records touches tag words it does not care about, and each cache line holds fewer useful bytes than the payload size alone would suggest. ## Getting the tag out of the block The in-design answer is to stop tagging blocks individually. If the allocator carves a whole run of memory into cells of a single size class, then the size of every cell in that run is known from the run, not from the cell. The run's descriptor records the class once, the cell address determines which run it belongs to, and the release path recovers the size by looking at the run rather than at a word beside the payload. Individual cells then carry **no** tag at all. What that costs is flexibility: cells in such a run cannot be split or merged into a different size, because there is no per-block size to change. That is the same trade seen from the other side — per-block tags are the price of a heap whose blocks can be re-carved, and dropping them buys density in exchange for fixing a run's class for its lifetime. ## Diagnosing it The measurement that settles the argument is the number of **live blocks**, not the number of live bytes. Multiply live blocks by the per-block tag and compare that with the bytes the program believes it asked for. If the ratio is embarrassing, the fix is structural: fewer, larger allocations, or an allocator design that keeps its metadata out of line.

  • Why does a minimum block size exist even for a one-byte request?
    Once released, a block has to sit on a free list, and the links that put it there are stored inside the block itself, alongside its size tag. A block too small to hold those links could never be represented as free. So the allocator establishes a floor and serves every tiny request from a block of at least that size, which is why a one-byte request and a sixteen-byte one can cost the same.
  • How can a design drop the per-block tag entirely?
    By making the size a property of the memory region rather than of the block: carve a run of memory into cells of one size class and record that class once in the run's descriptor. The release path maps a cell address to its run and reads the class from there. The cost is that cells in the run can no longer be split or merged into another size.

saying these in an interview costs you the question

  • Treats allocator overhead as a fixed percentage of the heap
  • Assumes the tag becomes negligible once the program allocates enough
  • Thinks a one-byte request occupies one byte plus a tag
  • Says a header and footer together are half a 24-byte payload
  • Believes metadata can be tuned away without changing the design