Хранение элементов в массиве: модели памяти и вычисление адреса по индексу

Массив хранит элементы одного типа в непрерывной области памяти. Адрес первого элемента называют базовым, а позицию любого другого вычисляют по формуле base + i * size, где i - индекс, size - размер одного элемента в байтах. Отсюда доступ по индексу за O(1): процессор умножает индекс на размер элемента и прибавляет базовый адрес, не перебирая предыдущие ячейки.

Эта модель объясняет несколько рабочих ситуаций: почему обход двумерного массива по строкам идёт быстрее обхода по столбцам, почему список Python из миллиона чисел занимает больше памяти, чем array.array, и откуда берётся segmentation fault при выходе за границы. Дальше разберём непрерывную раскладку, адресную формулу, различия статических и динамических массивов, выравнивание и примеры на C и Python.

Что такое массив и как он хранится в памяти

Массив - структура данных, где все элементы одного типа лежат подряд в одном блоке. Тип задаёт размер элемента: char занимает 1 байт, int в большинстве 64-битных сборок 4 байта, double 8 байт, указатель 8 байт. Зная размер элемента и адрес первого, можно посчитать адрес любого другого, не читая предыдущие.

Непрерывная область памяти: что это значит на практике

Непрерывность означает отсутствие посторонних данных и пропусков между соседними элементами. Первый элемент int-массива лежит, например, по адресу 0x1000. Тогда второй окажется по 0x1004, третий по 0x1008, четвёртый по 0x100C. Шаг между соседними адресами одинаков и равен размеру элемента.

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

Логический индекс и физическое смещение - разные величины. Индекс i отсчитывают от нуля, смещение в байтах равно i * size. Адресную арифметику, разницу между индексом и смещением, влияние кэш-линий и раскладку многомерных массивов разбирает статья Массив в оперативной памяти: непрерывный блок.

Базовый адрес и индекс: как связаны

Базовый адрес (base address) - адрес первого элемента, arr[0]. В C имя массива в выражениях приводится к указателю на первый элемент, поэтому arr и &arr[0] дают одинаковое значение. Индексация с нуля выбрана именно из-за адресной арифметики: смещение первого элемента равно нулю, и формула обходится без поправки.

Общий вид формулы: address(arr[i]) = base + i * sizeof(element). Здесь i - смещение в элементах, sizeof(element) - размер одного элемента в байтах. Компилятор подставляет это выражение в машинный код; для статического массива с константным индексом адрес может быть вычислен ещё на этапе компиляции.

Вычисление адреса элемента по индексу

Одна формула покрывает массивы любого типа: меняется только множитель. Именно поэтому индекс в C и Python выглядит как число, а превращается в адрес без обхода соседних элементов.

Формула адреса: base + i * size

Для char размер элемента 1 байт, поэтому адрес arr[i] равен base + i: смещение в байтах совпадает с индексом. Для double размер 8 байт: при base = 0x1000 элемент d[2] лежит по 0x1000 + 2 * 8 = 0x1010. Для указателя на 64-битной системе base + i * 8. В C запись arr[i] эквивалентна *(arr + i), и это не синтаксический сахар ради краткости, а прямое отражение адресной арифметики.

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

Пример на C: статический массив int

#include "stdio.h"

int main(void) {
    int arr[5] = {10, 20, 30, 40, 50};
    for (int i = 0; i != 5; i++) {
        printf("arr[%d]: value=%d address=%p\n", i, arr[i], (void *)&arr[i]);
    }
    return 0;
}

Вывод показывает, что адреса отличаются ровно на 4 байта, то есть на sizeof(int). Первый адрес и есть базовый, дальше шаг постоянный. Выход за пределы массива (arr[5] при длине 5) компилятор не поймает: поведение не определено, программа может вернуть мусор или упасть.

Пример на Python: список как динамический массив

lst = [10, 20, 30]
print(lst[0], lst[1], lst[2])
print(id(lst[0]), id(lst[1]), id(lst[2]))

В CPython список устроен как динамический массив указателей на объекты PyObject: в структуре списка поле ob_item объявлено как массив указателей PyObject *ob_item[], где ob_item содержит место для allocated элементов, а число используемых в данный момент - ob_size. Слот с индексом i лежит по адресу base + i * 8 на 64-битной системе, а значение получается разыменованием указателя из этого слота. Поэтому доступ lst[1] включает два шага: вычисление адреса слота и чтение объекта по ссылке. Устройство структуры списка и перевыделение памяти при заполнении описаны в исходном коде CPython (cpython/Objects/listobject.c) и в обсуждении реализации списка (How is Python's List Implemented?).

Функция id() возвращает адрес самого объекта, а не ячейки списка. Для небольших целых чисел CPython может переиспользовать одни и те же объекты, поэтому одинаковые значения иногда дают одинаковый id(). Это отличие от массива C, где элементы лежат в блоке непосредственно и адрес элемента однозначно задаёт данные.

Статические и динамические массивы: модели памяти

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

Статические массивы: фиксированная длина и стек

Локальный массив объявленной длины компилятор размещает в стеке кадра функции. Размер известен на этапе компиляции и не меняется. Память выделяется при входе в блок и освобождается автоматически при выходе. Глобальный или static-массив размещается в статической области (сегмент данных или BSS) и живёт всё время работы программы.

void func(void) {
    int arr[10];   /* 40 байт в стеке */
    /* ... */
}

Стек под процесс ограничен, и его размер в Linux задаётся в окружении ОС, а не в исполняемом файле: текущее значение можно проверить командой ulimit -s и изменить, например, командой ulimit -s 16384 (C/C++ maximum stack size of program). В примере на 64-битной Ubuntu ulimit -s выводит 8192, то есть 8192 КБ (8 МБ) (Default stack size for pthreads). Конкретный лимит зависит от дистрибутива и настроек, поэтому перед объявлением крупного локального массива его стоит проверить: массив из миллиона int занимает около 4 МБ, из десяти миллионов - около 40 МБ, и при небольшом лимите стека такое объявление может привести к переполнению стека. Такие объёмы надёжнее выделять в куче.

Динамические массивы: куча и изменяемый размер

Динамический массив выделяют в куче: malloc, calloc или realloc в C, new в C++, автоматически в Python, Go и Java. Размер можно менять во время работы. Каждый вызов malloc возвращает указатель на блок, а память освобождают через free, иначе блок останется занятым до конца процесса.

int *arr = malloc(5 * sizeof(int));
if (arr == NULL) {
    /* обработка нехватки памяти */
}
arr = realloc(arr, 10 * sizeof(int));
free(arr);

realloc освобождает старый объект, на который указывает переданный указатель, и возвращает указатель на новый объект требуемого размера; содержимое нового объекта совпадает с содержимым старого вплоть до меньшего из двух размеров (realloc(3p) - Linux manual page). Поэтому указатель, сохранённый до вызова, после realloc использовать нельзя: результат нужно сохранять в переменную. Механику роста, коэффициент расширения и амортизированную стоимость добавления элемента разбирает статья Динамические массивы: рост, реаллокация и цена копирования.

Массивы фиксированной длины и списки: в чём разница

Массив фиксированной длины хранит элементы одного типа прямо в отведённом блоке. Список Python устроен иначе: это динамический массив указателей на объекты PyObject. Сами значения лежат в отдельных объектах, а слоты списка содержат ссылки. Поэтому запись [1, "a", 3.14] допустима: три указателя смотрят на int, str и float.

Влияние размера элемента и выравнивания на адресацию

Шаг смещения задаёт размер элемента, и для составных типов он не равен сумме размеров полей.

Почему адреса элементов могут быть не кратны размеру

Для типов, которые требуют выравнивания, компилятор вставляет padding между полями структуры, и размер структуры превышает сумму размеров полей.

struct A { char a; char b; int i; };  /* обычно 8 байт: 1 + 1 + 2 padding + 4 */
struct B { char a; int i; char b; };  /* обычно 12 байт: 1 + 3 padding + 4 + 1 + 3 padding */

Шаг массива таких структур равен sizeof(struct). Адрес arr[1] для struct A может оказаться base + 8, а не base + 5. При ручном разборе бинарных данных ошибка в один байт сдвигает все последующие поля. Перестановка полей в объявлении часто уменьшает размер элемента и, соответственно, объём всего массива. Как компилятор выбирает выравнивание, как перестановка полей сокращает размер массива структур и как выравнивание по границе кэш-линии убирает false sharing, описано в статье Выравнивание данных в памяти и padding в массивах.

Выравнивание и производительность

Процессор читает выровненные данные за одно обращение. Обращение к невыровненному указателю или объекту может привести к аварийному завершению программы, ошибочным данным или медленному доступу, если архитектура допускает невыровненные обращения (EXP36-C. Do not cast pointers into more strictly aligned pointer types). На 32- и 64-битных архитектурах x86 нарушение правил выравнивания обычно влечёт лишь снижение производительности, но в некоторых обстоятельствах такой код всё равно может демонстрировать неопределённое поведение. Исторически невыровненный доступ на процессорах вроде Motorola 68000 вызывал исключение, тогда как Intel 80386/80486 с ним справлялись, и именно из этих реалий во многом исходил стандарт C89 (Демистификация unaligned access undefined behavior в C).

С точки зрения стандарта C преобразование указателя на один объектный тип в указатель на другой объектный тип допускается, но если полученный указатель не выровнен должным образом для ссылочного типа, поведение не определено (ISO/IEC 9899, 6.3.2.3, пункт 7). Например, разыменование указателя как uint32_t, когда значение адреса не кратно четырём, - это неопределённое поведение. Автоматическое выравнивание делает компилятор, но при разборе сетевых протоколов и бинарных форматов раскладку приходится учитывать вручную: поля в пакете идут по спецификации, а не по правилам компилятора.

Отсюда типовой приём: читать буфер побайтово или копировать нужный фрагмент через memcpy в выровненную переменную, а не приводить указатель на середину буфера к int *. Второй вариант даёт невыровненный доступ и неопределённое поведение по стандарту C.

Практические примеры на C и Python

Пример на C: статический и динамический массивы

#include "stdio.h"
#include "stdlib.h"

int main(void) {
    int arr[5] = {1, 2, 3, 4, 5};
    for (int i = 0; i != 5; i++) {
        printf("arr[%d] = %d, address = %p\n", i, arr[i], (void *)&arr[i]);
    }

    int *dyn = malloc(5 * sizeof(int));
    if (dyn == NULL) {
        return 1;
    }
    for (int i = 0; i != 5; i++) {
        dyn[i] = (i + 1) * 10;
        printf("dyn[%d] = %d, address = %p\n", i, dyn[i], (void *)&dyn[i]);
    }
    free(dyn);
    return 0;
}

В обоих случаях адреса идут с шагом 4 байта, потому что malloc возвращает непрерывный блок нужного размера. Различаются только расположение блока (стек против кучи) и способ освобождения: статический массив исчезает вместе с кадром стека, динамический требует free.

Пример на Python: список и индексация

lst = [10, 20, 30]
for i in range(len(lst)):
    print(i, lst[i], id(lst[i]))
lst[1] = 999
print(lst[1], id(lst[1]))

После присваивания слот с индексом 1 указывает на другой объект, а слоты 0 и 2 продолжают ссылаться на прежние. Сама адресная формула не меняется: base + i * 8 на 64-битной системе. Для больших числовых наборов разница в памяти заметна: список хранит 8-байтовые указатели плюс отдельные объекты int, а array.array или numpy.ndarray хранят значения плотно, без обёрток на каждый элемент. Точный размер объекта int в CPython зависит от версии и сборки, поэтому при оценке расхода памяти его лучше измерять через sys.getsizeof, а не брать по памяти.

Зачем это знать DevOps-инженеру и сисадмину

Модель памяти влияет на чтение диагностики и выбор структур данных в скриптах и сервисах.

• Разбор дампов и core-файлов: зная базовый адрес и раскладку структуры, нужное поле находят по смещению, а не перебором.
• Производительность циклов: порядок обхода многомерного массива меняет время работы в разы. Формулы для row-major и column-major и их связь с кэш-линиями разобраны в статье Row-major и column-major.
• Расход памяти: список Python из большого числа чисел несёт оверхед на указатели и объекты, а array и numpy.ndarray хранят значения плотно. Методику оценки объёма и инструменты профилирования описывает статья Измерение памяти под массивы: профилирование и оценка.
• Разделяемая память: buffer и memoryview позволяют передавать один блок между процессами без копирования, и адресация внутри него строится по той же формуле.
• Бинарные форматы и протоколы: разбор пакетов и файлов требует учёта порядка байтов и выравнивания полей.

Типичные ошибки при работе с массивами и как их избежать

• Выход за границы в C: чтение arr[n] при длине n даёт неопределённое поведение и часто segmentation fault. Индекс проверяют до обращения, а не после.
• Ошибка на единицу в цикле: условие i != n при обращении к arr[i + 1] или граница вида i != n - 1 там, где нужен полный проход.
• Утечка памяти: каждый malloc должен завершаться free на всех путях выполнения, включая ветки с ошибками.
• Работа с указателем после realloc или free. Возвращённый realloc указатель сохраняют в переменную, а освобождённую обнуляют.
• Неверное смещение в массиве структур: шаг равен sizeof(struct), а не сумме sizeof полей.
• IndexError в Python: список сам проверяет границы, но отрицательные индексы отсчитываются с конца и иногда маскируют логическую ошибку.

Границы удобно контролировать ассертами, утечки и невыровненный доступ - запуском под valgrind или санитайзерами, адреса элементов - печатью в отладочной сборке. Эти три проверки занимают минуты и снимают большинство ошибок до продакшена.