Geometric Growth, Copy Cost, and Peak Footprint

An append-only sequence cannot be stored in a fixed block, because its final size is unknown when it starts. The standard resolution is to over-allocate and grow by a constant factor. The choice of that factor is usually presented as a footnote about amortised O(1) appends, but it is a real engineering decision with at least four consequences: the total copying done over a build, the transient memory consumed at each growth, the fragmentation left behind, and the number of distinct regions the allocator must serve.

The amortised argument is correct and also dangerously incomplete. It bounds work per append in the limit of many appends; it says nothing about whether the pause at a particular append is acceptable, nothing about whether the peak memory during a growth can be afforded, and nothing about the allocator behaviour of repeatedly requesting a series of distinct large sizes.

The recurrence behind the factor

Let the growth factor be k > 1 and consider n appends. Capacity grows from 1 by repeated multiplication: 1, k, k², ... until it first exceeds n. The total number of element copies performed during all the growths is the sum of the capacities before each growth, which is dominated by the last term, roughly n / (k - 1).

Three values of k matter in practice. Doubling gives total copies of approximately n across the whole build, so each append costs about 1 extra element copy on average in addition to the store. A factor of 1.5 gives approximately 2n copies, so about 2 per append. Linear growth (k close to 1, as produced by adding a fixed increment) gives quadratic total copies, which is the failure mode that makes geometric growth necessary in the first place.

Doubling is not automatically the best choice. A smaller factor reduces the peak footprint, because the new buffer overlaps the old one by a larger fraction, and it wastes less space when the array stops growing in the middle of a capacity step. A larger factor reduces the number of growth events, which matters when each growth is expensive for reasons other than copying.

Some standard library implementations pick a factor near 1.5 precisely to balance waste against copy volume. The CPython list, for example, grows to approximately the current size multiplied by 1.125 plus a small constant, a much gentler factor that trades more copy volume for less slack; a Python list that grows to a million elements performs considerably more total copying than a vector that doubles, and also wastes far fewer elements at rest. Neither choice is wrong.

The transient copy and peak memory

The cost that geometric analysis omits is the peak. During a growth from capacity C to C*k, both buffers exist simultaneously, so instantaneous memory is C*(1+k) elements rather than C. With doubling that is 2C; with 1.5 it is 2.5C. The peak is reached at the largest growth step, and by then C can be nearly the final size.

This matters when the array itself dominates memory. A program holding a 4 GiB array that doubles to 8 GiB needs 12 GiB resident for the duration of the copy, even though its final footprint is 8 GiB. The copy also touches every element, so the fault cost of the new region plus the read of the old region together move more memory than any traversal of the array will.

The immediate consequence is that a memory limit must be sized for the peak, not the final size, and the peak depends on the growth factor. It also means a program that grows many large arrays concurrently experiences the sum of their peaks, which is why bulk-loading an array with a good capacity estimate is not merely a micro-optimisation: reserving the final capacity once removes every intermediate allocation, every copy, and every fault of the transient region.

realloc can mitigate the peak in one important case. If the region is at the end of the heap and the new size fits by extending the break, a conforming implementation may satisfy the request in place with no copying. That is a possibility, not a guarantee, and it depends on both the allocator state and the request size. Large requests that would use mmap cannot be extended in place at all; the allocator must map a new region and copy, because the mapping is not adjacent to the old one.

What the allocator sees

Each growth is a new request for a distinct size, and the freed old buffer goes back to the allocator as a large free block. A build that grows through capacities of 1 MiB, 2 MiB, 4 MiB, and 8 MiB asks the allocator for four distinct sizes and frees three. Because the freed blocks are large, glibc will typically have served the newest ones with mmap, which means each growth is not just a copy but a fresh mapping with its own first-touch faults, followed by munmap of the old region and the TLB shootdown that implies.

The reclaimed regions rarely satisfy the next request, because the next request is larger than any of them. The heap therefore accumulates large free regions that cannot be reused by this particular array, and the total committed memory of the process exceeds the sum of the live arrays by the size of that stranded residue. This is one of the ordinary sources of fragmentation, and it is worth distinguishing from leak-driven growth, as discussed in Fragmentation as a Latency Problem.

Long-running programs that repeatedly fill and clear the same vector behave differently. Once the capacity has stabilised at its high-water mark, the array stops growing and the sequence of distinct-size requests stops with it. Only the initial fill pays the growth cost; steady state uses the retained capacity. Retaining that capacity is therefore usually the right decision even when the array is momentarily small.

A sketch of the in-place possibility makes the allocator dependence concrete:

#include <stdlib.h>
#include <string.h>

/* Grow a buffer geometrically, preserving contents. realloc may extend in
 * place; when it cannot, it copies the old bytes into a new region. */
int push_int(int **buf, size_t *cap, size_t *len, int v)
{
    if (*len == *cap) {
        size_t newcap = *cap ? *cap * 2 : 8;
        int *p = realloc(*buf, newcap * sizeof *p);
        if (!p)
            return -1;
        *buf = p;
        *cap = newcap;          /* capacity is a hint to the allocator, not a promise */
    }
    (*buf)[(*len)++] = v;
    return 0;
}

The doubling here is a convention rather than a requirement, and the code’s behaviour under realloc is unspecified with respect to whether a copy occurs, which is why the cost cannot be predicted from the C source alone.

Shrinking and the high-water mark

Most container implementations keep the capacity after an element removal sequence empties the container, or shrink only when a size threshold is crossed. Shrinking on every removal would make the reverse pattern pathological: alternating push and pop at a capacity boundary would fault and copy on every operation. The standard solution is hysteresis, shrinking only when the size drops below a fraction of the capacity, so that a boundary-crossing workload does not thrash.

The cost of never shrinking is resident memory that the program no longer needs. For a process whose peak load is transient, that retained capacity shows up as steady-state RSS far above steady-state demand. The kernel will not reclaim it, because the pages are still mapped and anonymous, and the allocator will not return them, because they are a single live block. The only options are to shrink explicitly or to use an allocator interface that returns memory to the system.

Shrinking explicitly has a cost too, and it is the same as growth: a new region, a copy, and a free. Where the retained capacity is small relative to the process’s other memory, none of this matters. Where it is the majority of the footprint, it is the difference between a program that fits a memory budget and one that does not, and the fix is a capacity estimate from the input rather than a growth policy.

Choosing between growth and pre-sizing

The decision procedure is short. If the final size is known or bounded, reserve it once: this removes the copies, the transient peak, the sequence of distinct allocation requests, and the stranded free regions in one step. If it is not known, choose the factor against the memory budget: doubling when memory is plentiful and the array is a small part of the footprint, a gentler factor when the array is the footprint and the waste at rest matters.

Two numbers make the trade concrete for a given workload. The copy volume is approximately n / (k - 1) elements over the whole build, and the peak transient footprint is (1 + k) times the capacity at the largest growth. Both are computable from the final element count and the factor, before any code is written, and both are independent of how fast the machine is. The number that is not computable this way is the allocator response to a series of distinct large sizes, which depends on the allocator’s arena state and on whether those sizes crossed the mapping threshold described in The Cost Tiers of a Single Allocation Request.