Growth Policies in Dynamic Arrays and What the Allocator Does With Them

A growable array has one number that describes its state beyond the elements: capacity. The policy that decides when and by how much capacity increases determines the total copying work, the peak memory, and whether the allocator can satisfy the request without moving data at all. Implementations differ in the details, but the constraints that force the shape of the policy are the same everywhere.

The invariant that makes appends cheap

Write n for the element count and c for the capacity, with c ≥ n. The array is a single allocation of c elements plus a length field. Appending when n < c writes one element and increments n. Appending when n == c requires a new allocation of at least n + 1 elements, a copy of n elements, and a release of the old block.

If capacity grows by a constant k each time it is exhausted, a reallocation happens every k appends and copies the current length each time. Total copy work after N appends is about N²/(2k) element moves, quadratic. If capacity grows by a factor g > 1, the copy sizes form a geometric series and the total is bounded by N·g/(g−1). Doubling gives fewer than 2N moves; a factor of 1.5 gives fewer than 3N. The bound holds for any fixed g > 1, which is why the growth factor is a tuning parameter and not a correctness requirement.

The choice of g trades copy volume against slack. After a resize to capacity g·n, the fraction of the buffer that is unused immediately after the copy is (g−1)/g: one half at g = 2, one third at g = 1.5, one fifth at g = 1.25. That slack is not free in a program holding many arrays, but the copy volume grows as 1/(g−1), so shrinking g toward 1 makes the copying unbounded even though each individual resize still looks cheap.

Why the old block’s size matters to the allocator

realloc is specified to return a block of the requested size with the contents preserved up to the smaller of the old and new sizes, and to free the old block on success. The standard permits either outcome: the same address with an extended size, or a different address with the data copied. Which one happens depends on the allocator and on the size class of the request.

A typical allocator rounds requests up to a size class — a quantized set of sizes rather than a single power-of-two ladder. jemalloc’s documented classes for a 64-bit system with 4 KiB pages, for instance, step by 16 bytes up to 128, then by roughly 20 percent per step. Per the jemalloc manual page, realloc succeeds in place when the old and new sizes round up to the same class; otherwise it must copy. Whether a growth factor lands in the same class therefore depends on where in the ladder the sizes fall, not on a general rule about powers of two. Doubling a block that sits at the top of a class crosses into the next one; so does a factor of 1.5 applied to some sizes and not to others.

For large blocks, many allocators service requests with mmap on Unix-like systems, one mapping per allocation above a threshold. The threshold is not always a fixed number: glibc’s malloc starts at 128 KiB and then raises the effective threshold, up to a configured maximum, when a freed block that was itself mmapped is encountered, on the theory that such a block probably came from a large request. The kernel can extend a mapping in place if the virtual address range immediately following it is free; otherwise the mapping is moved. Page granularity matters here: the extension is rounded up to whole pages, so the usable capacity after an in-place extension may exceed the request.

/* Grow by 1.5x, but never below a floor and never past the size limit. */
static int reserve(vec *v, size_t need) {
    if (need <= v->cap) return 0;
    size_t cap = v->cap ? v->cap : 8;
    while (cap < need) {
        size_t next = cap + cap / 2;      /* 1.5x, integer arithmetic */
        if (next < cap) return -1;        /* wrapped: cannot grow */
        cap = next;
    }
    if (cap > SIZE_MAX / sizeof *v->data) return -1;
    void *p = realloc(v->data, cap * sizeof *v->data);
    if (!p) return -1;                    /* old block still valid */
    v->data = p;
    v->cap = cap;
    return 0;
}

Two properties of this loop are worth naming. The overflow check on next < cap catches the wrap that occurs when cap + cap/2 exceeds SIZE_MAX; without it the loop would terminate with a capacity smaller than need and the subsequent write would run past the block. And the SIZE_MAX / sizeof division checks the byte-count multiplication, which is the same overflow that calloc is specified to detect.

Copying cost is not the dominant cost at scale

The amortized argument counts element moves, which is the right model for small arrays. For an array of a few hundred megabytes, the copy is a memory-bandwidth event: the source must be read and the destination written, so the traffic is twice the block size, and the copy proceeds no faster than the memory path can supply and absorb bytes. A copy that fits a low cache level runs at cache speed; one that does not is limited by main memory, which is an order of magnitude slower and shared with every other core. During the copy the old and new blocks both exist, so peak resident memory is c + 2c = 3c elements for a doubling policy.

This is the case where incremental resizing earns its complexity: allocate the new block but move a fixed number of elements per subsequent append, keeping both blocks live and reading from the old one until it is drained. The append cost stays bounded instead of spiking, at the price of an extra branch and a stale block held for the duration of the migration.

A second-order effect is page faults. A freshly allocated large block is typically backed by untouched pages, and the first write to each page triggers a fault and a zeroing. That cost is proportional to the new capacity, not to the number of elements copied, so a policy that over-allocates generously pays it on the pages it never uses. Allocators that return memory already faulted in avoid part of this; those that hand out fresh anonymous mappings do not.

Shrinking is a separate decision

Growth policy is forced by the amortized argument; shrink policy is not, because nothing in the API requires capacity to track length downward. Removing an element can leave the buffer mostly empty indefinitely, which is the right behaviour for a stack that oscillates around a high-water mark and the wrong behaviour for a queue that drains once. The movement costs of removal itself are covered in Erasing From the Middle.

If shrinking is implemented, it must be hysteretic. Shrinking whenever n falls below c/2 makes a sequence of push/pop pairs across the boundary reallocate on every operation, converting an O(1) amortized cost into Θ(n) per pair. The standard fix is to shrink only when n < c/4 and then to c/2, which leaves a band of capacity between one quarter and one half in which neither growth nor shrink triggers. With that rule the potential argument still holds: each shrink is paid for by the removals that preceded it.

Deallocation has its own cost. Releasing a large block returns pages to the kernel, and a later growth must fault them back in. A program that alternates between filling and emptying a large array pays that fault cost repeatedly. Some allocators keep freed regions cached rather than returning them, which hides the cost at the price of resident memory that the process no longer logically owns.

What the interface promises

Language and library interfaces differ in how much of the policy they expose.

The C++ standard defines size(), capacity(), and reserve() on std::vector and requires that reserve(n) allocate capacity for at least n elements without changing the size, but it does not specify a growth factor. Implementations choose, and a program that depends on the exact capacity after a sequence of push_back calls is depending on the implementation. shrink_to_fit() is a non-binding request: an implementation may ignore it.

Go’s append returns a new slice header and leaves the growth policy to the runtime. Code that retains the result of append on a slice with spare capacity shares the backing array with the original, which is why appending to two slices derived from the same array can overwrite one through the other. The slice header is three words, and the aliasing follows from the pointer and capacity being copied by value.

Rust’s Vec exposes capacity(), reserve(), and shrink_to_fit() with similar guarantees: reserve may allocate more than requested, and shrink_to_fit shrinks toward the length but the allocator may leave the capacity somewhat larger. The borrow checker prevents the aliasing class of bug that Go’s slice headers permit, at the cost of making some in-place growth patterns require an explicit index-based loop.

In all three, the observable contract is the same: capacity is at least the length, growth is amortized constant, and no promise is made about the exact capacity or the timing of any individual reallocation. The engineering question is therefore never “what does the standard require” but “what does this implementation do, and does the program’s memory profile tolerate it”.

Failure modes

Allocation failure. realloc returning null leaves the original block valid, so the correct handling is to propagate the error without touching the pointer. Code that assigns the result directly to the array’s pointer loses the old block and leaks it.

Growth from zero. A policy that multiplies the current capacity fails when the capacity is zero, because every multiple of zero is zero. Every implementation special-cases the empty state with a non-zero initial capacity, commonly between 4 and 16 elements.

Copying non-trivially-movable types. A block copy is valid only for types that are trivially copyable; an array of objects with ownership must move each element, and the move constructor may throw. In C++ this is why std::vector growth requires the element type to be move-insertable and why a throwing move during reallocation leaves the container in a valid but unspecified state.

Aliasing across a resize. Any pointer or iterator into the buffer is invalidated by a reallocation. Retaining an index is safe; retaining an address is not. The distinction matters in code that caches a pointer to an element and later appends to the same array.

Overcommit. On a system that overcommits virtual memory, a successful allocation of a very large block does not guarantee that the pages can be backed. The failure appears at first write as a fault, which in most processes terminates it rather than returning an error to the caller.