Why does a linked list of 10 million 8-byte readings dwarf a flat buffer in memory?

## The claim under audit "Linked structures save memory because they allocate only what they need." It sounds right — no reserved capacity, no empty slots, one allocation per element that arrives and one freed per element that leaves. It is wrong for small payloads, and the audit that proves it is arithmetic anyone can do at a whiteboard. ## Costing one node Take ten million sensor readings, eight bytes each. Stored in one flat buffer, that is 80 MB and essentially nothing else: the elements are the storage. Stored as a chain, each reading becomes an independent heap record. Count what that record costs on a typical 64-bit machine: | Component | Typical size | | --- | --- | | The reading itself | 8 bytes | | Link field (reference to the next node) | 8 bytes | | Per-allocation header / bookkeeping | 8-16 bytes | | Alignment and size-class rounding | 0-8 bytes | | **Total per element** | **24-32 bytes** | Three to four times the payload — and the payload is the only part that carries information. Ten million readings become roughly 240-320 MB. Every extra link field a design adds is another word per node on top of that, and if the node stores a *reference* to the reading rather than the reading inline, you pay a second allocation and a second header for the value itself. Two secondary costs usually go unmentioned in the interview and are worth raising: - **Allocator bookkeeping beyond the header.** Millions of small live blocks give an allocator its worst case: metadata, free-list structure, and internal fragmentation across size classes. - **Nothing is amortized away.** The overhead is strictly per element. Doubling the element count doubles the wasted bytes; there is no fixed cost to spread. ## The honest comparison Contiguous storage is not free of waste. A buffer that grows by doubling carries unused capacity between growth events — in the worst case just after a growth, roughly half the block is slack, and the amortized average is smaller. So the fair statement is: a contiguous buffer wastes up to about 50% at a bad moment, and can be trimmed to exact size when it stops growing; a chain of small nodes wastes 200-300% permanently, and cannot be trimmed because the waste is structural. The balance shifts with payload size. If each element is a 400-byte record, a 24-byte wrapper is 6% overhead and nobody cares. The blow-up is a small-payload phenomenon, which is exactly why "eight-byte readings" is the shape that exposes it. The other thing that shifts the balance is *churn*: if half the elements are removed, a chain returns their memory immediately, while a contiguous buffer keeps its capacity until something explicitly shrinks it. ## Where the fixes actually live When the audit says the wrapper is the problem, the standard moves are structural, not micro-optimizations: - **Store more per node.** Give each node a small block of readings instead of one, so the header and link amortize over dozens of values. This is the classic unrolled-chain compromise and it recovers most of the density while keeping cheap splicing at block granularity. - **Allocate nodes from a pool.** Carving nodes out of one large region removes most of the per-allocation header and rounding cost, at the price of managing the region's lifetime. - **Keep the payload inline.** A node holding the value directly costs one allocation; a node holding a reference to a separately allocated value costs two, with two headers and an extra hop on every read. ## The interview move When a candidate asserts the memory saving, the interviewer is waiting for one number: the ratio of wrapper bytes to payload bytes. Producing "about 24-32 bytes for 8 bytes of data, so three to four times" — with the caveat that it depends on the machine's word size and the allocator's rounding — is the answer that ends the discussion. Refusing to give any number, or giving one with false precision as though it were universal, are the two ways to lose it. Mainstream runtimes differ here in ways worth knowing: managed environments typically attach an object header of one to two words to every heap record for type and bookkeeping purposes, while an unmanaged allocator adds its own block header instead — the header is smaller in some setups and larger in others, but no mainstream environment gives you a per-element allocation for free. The magnitude of the multiplier moves; the direction never does.