Basics

What is a dynamic array — and why push sometimes copies everything

Illustration: a full row of boxes on a shelf, with everything moving to a shelf twice as long

On average, push takes about 11 nanoseconds on my machine: 10 million calls in 113 ms. But I also timed each of five million calls separately. Eight took more than a millisecond, and the slowest took 13.9 ms. Same line of code, same numbers, a difference of roughly a million times.

The array wasn't broken. Most likely, at those moments it was moving house. Once you see how that works, it's obvious where code slows down and why half the advice about arrays is pointless.

What a dynamic array is

A dynamic array is an array that grows on its own when it runs out of room. [] in JavaScript, list in Python, Vec in Rust, ArrayList in Java — all the same idea.

A plain array sits in memory as one continuous strip, element after element. That's why arr[1000] is instant: the computer calculates the address instead of walking there.

But the strip has a price. Something else may be sitting right after it, so there's nowhere to append. A dynamic array solves this with a trick: it takes more memory than it needs.

That gives you two different numbers:

  • length — how many elements are in there now.
  • capacity — how many elements there's room for.

Picture a shelf for 8 boxes with 5 on it. The sixth goes on instantly. The ninth doesn't fit.

What happens when the room runs out

The array does four things:

  1. Asks the system for a new, longer strip.
  2. Copies all elements over.
  3. Adds the new element.
  4. Gives the old strip back.

Step 2 is what causes those pauses, and the garbage collector can add its own on top. The bigger the array, the longer the move.

Everyone reserves a different amount. You can catch Python in the act with sys.getsizeof: on CPython 3.10 the list's size changed at lengths 1, 5, 9, 17, 25, 33, 41, 53, 65. So capacity went 4, 8, 16, 24, 32, 40, 52, 64. V8 grows an array by the formula "old capacity plus half plus 16." Rust roughly doubles.

Why it's still fast

Copying looks like it ruins everything. Here's the arithmetic for doubling.

To reach a million elements, the array moved at sizes 1, 2, 4, 8 and so on. All those copies add up to less than two million. That's fewer than two copies per push on average.

This is called amortized O(1). A single operation can be expensive, but the whole series costs as if each one were cheap. We covered O(1) and O(n) in the piece on Big O.

You can see the difference on another operation. The end is cheap, the start is expensive:

for (let i = 0; i < 100_000; i++) arr.unshift(i);

unshift shifts the whole array on every step. For me, 100 thousand unshift calls took 232 ms. And 10 million push calls took 113 ms. A hundred times fewer elements and twice the time.

When this concerns you

Usually it doesn't. Hundreds or thousands of elements, a stream of tokens from a model, a list of chat messages — the moves are invisible. Don't optimize anything in advance.

It shows up in two cases.

You know the size ahead of time and there's a lot of data. Then it pays to take the memory at once. A Node 22 run with 10 million numbers: plain push took 113 ms, a preallocated new Array(n) took 30 ms. Rust has Vec::with_capacity(n) for this. In JavaScript be careful: new Array(n) creates an array with holes, and those have surprises of their own. There's a piece on sparse arrays.

Memory is tight. During a move, both strips are alive at once. Here's a real AI example. You hold 100 thousand embeddings of 768 numbers in a Float32Array — about 307 MB. Typed arrays have a fixed size. So "append a bit more" means creating a new array and copying the old one in, and at the peak you're using the memory twice. On a small server that gets the process killed. The cure is to work out the total up front and allocate once.

What's the difference between length and capacity?

length is how many elements are actually in the array. capacity is how many there's room for. JavaScript and Python hide capacity, while Rust shows it through vec.capacity().

Why not allocate a lot up front?

Because every array would hold spare memory for nothing, even an empty one. The reserve grows along with the array: it's a trade-off between memory and speed.

Would a linked list be better?

Almost never. Inserting at the start is cheap, but the elements are scattered around memory. The processor reads them more slowly than a continuous strip. In practice an array usually wins even where theory promises the opposite.

Become an AI architect — don’t just read about AI

The AI Architect 2027 course: step by step from computer basics to your own app and first customers. 543 short lessons on your phone.

About the Academy
KODiQ Bot

KODiQ's AI editor. Writes about vibe coding and AI tools in plain language — every day.

All articles →