Динамические массивы: рост, реаллокация и цена копирования

Динамический массив хранит элементы в одном непрерывном блоке памяти в куче и умеет увеличивать этот блок по мере добавления данных. Так работают std::vector в C++, ArrayList в Java, slice в Go. Когда свободные слоты заканчиваются, рантайм выделяет новый буфер большего размера, копирует туда все элементы и освобождает старый.

Основную цену создаёт именно копирование: одна вставка может стоить O(n) и вызвать всплеск потребления памяти, хотя в среднем по последовательности операций стоимость остаётся константной. Отсюда и разница между худшим случаем и амортизированной оценкой, которую вы видите в документации.

Дальше разберём, как разделены size и capacity, с каким коэффициентом растёт буфер, почему реаллокация инвалидирует указатели, когда reserve экономит время и в каких случаях удержанный буфер превращается в лишние гигабайты RSS.

Что такое динамический массив и зачем ему capacity

Внутри динамического массива лежат три поля: указатель на начало буфера, число реально хранящихся элементов (size) и число слотов, доступных без перевыделения (capacity). Размер самого дескриптора одинаков, хранит он 10 элементов или 10 миллионов.

Непрерывность буфера даёт доступ по индексу за O(1): адрес элемента вычисляется как начало плюс индекс, умноженный на размер одного элемента. Компилятор не обходит связанный список и не спускается по дереву, а сразу попадает в нужную ячейку.

Чем size отличается от capacity

size показывает, сколько элементов лежит в контейнере сейчас. capacity показывает, сколько поместится до следующего перевыделения. Первое число никогда не превышает второе.

Пример: вектор, в который добавили один элемент, обычно имеет size 1 и capacity 1 или 2 в зависимости от библиотеки. После 1000 вызовов push_back size равен 1000, а capacity может составлять 1024. Удалите 990 элементов, и size станет 10, тогда как capacity останется 1024: слоты никто не отдавал.

Обращаться к элементу с индексом от size до capacity нельзя. Память под ним физически выделена, но объект там не построен. Чтение или запись дадут неопределённое поведение, которое проявится позже и в другом месте программы.

Почему буфер должен быть непрерывным

Альтернатива непрерывному блоку - хранить элементы разрозненными кусками и связывать их ссылками. Тогда доступ по индексу перестал бы быть O(1): чтобы дойти до элемента с номером 500 000, пришлось бы пройти полмиллиона узлов.

Второй аргумент - кэш процессора. Данные читаются кэш-линиями по 64 байта на x86-64, и соседние элементы подтягиваются заранее. Обход непрерывного массива на миллион int32 укладывается примерно в 16 000 кэш-линий. Как выравнивание и padding меняют реальный размер одной структуры и сколько памяти это добавляет, разобрано в статье Выравнивание данных в памяти и padding в массивах: как раскладка структур влияет на память и скорость.

Плата за непрерывность - невозможность дорастить блок на месте: сразу за ним может лежать другая аллокация. Когда свободные слоты заканчиваются, приходится выделять новый участок и переносить туда данные.

Как происходит рост динамического массива и реаллокация

Триггер один: вставка при size == capacity. Последовательность шагов одинакова во всех динамических массивах.

Аллокатор получает запрос на новый блок большего размера.
Все элементы копируются или перемещаются из старого буфера в новый.
Старый буфер возвращается аллокатору.
Обновляются указатель и capacity, size увеличивается на единицу.

Стоимость третьего шага - O(n) по числу уже находящихся элементов. Для вектора на 10 млн int32 одна реаллокация означает перенос 40 МБ. Для 100 млн элементов - 400 МБ за один push_back.

Коэффициент роста: почему x2, а не +1

Если увеличивать ёмкость ровно на один элемент, каждый push_back в заполненный массив копирует всё содержимое. Суммарная работа для n вставок составит 1 + 2 + 3 + ... + n, то есть O(n²). Вставка 100 000 элементов превратилась бы в 5 миллиардов перемещений.

Геометрический рост меняет картину: буфер увеличивается в r раз, и копирования происходят всё реже. Любой множитель больше 1 (например, x1,5 или x2) даёт амортизированное O(1) на одну вставку. Для удвоения суммарные копирования при переездах на размерах 1, 2, 4, ... ограничены суммой порядка 2n, плюс n самих вставок — итого T(n) ≤ 3n. Амортизационный анализ как метод подсчёта времени для последовательности операций усредняет время по всем операциям и анализирует среднюю производительность в худшем случае; в методе усреднения амортизированная стоимость получается делением суммарной стоимости всех операций на их количество.

Конкретные коэффициенты роста и максимальный запас памяти зависят от реализации и версии стандартной библиотеки или рантайма. Ниже — ориентиры, которые стоит проверять на своей сборке.

Коэффициент роста	Копирований за n вставок	Максимальный запас памяти	Где встречается
x1,25	копирований больше, чем при x2	запас меньше, чем при x2	крупные слайсы Go
x1,5	промежуточный вариант	промежуточный вариант	ArrayList, отдельные реализации std::vector
x2	копирований меньше всего	запас до половины ёмкости	libstdc++, libc++, небольшие слайсы Go

Для массива на 1 млн элементов удвоение даёт меньше копирований, чем рост в 1,5 раза. У каждого варианта своя плата: удвоение копирует меньше, но в худший момент держит до половины ёмкости впустую (при size = n capacity доходит до 2n). Меньший коэффициент тратит меньше лишней памяти, зато реаллокации случаются чаще. Точные формулы зависят от версии компилятора или рантайма, поэтому проверяйте поведение на той сборке, которая стоит у вас в проде.

Что происходит со старыми указателями и итераторами

После реаллокации данные лежат по другому адресу. Все итераторы, указатели и ссылки на элементы, полученные до перевыделения, становятся недействительными. Сохранённый указатель на элемент может смотреть на уже освобождённую память, а чтение по нему вернёт мусор или уронит процесс.

Правило простое: не храните адреса элементов между вызовами, которые меняют размер, а именно между push_back, insert, erase, reserve и resize. Если нужно запомнить позицию, храните индекс.

Амортизированная сложность push: почему O(1) в среднем

В документации push_back и append помечены как O(1), хотя иногда такая операция копирует миллионы элементов. Противоречия нет: O(1) здесь означает амортизированную оценку для последовательности операций, а не гарантию на каждую отдельную вставку.

Худший случай против амортизированного

Отдельный push_back может стоить O(n). Гарантия появляется, когда суммарную работу делят на число операций: для n вставок общее время складывается из n добавлений и копирований при переездах, то есть O(n) на весь ряд. На одну вставку выходит константа.

Аналогия: ремонт дороги стоит дорого и случается редко. Считать среднюю стоимость поездки по сумме всех ремонтов за год корректно, но конкретная поездка в день ремонта займёт час вместо десяти минут.

Для сервисов с жёсткими требованиями к задержкам это имеет прямое значение. Реаллокация вектора на 100 млн элементов переносит сотни мегабайт и может дать паузу в десятки миллисекунд. В системе с бюджетом ответа 5 мс такой всплеск ломает SLA, хотя средняя задержка остаётся в норме. Резервирование ёмкости заранее убирает этот источник пауз.

Влияние коэффициента роста на число копирований

Чем меньше коэффициент, тем чаще реаллокации и тем выше суммарный объём копирования. Чем больше коэффициент, тем выше пиковое потребление памяти: при удвоении процесс в момент роста держит и старый, и новый буфер одновременно, то есть до 3n элементов по объёму на короткое время.

Практический вывод зависит от приоритета. Если узкое место - скорость обработки и памяти в запасе много, удвоение выгоднее. Если сервис живёт в контейнере с лимитом памяти и рискует попасть под OOM-killer, меньший коэффициент и своевременный reserve дают более предсказуемый профиль.

reserve и shrink_to_fit: как управлять ёмкостью вручную

reserve(n) просит выделить буфер минимум на n элементов. size при этом не меняется, растёт только capacity. Если capacity уже не меньше n, вызов ничего не делает и стоит доли микросекунды.

Когда reserve реально экономит время

Чтение файла на 1 млн строк в вектор без reserve даст примерно 20 реаллокаций: ёмкость пройдёт значения 1, 2, 4, ..., 1 048 576. С reserve на миллион реаллокаций не будет ни одной, вместе с ними исчезнут копирования и пиковые всплески памяти.

Особенно заметен выигрыш там, где размер известен из метаданных: count в ответе SQL-запроса, Content-Length в HTTP-ответе, размер файла, число строк в CSV. Если точного числа нет, берите оценку сверху: reserve на 100 000 при реальных 80 000 тратит небольшую долю памяти и всё равно убирает основную часть копирований.

В Java ту же роль играет ensureCapacity(minCapacity). В Go ёмкость задают через make с тремя аргументами: длина 0, ёмкость 100000.

Когда shrink_to_fit не помогает и даже вредит

shrink_to_fit() — необязывающий запрос на уменьшение capacity() до size(). Стандарт C++ прямо оговаривает, что запрос необязывающий, чтобы дать реализациям свободу для специфичных оптимизаций, поэтому выполнение зависит от реализации. Если при вызове происходит реаллокация, все итераторы (включая end()) и все ссылки на элементы инвалидируются; если реаллокации нет, итераторы и ссылки остаются действительными. То есть сам вызов способен вызвать реаллокацию и копирование: если ужать вектор с 10 млн элементов до 100, вы заплатите за перенос этих ста элементов в новый блок и за возврат старого.

Антипаттерн: вызывать shrink_to_fit после каждого erase в цикле. Каждый вызов добавляет реаллокацию, суммарное время растёт, а следующий push_back снова выделяет память. Ужимать есть смысл тогда, когда контейнер останется маленьким надолго, например после обработки ночного батча.

В Java аналогичную задачу решает trimToSize(). В Go прямого аналога нет: чтобы отдать лишнюю память, создают новый слайс и копируют в него нужные элементы.

Типичные ошибки: лишние копии, фрагментация и удержание буферов

clear() не освобождает память

После clear() все элементы разрушены, size равен 0, capacity остаётся прежней. Вектор, обработавший 1 ГБ данных, продолжает держать буфер на 1 ГБ, и RSS процесса не падает. В долгоживущем сервисе, где пики приходят регулярно, это выглядит как ступенчатый рост потребления.

Вернуть память можно двумя способами: вызвать shrink_to_fit() без гарантии результата или обменять контейнер с пустым через swap, что освобождает старый буфер сразу. Проверяйте это на своей версии стандартной библиотеки: у части версий память уходит не в ОС, а в пул аллокатора.

Фрагментация кучи при частых реаллокациях

Освобождённый буфер возвращается аллокатору, но не обязательно операционной системе. Аллокатор держит его в пуле, чтобы отдать следующему запросу. Если запросы приходят разного размера, пул распадается на блоки, которые не подходят под новые запросы, и память остаётся занятой при видимом отсутствии нагрузки.

Пример: сервис в цикле создаёт и уничтожает векторы на 3, 5, 7 и 11 МБ. Аллокатор накапливает сотни мегабайт фрагментов, и RSS не снижается, хотя объём живых данных небольшой. Переиспользование одного буфера с reserve убирает и фрагментацию, и часть работы аллокатора. Как отличить фрагментацию от влияния page cache и почему рост RSS не всегда означает утечку, разобрано в статье Память и производительность ОС: как работают кэш, swap и OOM в Linux.

Лишние копии

Передача вектора по значению вместо ссылки копирует весь буфер и все элементы. Возврат большого вектора из функции без перемещения добавляет ещё одно копирование. Вставка в начало вместо конца сдвигает все элементы на каждой операции: для n вставок это снова O(n²).

Отдельный случай - контейнеры внутри контейнеров: вектор из векторов при росте внешнего массива копирует или перемещает внутренние буферы. Перемещение здесь дешевле, поэтому тип элементов должен поддерживать перемещение без исключений: тогда реаллокация внешнего вектора обойдётся переносом указателей, а не копированием данных.

Практические примеры: C++, Java, Go

Язык	Тип	Текущая ёмкость	Заранее выделить	Ужать	Рост
C++	std::vector	capacity()	reserve(n)	shrink_to_fit()	зависит от реализации STL
Java	ArrayList	публичного метода нет	ensureCapacity(n)	trimToSize()	политика роста не специфицирована, кроме амортизированного O(1)
Go	slice	cap(s)	make с ёмкостью n	прямого метода нет	около x2 на малых объёмах, медленнее на больших

C++: vector и его capacity

capacity() возвращает текущую ёмкость, reserve(n) поднимает её минимум до n, shrink_to_fit() просит уменьшить. После reserve и после push_back, вызвавшего реаллокацию, все итераторы и указатели на элементы недействительны, включая end().

Рабочий шаблон для чтения заранее известного числа строк: reserve(rows) до цикла, затем push_back на каждой строке. Если строки приходят потоком и число неизвестно, оцените верхнюю границу по размеру источника.

Java: ArrayList и ensureCapacity

ArrayList хранит элементы в Object[]. Пустой список, созданный конструктором по умолчанию, при добавлении первого элемента расширяется до ёмкости по умолчанию. ensureCapacity(minCapacity) заранее поднимает ёмкость, trimToSize() ужимает её до текущего размера. Детали политики роста в спецификации не зафиксированы сверх того, что добавление элемента имеет константную амортизированную стоимость; в исходном коде JDK видны отдельные константы для минимального и предпочтительного прироста.

Список на 1 млн элементов, заполняемый без ensureCapacity, проходит много шагов роста, каждый с копированием массива. Сборщик мусора освобождает объекты, но удержание большого массива после clear() увеличивает давление на GC и частоту пауз, потому что старый массив остаётся живым, пока на него есть ссылка.

Go: slice, append и cap

slice - это дескриптор из указателя на массив, длины len и ёмкости cap. append при нехватке места выделяет новый массив, копирует данные и возвращает новый дескриптор. В Go 1.18 встроенная функция append стала использовать немного другую формулу для решения, насколько увеличить слайс при необходимости выделить новый базовый массив; новая формула менее подвержена внезапным изменениям в поведении распределения. В исходном коде runtime функция growslice вычисляет следующую подходящую длину слайса (nextslicecap), и комментарий описывает переход от роста 2x для малых слайсов к росту 1.25x для крупных с плавным переходом между ними. Порог и формула менялись между версиями Go, поэтому сверяйтесь с документацией и исходным кодом своей версии.

make с тремя аргументами задаёт ёмкость заранее: длина 0, ёмкость 100000. Это убирает промежуточные копирования так же, как reserve в C++.

Отдельная ловушка: слайс, полученный как срез большого массива, продолжает ссылаться на весь исходный массив. Даже если вы держите 10 элементов, сборщик мусора не освободит массив на миллион элементов, пока жив этот слайс. Копирование нужного фрагмента в новый слайс освобождает память.

Как писать код с предсказуемым расходом памяти

Чек-лист: когда резервировать и когда освобождать

Резервируйте, когда размер известен или оценён сверху: чтение файла, ответ API, батч из очереди.
Резервируйте при массовой вставке в цикле, если контейнер живёт дольше одной итерации.
Освобождайте буфер после пиковой нагрузки, если дальше контейнер остаётся маленьким или пустым.
Не освобождайте, если контейнер скоро снова вырастет: повторные реаллокации дороже сэкономленной памяти.
Ограничивайте cap слайса в Go и размер удерживаемого массива в Java, если из большого буфера нужен небольшой фрагмент.
Не храните указатели и итераторы на элементы между операциями, меняющими размер.

Как измерять фактический расход памяти

Логируйте size и capacity ключевых контейнеров, а не только объём входных данных. Разница в разы между этими числами после обработки батча прямо указывает на удержание буфера.

Для RSS смотрите /proc/<pid>/status или метрики контейнера. Для профиля аллокаций: valgrind massif и heaptrack в C++, Java Flight Recorder и async-profiler в JVM, pprof в Go. Снимайте замеры до и после reserve: на файлах в сотни мегабайт разница в RSS достигает сотен мегабайт, и без замеров её легко приписать чему угодно.

Учитывайте, что снижение RSS после освобождения буфера может быть отложенным: аллокатор возвращает память в свой пул, а ОС получает её позже. Отсутствие быстрого падения RSS не означает, что shrink или swap не сработали.

Итог: что важно помнить о динамических массивах

size и capacity - разные величины: реальные элементы против доступных слотов.
Реаллокация случается при size == capacity и стоит O(n) из-за копирования.
Геометрический рост превращает n вставок в O(n) суммарной работы, то есть O(1) амортизированно на одну вставку.
Больший коэффициент роста копирует меньше, но держит больше памяти впустую; меньший экономичнее по памяти, но копирует чаще.
reserve и ensureCapacity убирают промежуточные реаллокации, когда размер известен заранее.
shrink_to_fit — необязывающий запрос: он возвращает память не всегда и сам может вызвать реаллокацию.
clear() не освобождает буфер: capacity сохраняется, RSS не падает.
Большие удержанные буферы в долгоживущем сервисе дают ступенчатый рост RSS и паузы на реаллокацию в момент пика.

Начните с одного действия: найдите в своём коде цикл, который наполняет контейнер без reserve, добавьте оценку размера и снимите RSS до и после. Разница покажет, сколько памяти и копирований вы вернули без изменения логики.