Что такое динамический массив — и почему push иногда копирует всё

В среднем push занимает у меня около 11 наносекунд: 10 миллионов вызовов за 113 мс. Но я засёк отдельно каждый из пяти миллионов вызовов. Восемь заняли больше миллисекунды, а самый долгий — 13,9 мс. Та же строчка кода, те же числа, и разница примерно в миллион раз.
Массив не сломался. Чаще всего в такие моменты он переезжал. И когда понимаешь, как это устроено, сразу видно, где код тормозит и почему половина советов про массивы бессмысленна.
Что такое динамический массив
Динамический массив — это массив, который сам растёт, когда в нём кончается место. [] в JavaScript, list в Python, Vec в Rust, ArrayList в Java — всё это он.
Обычный массив лежит в памяти сплошной лентой, элемент за элементом. Поэтому arr[1000] работает мгновенно: компьютер считает адрес, а не идёт по порядку.
Но у ленты есть цена. Рядом с ней может лежать что-то чужое, и дописать в конец некуда. Динамический массив решает это хитро: он берёт память с запасом.
Отсюда два разных числа:
- length — сколько элементов лежит сейчас.
- capacity — на сколько элементов занято место.
Представь полку на 8 коробок, из них заняты 5. Шестая встаёт мгновенно. А вот девятая уже не влезает.
Что происходит, когда место кончилось
Массив делает четыре вещи:
- Просит у системы новую ленту, побольше.
- Копирует туда все элементы.
- Кладёт новый элемент.
- Отдаёт старую ленту.
Шаг 2 и даёт такие паузы, а сборщик мусора может добавить к ним своё. Чем больше массив, тем дольше переезд.
Запас у всех разный. Python можно поймать за руку через sys.getsizeof: на CPython 3.10 размер списка менялся при длине 1, 5, 9, 17, 25, 33, 41, 53, 65. То есть ёмкость шла 4, 8, 16, 24, 32, 40, 52, 64. V8 растит массив по формуле «старая ёмкость плюс половина плюс 16». Rust примерно удваивает.
Почему это всё равно быстро
Кажется, что копирование всё портит. Смотри арифметику для удвоения.
Чтобы дойти до миллиона элементов, массив переезжал на размерах 1, 2, 4, 8 и так далее. Сумма всех копирований — меньше двух миллионов. На один push приходится меньше двух копий в среднем.
Это называется амортизированное O(1). Отдельная операция может быть дорогой. Но вся серия стоит столько, будто каждая дешёвая. Что такое O(1) и O(n), мы разбирали в статье про Big O.
Разница видна на другой операции. В конец дёшево, а в начало дорого:
for (let i = 0; i < 100_000; i++) arr.unshift(i);
unshift двигает весь массив на каждом шаге. У меня 100 тысяч unshift заняли 232 мс. А 10 миллионов push — 113 мс. В сто раз меньше элементов, а времени вдвое больше.
Когда это касается тебя
Обычно никак. Сотни и тысячи элементов, поток токенов от модели, список сообщений в чате — переезды там незаметны. Не надо ничего оптимизировать заранее.
Заметно становится в двух случаях.
Ты знаешь размер заранее и данных очень много. Тогда память выгодно занять сразу. Прогон на Node 22 с 10 миллионами чисел: обычный push — 113 мс, заранее созданный new Array(n) — 30 мс. В Rust для этого есть Vec::with_capacity(n). В JavaScript будь осторожнее: new Array(n) создаёт массив с дырами, а у них свои сюрпризы. Об этом есть статья про разреженные массивы.
Память впритык. В момент переезда живут обе ленты сразу. Вот реальный пример с ИИ. Ты держишь 100 тысяч эмбеддингов по 768 чисел в Float32Array — это примерно 307 МБ. У типизированных массивов размер фиксирован. Поэтому «дописать ещё немного» означает создать новый массив и скопировать туда старый, а в пике память занята дважды. На маленьком сервере процесс из-за этого убивают. Лекарство — посчитать итог заранее и выделить один раз.
Чем length отличается от capacity?
length — сколько элементов реально лежит в массиве. capacity — на сколько есть место. В JavaScript и Python ёмкость скрыта, а в Rust её можно посмотреть через vec.capacity().
Почему не выделить сразу побольше?
Потому что каждый массив держал бы лишнюю память впустую, даже пустой. Запас растёт вместе с массивом — это компромисс между памятью и скоростью.
Связный список был бы лучше?
Почти никогда. Вставка в начало у него дешёвая, но элементы разбросаны по памяти. Процессор читает их медленнее, чем сплошную ленту. На практике массив обычно выигрывает даже там, где теория обещает обратное.
Курс «Профессия 2027: ИИ-архитектор»: шаг за шагом от основ компьютера до своего приложения и первых клиентов. 543 коротких урока на телефоне.





