Before a bulk load, what does pre-allocating a growable array's capacity actually buy you?
answer
- the total work does not change
- count the allocations, not the elements
- how many times is the data copied?
- two blocks are live during a copy
- over-shooting is not given back
basics
~20 sPre-allocating removes the repeated allocate-copy-release cycles during the load: fewer allocator round-trips, no moment holding two blocks at once, no growth-driven invalidation, and a flatter latency profile. It does not change the asymptotic cost of appending n elements.
solid answer
~50 sIt buys constant factors and predictability, not a better complexity class — appending n elements is linear either way. Concretely: one allocation instead of a logarithmic number of them; the incoming data copied once instead of the already-placed elements being recopied on every growth step; no window where the old and new blocks are both live, which is what drives the transient peak in memory; a flat latency profile instead of periodic spikes when a large copy lands mid-request; and stable element positions for the whole load, so anything holding a position stays valid. What it costs: capacity is not returned automatically, so an over-generous estimate is memory you keep for the life of the structure, and sizing from a length field in untrusted input turns a bad number into a giant allocation. Under-estimating is graceful — you simply fall back to normal growth.
go deeper
Know that a growable array can be told its expected size in advance, and that this avoids repeatedly allocating and copying while the data is loaded. You are not expected to quantify the win.
Explain what changes and what does not: allocation count and bytes copied go down, the asymptotic O(n) total for the load does not. Mention that both blocks are live during a growth copy, which is why the peak footprint exceeds the final one.
Argue it as a latency and memory decision with evidence — allocation counts, copy volume, high-water mark — and name the failure mode of over-reserving, since capacity is not returned. Flag pre-sizing from untrusted counts as an availability risk.
Decide when this is worth codifying at all. A codebase-wide habit of pre-sizing to worst-case batches is a fleet memory regression; a rule that says 'pre-size only when the exact count is known and bounded' is cheap to review and hard to get wrong.
## What pre-allocation is Pre-allocating (pre-sizing) means asking the growable array for a capacity up front, before you start appending, so the block is big enough for the whole load from the start. The size stays zero; only the capacity moves. It is a hint about the future, and getting it wrong is never a correctness problem — it is purely a performance and memory decision. ## What it does not change Start here, because this is where candidates overclaim. Appending n elements into a growable array with geometric growth is O(n) total work whether or not you pre-size. Pre-allocation does not make an individual append cheaper in any interesting sense, does not change lookup or erase costs, and does not turn a linear load into a constant-time one. Anyone who says "pre-allocating makes appends O(1)" has confused the constant factor with the complexity class. ## What it genuinely changes Four things, all of which matter in production and none of which show up in a complexity table: **1. Allocator round-trips.** Growing from empty to n elements takes on the order of log n allocations. Each one is a trip through the allocator, which under contention or fragmentation is far from free, and each new block is cold — the copy touches pages that were never in cache. **2. Bytes copied.** Every growth step copies the elements already placed. Summed over the whole load that is on the order of n extra element copies beyond the n copies needed to place the data itself, plus the corresponding writes. Pre-sizing removes that entire second stream of work. **3. Peak memory during the copy.** This is the one people forget. During a growth step the old block and the new block are *both* live — you cannot release the source until the copy finishes. So the transient footprint at the last growth step exceeds the final footprint. If you are near a memory ceiling, the load can fail at a moment when the final structure would have fit comfortably. Pre-sizing means the block is allocated once, at its final size, with no overlap. **4. Stability.** No reallocation inside the load window means no element is relocated, so positions and handles captured during the load stay valid. This is a legitimate use of pre-sizing, but it is a *fragile* guarantee: it holds only while the estimate is a genuine upper bound, and one future edit that appends an extra element reintroduces the hazard silently. Prefer it as an optimisation, not as the safety mechanism something else depends on. ## The latency argument For a service, the interesting number is not total time but the shape of the distribution. Unsized growth concentrates its work into rare, large copies: most appends are trivial and a handful copy the entire structure. If those land inside a request, they appear as periodic tail-latency spikes that correlate with input size and are hard to attribute — the slow request is the one unlucky enough to trigger the copy, not the one doing the most work. Pre-sizing moves that cost to a single, predictable, up-front allocation. Trading the same total work for a better distribution is usually the actual reason to do this. ## What it costs **Over-estimating is permanent.** Capacity is a high-water mark under the common never-shrink policy, so a block sized for the worst-case batch stays that large for the life of the structure. Pre-sizing thousands of short-lived structures to a p99 batch size, across a fleet, is a memory regression dressed as an optimisation. The rule of thumb: pre-size when you know the count (a row count, a content-length, a fixed fan-out), estimate conservatively when you do not, and never pre-size to the worst case "just in case". **Untrusted counts are an availability risk.** Sizing a buffer from a length field supplied by a caller means a hostile or corrupt count becomes an immediate huge allocation, before a single element has arrived to validate it against. Either bound the pre-size to a sane ceiling, or let normal growth do the work — growth is self-limiting because you can only grow as fast as real data actually arrives. **Under-estimating is fine.** You get the normal growth path for the remainder. This asymmetry — cheap to under-shoot, expensive to over-shoot — should shape every estimate you pick. ## How to argue it with evidence Do not benchmark wall-clock alone; the win is structural. Count allocations and bytes copied during the load, and look at the memory high-water mark rather than the steady state. If the load is 200 elements, none of this matters and pre-sizing is noise you added to the code. If it is millions of rows on a request path with a memory ceiling, the allocation count and the transient peak are the numbers that decide it.
- If the asymptotics are unchanged, why do people still measure a large speedup?Because the constants are large. Unsized growth performs on the order of log n allocator round-trips and recopies the already-placed elements at every step, roughly doubling the total copy volume, all into cold memory. Pre-sizing removes that second stream of work entirely. Same complexity class, materially less machine work — and a much flatter latency distribution.
- What is the risk of pre-sizing from a length field in an incoming payload?A corrupt or hostile count becomes an immediate enormous allocation before any data has arrived to contradict it — a cheap request that costs you a lot of memory. Either clamp the pre-size to a defensible ceiling, or skip it and let ordinary growth pace the allocation against the data that actually shows up.
- You pre-sized for the largest batch you have ever seen, but most batches are tiny. What does that cost?Under a never-shrink policy the capacity is a high-water mark, so every structure that pre-sizes pays the worst case for its whole lifetime. Across many structures and many instances that is steady-state memory bought for a rare event. Size to the typical case and let growth handle the outliers — under-shooting is cheap.
saying these in an interview costs you the question
- Pre-allocating turns appending n elements from O(n) into O(1)
- Reserve as much as possible, spare capacity is free
- Reallocation costs time but never extra peak memory
- Pre-sizing is a reliable guarantee that nothing will be relocated
- Sizing a buffer from a caller-supplied count is harmless