High Water

Everyone picks the growth factor by counting copies. Geometric growth makes push amortized O(1), arithmetic growth makes it O(n), and the argument is over before anyone has looked at the heap underneath. So this puts one there — a first-fit free list with coalescing, over a bump pointer — and reallocates through it, which makes the second bill arrive.

The waterfall is one row per allocation generation: the whole address space, drawn at the scale it has reached by that step. Teal is elements that exist, dark teal is capacity bought and not yet used, grey is freed space, and the pale tick on the right is the high-water mark — the furthest address the process has ever touched, which is the number the operating system actually charges for.

At ×2 the rows march to the right and never come back.

Short by one, forever

Step through it and watch the two bars under the fall. They are the only comparison the allocator makes: the longest run of freed space against the block being asked for.

cap 64 → 128:   free run 63      asked for 128     short by 65
cap 128 → 256:  free run 127     asked for 256     short by 129
cap 256 → 512:  free run 255     asked for 512     short by 257

The free run is 1 + 2 + 4 + … + 2^k, which is 2^(k+1) − 1, and the block being abandoned is 2^(k+1). So everything the array has ever freed, added together and perfectly coalesced into one run, is one element short of the block it is about to walk away from — and a hair under half of the one it is asking for. Not usually. Not at these sizes. Every time, at every n: the header counts the reuses and it reads 0 after eighteen reallocations and 131,071 elements of freed space, and it reads 0 for every n from 1 to 20,000.

Which means the free list is dead code. Switch freed space to never reuse — bump only and the run does not change: same generations, same addresses, same high water of 262,143, to the element. An entire allocator mechanism, sitting under the most-used data structure in the language, that never fires once.

The high water settles at exactly 2× the capacity — and capacity peaks at twice the live elements, so the worst moment of a ×2 array is 3.9997 addresses touched per element you are actually storing, which the fall reaches at n = 16,385.

The threshold is the golden ratio, and rounding decides it

Wind the factor down and at some point the arithmetic flips. Reuse needs the freed run to cover the next block:

1 + r + r² + … + r^(k−1)  ≥  r^(k+1)
      (r^k − 1)/(r − 1)   ≥  r^(k+1)

which in the limit is r² − r − 1 ≤ 0, so r ≤ φ. That is where the folklore number comes from, and the simulation lands on it hard. Over 100,000 pushes:

The flip sits between 1.617 and 1.618. It is a knife edge in the literal sense: at exactly φ the inequality is an equality, so the rounding mode in newCap = ceil(cap × φ) is the whole decision. Round up and you get 0 reuses; round down — floor instead of ceil, one word — and the same factor reuses twice. There is no tolerance either side of it to hide in.

The first reuse under ×1.5 is worth watching frame by frame, because the numbers are small enough to check by hand. Capacities go 1, 2, 3, 5, 8, 12, 18; at the seventh generation the freed run is 19 and the request is 18, the block lands back at address 0, and the high-water tick stops at 31 and stays there while the array doubles again underneath it.

What reuse is worth, and what it costs

Running the free list against the same stream with it switched off, 100,000 elements each:

Three exact ties and then a column that starts doing work, which is the clearest statement of the threshold the demo has. And the last column is the bill you pay for it: there is no factor that both takes its memory back and copies each element about once. +8 reuses 12,469 times and is still the worst row in the table on footprint — reuse does not make arithmetic growth frugal, it only stops it being catastrophic, and it charges 6,249 copies per element for the favour.

The move that makes all of this go away

Tick grow in place. Copies per element goes to 0.000 and the high water goes to 131,072, which is exactly the capacity — no waste at all, because nothing was ever abandoned. This is realloc’s cheap path: if the space directly above the block is free, extend it there and copy nothing.

It is also the path a C++ std::vector structurally cannot take. An Allocator offers allocate and deallocate and nothing in between, so there is no way to ask “can this block get bigger where it is?” — and even with one, the elements would have to be trivially relocatable for the answer to be usable. The entire table above is a consequence of an interface, not of arithmetic.

And it is conditional on an empty heap, which is why there is a second client. Set heap to a second client allocating and its small long-lived blocks start landing directly above the array: in-place growth now succeeds 13 times out of 18 instead of 17, and copies per element goes from 0.000 to 0.088. The purple blocks in the fall are the ones in the way.

Reading it

←/→ scrub, space plays, clicking a row jumps to that generation. The gutter on the far left marks what each generation did — teal for a reuse, purple for an in-place grow — so the events stay findable when there are 249 rows and no room for labels. The two bars at the bottom are the bills, on a log axis because +8 is four orders of magnitude away from the rest; the faint ticks on them are where the other five factors land on the same stream.

Reuse

src/high-water.js is a framework-free ES module:

• Heap — a first-fit (or best-fit) free list with coalescing over a bump pointer. alloc, free, extendInPlace, regions() for drawing, largestHole(), freeBytes().
• simulate({ n, growth, fit, tenants, inPlace, seed }) — one frame per allocation generation, each carrying the heap state after it and the comparison made before it (runBefore, spaceAbove, needed), so a renderer can scrub in both directions. Reports highWater, copies, reuses, inPlaceGrows, copiesPerElement, peakWaterPerCap.
• compare({ n, fit, tenants, inPlace }) — the same push stream under all six growth factors, which is what the ghost ticks are.
• GROWTH, GROWTH_ORDER, FITS, TENANTS — the vocabulary, so the demo’s selects are generated rather than transcribed.

No rendering and no timers in the module; the canvas demo is reference code.

Gotchas

• copiesPerElement is sampled, not asymptotic. It depends on where n falls relative to the last growth, and sweeps the whole band [1/(r−1), r/(r−1)] as n moves: measured over n = 1,000…20,000 it covers 0.999–2.000 for ×2 and 1.991–2.999 for ×1.5. Quoting one n as “the” copy cost is the mistake the band exists to stop.
• runBefore is the number the decision turned on, captured before the allocation. largestHole on the same frame is the state afterwards and is not what was compared — reading the wrong one makes the demo claim a block fit in a hole smaller than itself.
• First-fit and best-fit are the same run with nothing else allocating: the array’s corpses coalesce into one hole and there is no choice to make. They diverge in 8 of 72 configurations, all of them with the second client on — and not always the way you would guess. At ×1.25 with tenants and 20,000 elements, first-fit ends at 39,583 and best-fit at 65,474.
• One unit is one element, not one byte. There is no header, no alignment and no size class, which is the simplification that lets the ×2 arithmetic come out exactly one short. A real malloc rounds to a size class and the shortfall gets worse, not better.
• reserve() changes everything and is not modelled. The whole picture is about an array that learns its size by being surprised.
• The demo bundles its own copy of high-water.js (self-contained by contract); re-copy after editing src/.
• node scripts/screenshot-demo.mjs [out] [--growth=] [--fit=] [--tenants=] [--inplace] [--n=] [--at=end|<gen>] [--w= --h=] regenerates thumb.png through site/scripts/lib/chromium.mjs.