Хранение массива в структуре данных: принципы и критерии выбора подхода в 2026

Хранение массива в структуре данных означает, что непрерывный блок элементов одного типа лежит внутри составного типа, а не в отдельно выделенной области, на которую структура ссылается указателем. Структура и её массив живут в одной области памяти, освобождаются одним вызовом free, а адрес i-го элемента считается арифметикой base + i * sizeof(T). Как только поле-массив заменяют указателем на внешний буфер, к каждому доступу добавляется разыменование, к числу аллокаций прибавляется вторая, а к рискам — проверка на NULL и потеря локальности кэша.

Выбор между непрерывным (contiguous) и связным (linked) хранением задаёт профиль обращений к памяти, и на современных CPU он часто весит больше асимптотики. Обход contiguous-массива из 1 млн int32 читает 4 МБ последовательно, аппаратный prefetcher тянет линии кэша заранее. Обход linked-списка из 1 млн узлов превращается в pointer chasing: почти каждый следующий узел лежит в новой странице. Разрыв между попаданием в кэш и обращением к DRAM измеряется порядками, и его оплачивает код, который гоняется по указателям.

Дальше разбираем три способа хранить массив внутри структуры, сравниваем их в таблице, показываем примеры на C11/C17, Go 1.22+ и Python 3.12+, даём команды замеров и переносим те же критерии на уровень дисковых массивов. В финале — чек-лист из 12 пунктов и шаблон обоснования решения для ревью.

Что значит хранить массив в структуре данных

Массив в структуре — это набор элементов одного типа, который начинается по фиксированному смещению внутри составного объекта. Компилятор знает смещение и размер на этапе сборки, поэтому обращение к element[i] превращается в одну инструкцию загрузки без дополнительного разыменования. Модель памяти и вычисление адреса по индексу подробно разобраны в материале про базовый адрес, выравнивание и статические массивы. В коде встречаются три варианта хранения, и путаница между ними даёт основную часть ошибок.

Массив как поле, указатель на массив и динамический массив

В Python массив внутри структуры почти всегда означает ссылку на объект list или array.array: сам экземпляр класса хранит указатель, а данные лежат в отдельном объекте. Копирование класса не копирует содержимое контейнера, а объём считается в два шага. Правила расчёта вместе с оверхедом заголовков и аллокатора разобраны в статье об измерении памяти под массивы.

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

Почему раскладка в памяти важнее синтаксиса

Точные значения задержек L1, L2, L3 и DRAM в тактах зависят от конкретной микроархитектуры и версии процессора, поэтому универсальных чисел для всех CPU приводить нельзя. Достоверно одно: разрыв между попаданием в кэш и обращением к DRAM измеряется порядками, и именно этот разрыв оплачивает код, который гоняется по указателям. Для конкретной платформы задержки стоит брать из официального optimization guide производителя или измерять самостоятельно.

Посчитаем на конкретных объёмах. Массив из 1 млн int32 занимает 4 МБ: миллион элементов по 4 байта. При последовательном обходе CPU подтягивает линии кэша по 64 байта, то есть 16 элементов за одно обращение, и предзагрузчик выбирает следующий блок заранее. Связный список из 1 млн узлов, где узел это int32 плюс 8-байтовый указатель, требует минимум 16 МБ под полезные данные и указатели, а с заголовками аллокатора и выравниванием узел часто занимает 24–32 байта вместо 12. Каждый переход по next — отдельное обращение к памяти, которое предзагрузчик предсказать не может.

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

Contiguous и linked: два подхода к хранению массива

Contiguous-хранение: элементы лежат в одном блоке, адрес i-го считается как base + i * sizeof(T). Доступ по индексу O(1), вставка и удаление в середине O(n), потому что хвост сдвигается на месте. Linked-хранение: каждый элемент это узел с данными и указателем на следующий, доступ по индексу O(n), вставка и удаление при известном узле O(1), память на элемент растёт на указатель и заголовок аллокатора. Оба подхода описывают одну задачу, но дают разный профиль обращений.

Таблица сложностей и реальные накладные расходы

Амортизированная вставка в конец динамического массива стоит O(1), но константа не нулевая: при удвоении ёмкости аллокатор выделяет новый буфер и копирует все элементы. В этот момент процесс держит примерно в полтора раза больше памяти, чем полезные данные. Для массива из 1 млн int32 копирование 4 МБ занимает доли миллисекунды на серверном CPU, однако в latency-sensitive сервисе такие пики видны в p99 и портят SLA.

Асимптотика без констант обманывает. O(1) по связному списку проигрывает O(n) по массиву, когда n небольшое и данные помещаются в кэш: сдвиг 64 байт внутри одной линии дешевле, чем переход по указателю в другую страницу.

Гибридные структуры: когда ни чистый массив, ни чистый список не подходят

Продакшен редко выбирает крайние варианты. Компромисс дают структуры, которые хранят элементы блоками:

• deque: массив блоков фиксированного размера плюс карта блоков. Даёт амортизированную вставку в оба конца и индексацию за O(1). Брать для очередей и стеков, где нужен доступ по позиции.
• unrolled linked list: в узле лежит несколько элементов, число переходов по указателям падает в 8–16 раз. Брать при частых вставках и необходимости обхода.
• B-tree и B+tree: широкие узлы по 8 КБ, как страницы PostgreSQL и большинства файловых систем. Дают локальность чтения и дешёвую вставку одновременно, поэтому лежат в основе индексов и key-value хранилищ.
• rope: дерево из фрагментов строки, применяют там, где нужны вставки в середину большого текста без копирования всего буфера.
• skip list: многоуровневый связный список с O(log n) на поиск, вставку и удаление и с простой конкурентной реализацией. Используется в in-memory хранилищах и LSM-движках.

Чистый linked-список остаётся уместен там, где важны порядок и дешёвое перемещение узлов между контейнерами, например во внутренних очередях планировщика. Для остальных задач в 2026 году чаще выигрывают гибриды.

Массив в структуре на C, Go и Python: примеры и подводные камни

Одна задача решается тремя рантаймами по-разному. В C раскладкой управляете вы, в Go часть решений принимают escape-анализ и сборщик мусора, в Python данные всегда лежат в отдельном объекте, а структура хранит ссылку. Примеры ниже рассчитаны на C11/C17, Go 1.22+ и Python 3.12+.

C: struct с массивом фиксированной длины

Канонический пример: struct Packet { uint8_t payload[1500]; size_t len; };. Поле payload лежит внутри структуры, отдельной аллокации нет. Размер структуры на 64-битной платформе около 1512 байт: 1500 байт полезных данных, 8 байт под len и 4 байта выравнивания, потому что size_t требует адреса, кратного 8. Перестановка полей местами размер не меняет, но порядок доступа к памяти стоит проверять замером.

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

Для переменной длины используют гибкий массив-член из C99: struct Buf { size_t len; uint8_t data[]; };. Память выделяют одним вызовом malloc(sizeof(struct Buf) + n), и data идёт вплотную к len. Приём лежит в основе сетевых буферов и структур ядра Linux, где нужен один непрерывный блок и одно освобождение.

Типичные ошибки: выход за границы поля-массива, отсутствие проверки len, переполнение при копировании через memcpy, неверный sizeof при работе с указателем вместо структуры. Сборку проверяйте набором флагов gcc -Wall -Wextra -fsanitize=address,undefined: AddressSanitizer ловит выход за границы массива внутри структуры, UBSan ловит арифметику по указателям и переполнения. Размещение данных на стеке и в куче, причины переполнения стека и работу аллокаторов разбираем в отдельном материале про критерии выбора между стеком и кучей.

Go: массивы, срезы и escape-анализ

В Go три сущности, которые легко перепутать. [N]T — массив фиксированной длины, значение копируется целиком и лежит внутри структуры. []T — срез, то есть дескриптор из указателя, длины и ёмкости, а данные лежат в отдельном буфере. Структура с полем [N]T остаётся непрерывной, пока не утекает в кучу.

Пример: type Header struct { Magic [4]byte; Version uint16; Payload [1024]byte }. Все поля идут одним блоком, обход Payload читается последовательно. Куда попадёт структура, решает escape-анализ: команда go build -gcflags='-m' печатает, какие переменные уезжают в кучу. Если функция возвращает указатель на структуру с большим массивом, аллокация идёт в heap, и дальше в дело вступает сборщик мусора.

Отдельная ловушка — копирование по значению. Массив [1<<20]byte в структуре, переданной по значению, означает копирование мегабайта при каждом вызове, и компилятор такие копии не убирает. Аллокации на операцию показывает go test -bench=. -benchmem. Общие буферы, алиасинг и время жизни данных разобраны в статье про срезы и представления массивов.

Python: list, array.array и numpy внутри класса

В CPython list — это массив указателей на объекты PyObject, а не непрерывный массив значений. Пустой список на 64-битной платформе имеет фиксированный оверхед 56 байт, а каждый элемент хранится как 8-байтовый указатель на объект в куче (EmiTechLogic, How Python Lists Really Work). То есть список из 1024 элементов занимает около 8 КБ только под указатели, а сами объекты int лежат отдельно. Мелкие целые от -5 до 256 интерпретатор кэширует, остальные создаёт заново.

array.array из стандартной библиотеки хранит сырые значения: array.array('i', [0]) * 1024 занимает примерно 4 КБ непрерывной памяти без объектов на каждый элемент. numpy.ndarray даёт непрерывный буфер с dtype и strides и выигрывает на числовых операциях. Полное сравнение по типам данных, байтам и скорости собрано в статье про list, array и NumPy.

Два подводных камня. Первый: numpy-массив внутри класса это ссылка на буфер, и копирование класса не копирует данные, для независимой копии нужен .copy(), а для чтения без копии подходит memoryview. Второй: sys.getsizeof показывает размер самого контейнера и не учитывает вложенные объекты, поэтому для реального объёма нужны замеры процесса, а не размер одного объекта.

Сводка по языкам: C даёт максимум контроля над раскладкой и нулевые накладные расходы на рантайм, Go даёт безопасность памяти и сборщик мусора ценой неопределённости места аллокации, Python даёт гибкость и платит за неё указателями и объектами.

Как структура влияет на скорость доступа, вставки и удаления

Практический ориентир выводится из трёх чисел: доля чтений, размер массива, место вставок. Вставка в начало contiguous-массива из 1 млн int32 сдвигает около 4 МБ. Точное время такого сдвига зависит от CPU, компилятора и реализации memmove, поэтому его нужно измерять на своём стенде, а не брать из общих цифр. Для связного списка вставка в начало стоит O(1), но обход тех же 1 млн узлов может идти в разы медленнее обхода массива. Решает замер на вашем стенде.

Профиль нагрузки: read/write ratio и паттерн доступа

Сначала формализуйте нагрузку. Достаточно пяти параметров:

1. Доля чтений и записей, например 99% чтений и 1% вставок.
2. Место вставок и удалений: начало, конец, середина, случайная позиция.
3. Средний и максимальный размер массива и частота его изменений.
4. Требования к задержке по p50 и p99, а не среднее значение.
5. Допустимый пик памяти, включая момент реаллокации.

Из этого набора выводятся решения. Read-heavy с доступом по ключу: contiguous-массив плюс хеш-индекс, вставки редкие. Write-heavy со вставками в середину: B-tree или связный список, потому что contiguous-массив копирует хвост на каждой вставке. Смешанная нагрузка с хвостовыми вставками: динамический массив с удвоением ёмкости, где вставка амортизированно O(1), а пик памяти в момент копирования составляет около 1.5x от полезного объёма.

Как измерить, а не угадать: команды и метрики

• C и C++: perf stat -e cache-misses,cache-references ./bench, плюс hyperfine для повторяемых прогонов.
• Go: go test -bench=. -benchmem -cpuprofile=cpu.out, затем go tool pprof cpu.out. Флаг -benchmem показывает аллокации на операцию и сразу выявляет лишние копии.
• Python: python -m timeit для микрозамеров, py-spy top для профиля работающего процесса, memory_profiler для роста памяти.

Смотреть стоит четыре метрики: время на операцию, аллокации на операцию, cache-misses и задержку p99. Типичные ошибки бенчмарков: отсутствие прогрева, удаление кода компилятором как мёртвого, влияние сборки мусора на коротких прогонах, слишком маленькая выборка. Расчётный объём памяти стоит сверить с фактическим, чтобы увидеть оверхед заголовков и аллокатора; методика сравнения описана в статье про профилирование памяти под массивы.

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

От памяти к диску: та же логика в дисковых массивах

RAID-уровни повторяют тот же выбор: непрерывность против распределения. RAID 0 разбивает данные на полосы и даёт пропускную способность без избыточности. RAID 1 хранит копию, как contiguous-массив с дублированием. RAID 5 и RAID 6 добавляют чётность и платят за неё на каждой записи. Решение определяется профилем ввода-вывода: последовательным или случайным.

RAID-уровни как выбор структуры хранения

RAID 5 на больших HDD в 2026 году остаётся рискованным. Неисправимые ошибки чтения (URE) возникают с частотой от 1 к 10^14 до 1 к 10^16 прочитанных бит, что соответствует примерно 12,5 ТБ, 125 ТБ и 1,25 ПБ данных (DiskInternals, RAID 5 rebuild failure probability). Чем больше ёмкость дисков, тем больше данных приходится читать при перестроении и тем выше шанс наткнуться на плохой сектор. Перестроение RAID 5 может занимать от нескольких часов до нескольких дней: для массивов 4–8 ТБ это обычно 8–24 часа, а на больших массивах 10+ ТБ rebuild может растянуться на несколько дней (iCare Recovery, RAID 5 recovery). Для продакшена чаще берут RAID 10 или RAID 6 с горячим резервом.

Порядок цифр для ориентира: HDD даёт около 100–200 МБ/с на последовательном чтении и 100–300 IOPS на случайных операциях 4 КБ; NVMe даёт 3000–7000 МБ/с последовательно и 50K–500K IOPS на случайных операциях в зависимости от накопителя (fio: Real Disk Benchmarking). Отсюда вывод: при случайной записи RAID не спасёт, помогут NVMe и правильная структура на стороне хранилища. При последовательной записи полосы RAID 0 или RAID 10 дают максимум пропускной способности.

LSM-деревья в RocksDB, Cassandra и похожих системах это осознанный компромисс: запись идёт последовательно в новые файлы, а фоновая компакция перекладывает данные. Случайная запись превращается в последовательную ценой дополнительного чтения и расхода на компакцию. B-tree в PostgreSQL и MySQL работает иначе: страницы по 8 КБ дают локальность чтения, а запись обновляет страницу на месте.

Чек-лист критериев выбора структуры для хранения массива

Список работает в любом языке. Пройдите по пунктам до того, как писать код.

1. Размер массива известен на этапе компиляции или меняется во время работы.
2. Профиль нагрузки: read-heavy, write-heavy, смешанный, с каким соотношением чтений и записей.
3. Место вставок и удалений: начало, конец, середина, случайная позиция.
4. Требования к задержке по p50 и p99, а не среднее значение.
5. Допустимый пик памяти, включая момент реаллокации и удвоения ёмкости.
6. Нужен ли доступ по индексу за O(1).
7. Нужен ли обход в порядке вставки или в отсортированном порядке.
8. Есть ли требования к локальности кэша и работает ли структура в горячем пути.
9. Какой рантайм и сборщик мусора, попадают ли большие массивы в паузы GC.
10. Как структура сериализуется и передаётся по сети, нужен ли непрерывный буфер.
11. Насколько просто объяснить структуру команде и покрыть её тестами.
12. Есть ли проверенная библиотека вместо самописного кода: deque, B-tree, skip list в стандартной библиотеке или зрелой зависимости.

Шаблон обоснования решения для команды

Пять строк в ADR или комментарии к коду снимают половину споров на ревью:

1. Контекст: сервис, объём данных, профиль нагрузки.
2. Рассмотренные варианты: contiguous, linked, гибрид.
3. Выбранный вариант и причина в одну фразу.
4. Метрики: бенчмарк, аллокации на операцию, cache-misses, p99.
5. Риски и условие пересмотра: при каком росте данных или смене профиля решение меняется.

Пример заполнения для сервиса с 10 млн записей и 99% чтений: выбран contiguous-массив плюс хеш-индекс, потому что доступ по ключу занимает O(1), а обход идёт последовательно; linked отклонён из-за промахов кэша на обходе; метрики — ноль аллокаций на чтение по benchmem и p99 в пределах 0.2 мс; решение пересматривается, если доля вставок вырастет выше 10%.

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