Choosing a growth factor

A dynamic array that has run out of room allocates a bigger one and copies. How much bigger?

Any factor above 1 gives an amortised constant cost per append, so the complexity class does not decide it. The choice is entirely in the constants, and the constants pull in opposite directions: a larger factor means fewer copies and more memory sitting unused, a smaller factor means the reverse.

Measured, appending twenty thousand elements:

Reading the trade #

The shape is a hyperbola, and the interesting part is how quickly the returns diminish.

Going from ×1.125 to ×2 cuts the amortised cost by a factor of 3.7, from 9.89 to 2.64. Going from ×2 to ×4 cuts it by a further 21%, from 2.64 to 2.09, and costs an extra 30 percentage points of wasted memory. The elbow is somewhere between 1.5 and 2, which is where essentially every implementation lands.

Note that ×3 does not sit neatly between ×2 and ×4 — it measures 2.48 and wastes 66%, worse on the memory axis than ×4 by only three points while giving up most of the time saving. Where the final capacity happens to land relative to $n$ is doing that, which is the next paragraph’s subject.

The waste column deserves care, because it is not monotone and the non-monotonicity is real rather than noise. Growing by ×1.25 leaves only 1% unused at twenty thousand elements, less than ×1.125’s 10%, because where the final capacity falls relative to $n$ depends on the exact sequence of allocations and can land almost exactly on $n$ by luck. The waste figure is a snapshot at one $n$, and the honest quantity is the expected waste over a uniformly random stopping point, which for factor $g$ is about $\frac{g-1}{2g}$ — 25% for doubling, 17% for ×1.5, 10% for ×1.25.

The measured single-$n$ figures are noisier than that formula and bracket it, which is worth knowing before quoting either.

Why the factor does not change the class #

Worth pausing on why every factor above 1 gives the same complexity class, because it is the reason the choice is a pure constant-factor question.

With growth factor $g$, the capacities are $1, g, g^2, \ldots$ and the total copying to reach $n$ elements is

$$1 + g + g^2 + \cdots + g^k = \frac{g^{k+1}-1}{g-1} \approx \frac{g}{g-1}\, n$$

Divided by $n$ appends, that is $\frac{g}{g-1}$ — a constant for any fixed $g > 1$, and one that blows up as $g$ approaches 1. Substituting: $g = 2$ gives 2, $g = 1.5$ gives 3, $g = 1.25$ gives 5, $g = 1.125$ gives 9.

Those are exactly the measured numbers, to within the rounding that ceil introduces at small capacities: 2.64, 3.73, 5.04, 9.89 against predicted 2, 3, 5, 9 plus one unit per append for the writes themselves. The formula and the simulation are two independent routes to the same quantity and they agree, which is the discipline this site applies wherever two routes exist.

The blow-up as $g \to 1$ is the same limit that makes a fixed-step array quadratic. There is no discontinuity: the cost per append is $\frac{g}{g-1}$, which is finite for every $g > 1$ and infinite in the limit, and a fixed step is that limit.

The peak is worse than the waste #

There is a second memory cost that the table above does not show and that decides the question in some systems.

During a resize, both arrays exist at once. Growing a doubling array from capacity $c$ to $2c$ requires $3c$ elements of memory momentarily. The peak footprint is 1.5 times the new capacity, and close to a memory limit, that transient peak is what fails.

Growing by ×1.5 has a peak of $2.5c$ against a new capacity of $1.5c$ — a ratio of 1.67, worse relative to the result but smaller in absolute terms. The comparison depends on which quantity is the binding constraint, which is a familiar refrain on this site: the ranking depends on which count is chosen, and here the two counts are peak memory and steady-state memory.

The allocator argument for 1.5 #

There is a widely repeated argument that growth factors below the golden ratio $\varphi \approx 1.618$ allow an allocator to reuse previously freed blocks, and that this is why several standard libraries use 1.5.

The argument goes: with factor $g$, the sum of all previously freed capacities is $1 + g + g^2 + \cdots + g^{k-1} = \frac{g^k - 1}{g - 1}$. For the next allocation of size $g^{k+1}$ to fit in that freed space requires $\frac{g^k-1}{g-1} \ge g^{k+1}$, which for large $k$ requires $g^2 - g - 1 \le 0$, giving $g \le \varphi$. With doubling, the freed blocks are always one short of what is needed, so the array marches forever upwards through the address space and never reuses anything.

It is a genuinely elegant piece of reasoning and its practical force depends entirely on the allocator. It assumes the freed blocks are contiguous and coalesced, which requires that nothing else allocated in between — an assumption that fails in most real programs. Modern allocators also use size classes, so a request for $1.5c$ and a request for $2c$ may land in the same bucket and behave identically.

So: a real consideration, frequently overstated, and impossible to settle from this site’s measurements because the site models an array and not an allocator. Where an implementation has chosen 1.5 there is usually a benchmark behind it as well as the argument.

The arithmetic half of it can be settled, and it arrives later than advertised #

What can be checked here is the counting the argument rests on, and the check is worth doing because the argument is always stated asymptotically and every real array starts at capacity 1. Capacities are integers, growth is $\lceil gc \rceil$, and the question is at which resize the freed blocks first add up to the next request.

Doubling behaves exactly as the argument says: $1 + 2 + \cdots + 2^{k-1} = 2^k - 1$, one byte short of the $2^k$ being asked for, at every resize, forever. It is a strikingly tidy failure and it is the reason the argument gets repeated.

The golden ratio itself also never works, which the asymptotic statement obscures. $\varphi$ is the value at which the inequality becomes an equality in the limit, so rounding capacities up puts every finite case on the wrong side of it. A growth factor “below $\varphi$” has to be meaningfully below it to do anything.

And 1.5 — the factor the argument is usually invoked to justify — does not reuse anything until the sixth resize. An array that never exceeds a few thousand elements has had perhaps eight or nine resizes in its whole life, so the property is available for the last three or four of them and the first five behave exactly like doubling. For the small arrays that make up most of the arrays in most programs, the allocator argument describes a benefit that has not started yet.

None of that refutes the argument; it bounds it. The elegant asymptotic statement is true, the factor libraries actually chose reaches it late, and the case where it matters most — a single array growing to a large size in a program that allocates nothing else — is the case that is easiest to fix by reserving the capacity up front instead — which a later section here measures, and which makes the growth factor irrelevant rather than optimal.

Growing by a fixed amount is the mistake #

The failure worth naming is growing by a constant amount rather than a constant factor: capacity increases by 1, or by 16, or by 1,024, each time it fills.

This is quadratic. With a step of $s$, the resizes happen at sizes $s, 2s, 3s, \ldots$ and the total copying is $s(1 + 2 + \cdots + n/s) \approx \frac{n^2}{2s}$. Dividing by $n$ appends gives $\frac{n}{2s}$ per append — which grows with $n$ and is therefore not a constant at all.

It is an easy mistake to make and a hard one to notice, because for small $n$ and a decent step size the cost per append is small and the structure works perfectly. The quadratic nature shows up only when the data gets big, which is usually in production.

The site’s gate asserts that the amortised-constant check refuses a fixed-step array. That is the must-reject discipline applied here: a check that accepted a quadratic append would be certifying nothing, and there would be no other symptom.

The measurement across sizes is how the difference becomes visible. A doubling array’s amortised cost is 2.023 at 1,000 appends and 2.024 at 64,000 — flat to four digits across a factor of 64. A fixed-step array’s would rise by the same factor of 64.

Two more sizes, an order of magnitude apart, say what does and does not move. The shape is fixed — no point is below and left of every other at any size — and the numbers on the axes are not.

What the standard libraries do #

The published choices, for context rather than as authority:

• C++ std::vector — the standard specifies only amortised constant. GCC’s libstdc++ doubles; MSVC’s implementation uses 1.5.
• Java ArrayList — grows by 50%, i.e. ×1.5.
• Python list — grows by roughly ×1.125 plus a constant, deliberately modest, with the small additive term keeping the tiny cases sane.
• Rust Vec — doubles, with a minimum first allocation depending on element size.
• Go slices — doubled below 256 elements and then grow by a decreasing factor approaching ×1.25, an explicit attempt to get the best of both regimes.

The range is 1.125 to 2, which is exactly the range where the measured curve has its elbow. The disagreement is not carelessness; it is different weightings of a trade-off that has no dominant answer, made by people optimising for different workloads.

Python’s ×1.125 is the outlier and the reasoning is visible in its behaviour: with an amortised cost near 10 units per append it is the most expensive on the table, and CPython’s per-append overhead is dominated by interpreter dispatch rather than by memory copying, so ten units of copying costs proportionally much less than it would in C. The memory saving is real and the time cost is hidden by a larger constant elsewhere — which is a decision that only makes sense once the constants in that context are known.

The shrink question #

A dynamic array that only ever grows is easy. One that also shrinks when elements are removed has a trap in it, and the trap has the same shape as everything else on this page.

The naive rule — halve the capacity when the array is half empty — produces thrashing. Sit exactly at the boundary and alternate one append with one removal: the append triggers a growth and copies everything, the removal triggers a shrink and copies everything back, and every single operation costs $\Theta(n)$. The amortised bound is destroyed by a sequence that does nothing.

The fix is hysteresis: shrink only when the array is a quarter full, halving to half full. Now after a resize the array is far from either boundary, and $\Theta(n)$ operations must happen before another resize can be triggered — which is exactly the condition the amortised argument needs.

This is a good illustration of why amortised bounds are about sequences and cannot be checked one operation at a time. Both rules make every individual operation look identical. Only a sequence distinguishes them, and only an adversarially chosen sequence distinguishes them quickly.

Reserving up front #

There is a way to avoid the whole question, and it is worth naming because it is usually the right answer when it is available.

If the final size is known in advance, reserve it. One allocation, no copies, no waste, no growth factor. The amortised cost falls to exactly one unit per append — the write — and the sawtooth disappears entirely.

Measured against a doubling array’s 2.02 units per append, reserving halves the cost of building a large array, and against ×1.125 it divides it by ten. That is a much larger saving than any choice of growth factor buys, and it is available whenever the size is computable or even roughly estimable — reserving too much wastes memory once and copies nothing.

This is the general shape of the best optimisations on this site: not a better algorithm within the constraints, but a change to the constraints. Counting sort escapes the comparison floor by not comparing; reserving escapes the growth-factor trade by not growing. In both cases the escape needs extra information — a bounded key range, or the final size — and the information is often available for the asking.

The right factor is a function of the size, and one library says so #

Go’s rule is listed above as an outlier — double below 256 elements, then approach ×1.25 — and it is the only entry on that list that is not a single number. It is also the one the arithmetic in this essay most clearly supports, and the reason is a mismatch between the two axes.

The cost per append is scale-free. It is $g/(g-1)$, which mentions no $n$ at all: doubling costs two units per append whether the array holds ten elements or ten million.

The waste is not. It is about $\frac{g-1}{2g}$ of the capacity, which is a proportion — and a proportion of a small number is a small number. Doubling an array that ends at a hundred elements leaves twenty-five slots unused, which nothing anywhere cares about. Doubling one that ends at a hundred million leaves twenty-five million, which is a decision somebody has to defend.

So the two axes are not commensurable across scales. At small sizes only one of them has a number worth looking at, and the trade collapses: take the cheap-per-append factor, because the waste it produces is not a quantity. At large sizes the waste becomes real and the trade reappears.

Which is exactly Go’s rule, derived rather than benchmarked. Below a couple of hundred elements, double — the copying saving is real and the waste is a rounding error. Above it, shrink the factor towards 1.25 — the copying saving is the same proportion of a much larger absolute cost, and so is the waste, and now they compete.

Two things follow that are worth stating separately from the rule.

A fixed factor is a compromise across sizes rather than across workloads. Every library on the list except Go has picked one number to serve arrays of ten elements and arrays of ten million, and the arithmetic says those two cases want different answers. Python’s ×1.125 is the choice that most favours the large case and most penalises the small one, which is why it carries an additive term to keep the tiny arrays sane — a correction whose existence is evidence for the same mismatch.

And the threshold is correctly absolute. Two hundred and fifty-six is a number of elements with no $n$ in it, and that is right for once: the question it answers is is this array small enough that its waste is not a quantity, and “small enough not to matter” is an absolute judgement about bytes rather than a ratio. It is the rare case on this site where a bare integer in a source file is the correct shape for the constant rather than a calibration that has aged.

What none of this measures #

Two things, both of which could reverse the conclusion for a given system.

Memory locality of the copy. A resize copies a contiguous block, which is the cheapest access pattern hardware offers and the one this site’s cache model charges least for. Counting copies as units of equal cost overstates the price of copying relative to almost any other operation. That biases the whole analysis towards larger factors than it should.

Whether the memory is ever touched. An allocation that is never written may cost nothing at all, because operating systems allocate address space lazily and commit pages on first touch. A doubling array’s 39% unused capacity may be 39% of address space and close to 0% of physical memory — which makes the waste column much less alarming than it looks, on a system with virtual memory and without an overcommit limit.

Both push in the same direction, towards doubling being a better default than the table suggests. Neither is measurable with an array simulator, and saying so is more useful than a number that pretends otherwise.