Tensions in Practice: Early space reservation in tension with a later copying spike¶
Contiguous array · four invented appends
An array receives A, B, C and D. Reserving four slots first leaves room for every append in this example. Starting with two slots uses less space initially, but appending C to a full array requires a larger allocation and copying A and B. Most appends still look cheap; the expensive event lands on one particular request.
Avoid resize work on the append path
Prepare enough capacity before the illustrated additions arrive.
Avoid reserving unused space too early
Let allocation grow with actual demand when the final length is uncertain.
Why these aims pull against each other
Growing on demand saves early reserved space by leaving some future operation responsible for allocation and copying. An average cost does not describe that operation’s burst of work.
Choose an arrangement to see what changes and what remains difficult.
Finite illustrative comparisons. Labels carry the meaning; color does not establish a preference or measured effect.
What this choice protects
What it costs
When it fits
Compare the arrangements
Reserve four first
Allocate four contiguous slots before A arrives, then append the four items without growing this array.
| Slots | Existing items copied | Unused slots | |
|---|---|---|---|
| Append A | 4 | 0 | 3 |
| Append B | 4 | 0 | 2 |
| Append C | 4 | 0 | 1 |
| Append D | 4 | 0 | 0 |
- What it protects
- No append in the declared sequence copies existing items for a resize.
- What it costs
- More slots are reserved early, and they remain unused if the sequence stops after A or B.
- When it fits
- Fits a credible four-item bound or an affordable capacity estimate when append-time copying is undesirable.
Illustration note: The table counts existing elements moved by resizing, not allocator time or all memory writes. Upfront allocation still costs work.
Grow on demand
Begin with two slots. When C arrives, allocate four, copy A and B, then append C; D fits without another growth.
| Slots | Existing items copied | Unused slots | |
|---|---|---|---|
| Append A | 2 | 0 | 1 |
| Append B | 2 | 0 | 0 |
| Append C | 4 | 2Copy A and B | 1 |
| Append D | 4 | 0 | 0 |
- What it protects
- The initial reservation is smaller if later items never arrive.
- What it costs
- C bears allocation and copying; old and new storage may overlap while the move completes.
- When it fits
- Fits uncertain growth and a workload that can tolerate the occasional resize event.
Illustration note: Doubling and the four-item sequence are explicit toy policies. No allocator, pointer-stability or amortized latency guarantee is implied.
What this illustration does—and does not—establish
Data Structure: Worst-Case versus Amortized Cost (measurement) supplies the mismatch between average cost and an individual growth event. The finite trace counts actual copied elements under a declared relocation policy.
- The fixed reservation does not cover a fifth item; exceeding the assumed bound needs another policy.
- An implementation that can extend storage in place may avoid some copies; this example assumes relocation is required.
- Moving references to externally held elements needs separate correctness treatment.
Source entries
Data Structure
Data Structure: Worst-Case versus Amortized Cost (measurement) supplies the conflict examined here.
Worst-Case versus Amortized Cost (measurement)
Some arrangements are cheap on average but occasionally catastrophic (a dynamic array's rare O(n) resize, a hash's rehash). The failure mode is choosing on average-case performance where a worst-case spike is intolerable — a real-time or adversarial setting where the occasional expensive operation arrives at exactly the wrong moment, or a triage system whose rare expensive path floods under a correlated surge.