Массив как непрерывный блок памяти: базовый адрес и размер элемента
Массив из пяти значений типа int занимает в оперативной памяти ровно 20 байт, если int на этой платформе равен 4 байтам. Пять элементов лежат подряд, без промежутков, начиная с одного адреса. Такой макет дает массиву два свойства: доступ к элементу по индексу за постоянное время и плотную упаковку данных.
Непрерывность отличает массив от связного списка, где узлы разбросаны по куче и связаны указателями. Чтобы добраться до пятого узла списка, нужно пройти четыре предыдущих. Для массива достаточно знать адрес начала и размер одного элемента.
Схема адресов для int arr[5] с базовым адресом 0x1000:
- arr[0] - 0x1000
- arr[1] - 0x1004
- arr[2] - 0x1008
- arr[3] - 0x100C
- arr[4] - 0x1010
Шаг между соседними адресами равен 4 байтам, то есть размеру типа int. Общий размер массива считают как количество элементов, умноженное на размер элемента: 5 × 4 = 20 байт.
| Тип | Типичный размер (байт, 64-битная платформа) | Массив из 5 элементов, байт |
|---|---|---|
| char | 1 | 5 |
| short | 2 | 10 |
| int | 4 | 20 |
| long | 8 | 40 |
| double | 8 | 40 |
| указатель | 8 | 40 |
В C и C++ массив может лежать на стеке, если это локальная переменная, или в куче. Во втором случае память выделяют через malloc, calloc или new, а базовый адрес возвращает сама функция выделения. Модель доступа при этом не меняется: указатель на первый элемент плюс арифметика по индексу. О том, как ведут себя буферы, которые умеют расти, читайте в разборе динамических массивов: рост, реаллокация и цена копирования.
Что такое базовый адрес и как он определяется
Базовый адрес - это адрес первого элемента массива, arr[0]. Все остальные адреса вычисляются от него. В C и C++ имя массива в выражении превращается в указатель на первый элемент, поэтому arr и &arr[0] дают одно и то же значение. Исключения два: оператор sizeof возвращает размер всего массива, а оператор &arr дает указатель на массив из пяти int, а не на int.
Откуда берется конкретное число? У статического массива в глобальной области адрес известен на этапе компоновки, и линкер прописывает его в исполняемый файл. У локального массива адрес вычисляется при входе в функцию: компилятор выделяет место в стековом фрейме, сдвигая регистр указателя стека. У динамического массива адрес возвращает аллокатор: malloc(20) отдаст адрес начала свободного блока подходящего размера.
В Java и Python базовый адрес скрыт от программиста. Массив Java - объект, и ссылка на него ведет в кучу JVM, где лежат служебный заголовок, поле длины и сами данные. В CPython список реализован как массив указателей: он хранит указатели на объекты PyObject, а не сами значения, и при росте списка этот массив указателей перевыделяется. В исходном коде CPython это отражено в работе с массивом элементов типа PyObject** (ob_item), для которого при необходимости выполняется перевыделение памяти.
Внутреннее представление и размеры типов зависят от платформы, компилятора и версии рантайма. Прежде чем опираться на конкретные числа в байтах, проверяйте их на своей системе: sizeof в C, sys.getsizeof в Python, Unsafe или jol в JVM.
Размер элемента и почему он одинаков для всех элементов
Массив по определению содержит элементы одного типа. Значит, размер каждого элемента в байтах один и тот же, и это позволяет обойтись одной формулой смещения. Типичные размеры на 64-битных платформах: char - 1 байт, short - 2, int - 4, long и указатель - 8, double - 8 байт. Стандарт C не фиксирует размер int жестко, он гарантирует лишь минимальные диапазоны значений, поэтому на разных платформах числа расходятся.
Размер типа не критичен сам по себе. Критично то, что внутри одного массива это число постоянно. Если бы элементы были разного размера, пришлось бы хранить таблицу смещений и просматривать ее при каждом обращении. Постоянный размер превращает поиск адреса в умножение и сложение.
Для массива структур размер элемента равен размеру структуры с учетом выравнивания и padding. Структура из char и int займет не 5 байт, а 8: компилятор вставит три байта заполнения. Как перестановка полей меняет размер массива структур, разобрано в статье про выравнивание данных и padding.
Адресная арифметика: как вычислить адрес любого элемента
Формула, на которой держится вся индексная адресация: адрес элемента = базовый адрес + индекс × размер элемента. Три величины: начало массива, порядковый номер элемента и размер типа. Больше для доступа ничего не нужно.
Проверим на int arr[5] с базовым адресом 0x1000 и элементом 4 байта:
- arr[0]: 0x1000 + 0 × 4 = 0x1000
- arr[1]: 0x1000 + 1 × 4 = 0x1004
- arr[4]: 0x1000 + 4 × 4 = 0x1010
Умножение индекса на размер элемента и есть адресная арифметика. Компиляторы часто заменяют умножение на сдвиг, когда размер типа равен степени двойки, или накапливают смещение сложением внутри цикла. Логика остается прежней.
Формула адресации и её вывод
Вывод прост. Нулевой элемент начинается ровно по базовому адресу, смещение равно нулю. Первый элемент начинается сразу за нулевым, то есть через размер элемента байт. Второй - через два размера, i-й - через i размеров. Общее правило: смещение = индекс × размер элемента.
Для double (8 байт) адрес arr[3] = базовый + 3 × 8 = базовый + 24. Для char (1 байт) адрес arr[3] = базовый + 3, здесь индекс и смещение численно совпадают. Такое совпадение встречается только при размере элемента в один байт.
Формула дает верный адрес для любого индекса в границах массива. За границами она тоже выдаст число, просто укажет на чужую память. Поэтому контроль границ держится на уровне языка или среды, а не на уровне арифметики.
Пример вычисления адреса в C и ассемблере
В C запись arr[2] и *(arr + 2) означают одно и то же. Компилятор для int arr[5] посчитает адрес как arr + 2 * sizeof(int), то есть arr + 8. Масштабирование выполняет компилятор: в выражении arr + 2 двойка трактуется как количество элементов, а не байт.
Внутри процессора это превращается в одну инструкцию с масштабированием индекса. Для x86-64 типичный вид: mov eax, DWORD PTR [rbp-20+rax*4], где rax хранит индекс, а множитель 4 соответствует размеру int. Формат адресации [база + индекс × масштаб + смещение] встроен в архитектуру, и процессор вычисляет адрес без отдельных инструкций умножения. Для 8-байтовых элементов масштаб будет 8, для 2-байтовых - 2.
В Java и Python сходная арифметика выполняется внутри виртуальной машины или интерпретатора. Разработчик пишет arr[i], а байтовое смещение считает рантайм, добавляя проверку границ.
Логический индекс и физическое смещение: в чём разница
Логический индекс - порядковый номер элемента, который программист пишет в квадратных скобках. Физическое смещение - количество байт от начала массива до начала элемента. Связывает их один множитель: смещение = индекс × размер элемента. Для int arr[5] индекс 3 дает смещение 12 байт, а не 3. Путаница между этими величинами приводит к ошибкам при работе с указателями, парсингом бинарных форматов и сериализацией.
Почему индексация обычно начинается с нуля
При индексации с нуля смещение первого элемента равно нулю, а его адрес совпадает с базовым. Формула получается без поправок. Если бы нумерация начиналась с единицы, перед умножением пришлось бы вычитать единицу, а это лишняя операция в самом горячем месте программы.
В C нумерация с нуля закрепилась как стандарт и перешла в C++, Java, C#, Go, JavaScript, Python. Языки с другой базой тоже существуют: в Pascal диапазон индексов задают явно, а внутри все равно пересчитывают в смещение от начала. В Lua и MATLAB принята нумерация с единицы, но физический макет от этого не меняется.
Как смещение используется при доступе к элементу
Цепочка действий при чтении arr[i] выглядит так. Компилятор или интерпретатор берет базовый адрес, умножает индекс на размер элемента, складывает результаты и получает адрес ячейки. Процессор загружает значение по этому адресу в регистр. Все шаги, кроме самой загрузки из памяти, выполняются за фиксированное число тактов.
Для массива структур смещение считается по размеру структуры, включая байты заполнения. Массив из 100 структур по 32 байта займет 3200 байт, и адрес сотого элемента отстоит от начала на 99 × 32 = 3168 байт.
Выход за границы не ломает арифметику: адрес просто указывает мимо массива. В C и C++ это неопределенное поведение, которое может проявиться сразу или через часы работы. В Java среда выбросит ArrayIndexOutOfBoundsException, в Python - IndexError.
Практические следствия: производительность, кэш и безопасность
Непрерывный макет дает два измеримых эффекта: постоянное время доступа к элементу и предсказуемую загрузку данных в кэш. Оба эффекта заметны на реальных нагрузках, где разница между обходом массива и обходом связного списка измеряется в разы.
Почему доступ по индексу выполняется за константное время
Оценка O(1) означает, что число операций для вычисления адреса не зависит от индекса. Умножение и сложение для arr[0] и arr[1000000] занимают одинаковое время. Дополнительный множитель - промах кэша: если нужная строка памяти не в кэше, загрузка займет сотни тактов вместо единиц, но это свойство подсистемы памяти, а не формулы.
Сравните со связным списком. Чтобы дойти до миллионного узла, нужно выполнить миллион переходов по указателям, и каждый переход с большой вероятностью ведет в случайную область памяти. Массив позволяет вычислить адрес сразу и обратиться к нему напрямую.
Влияние выравнивания и кэш-линий на производительность
Процессоры читают память блоками. В руководстве по оптимизации Intel для архитектур Intel 64 и IA-32 указан размер кэш-линии 64 байта (Intel 64 and IA-32 Architectures Optimization Reference Manual). Для 4-байтового int это 16 значений: когда программа обращается к arr[0], в кэш попадают и arr[1] - arr[15]. Следующие пятнадцать обращений обслуживаются из кэша за единицы тактов.
Отсюда практическое правило: последовательный обход массива быстрее произвольного. Обход двумерного массива в порядке, не совпадающем с раскладкой в памяти, дает промах почти на каждом шаге вместо одного промаха на 16 элементов.
Второй фактор - выравнивание. Компиляторы размещают массивы по границам, кратным размеру элемента и часто кратным 16 или 32 байтам, чтобы переменная не пересекала границу кэш-линии. Для простых массивов это делается автоматически, для структур требуются осознанные решения по порядку полей.
Безопасность тоже связана с макетом. В C и C++ проверки границ нет: запись arr[5] для массива из пяти элементов попадет в соседнюю переменную. В Java доступ проверяется, при нарушении выбрасывается ArrayIndexOutOfBoundsException, в Python - IndexError, в C# - IndexOutOfRangeException. Цена проверки - несколько тактов на обращение, выигрыш - предсказуемое поведение вместо неопределенного.
Многомерные массивы: как они раскладываются в линейную память
Оперативная память линейна: у каждой ячейки один адрес. Двумерный массив приходится раскладывать в одномерную последовательность, и от выбранного порядка зависит формула адреса и скорость обхода.
Для массива M × N при построчном хранении адрес элемента [i][j] считается так: базовый + (i × N + j) × размер элемента. Пример: int arr[3][4] с базовым адресом 0x2000 и элементом 4 байта. Адрес arr[1][2] = 0x2000 + (1 × 4 + 2) × 4 = 0x2000 + 24 = 0x2018.
Построчное и столбцовое хранение: сравнение
Выбор порядка хранения - это вопрос соглашения. Построчный (row-major) формат используется, например, в языке C, тогда как Fortran применяет столбцовый (column-major) формат (Memory layout of multi-dimensional arrays). В NumPy формат по умолчанию - построчный; столбцовый задается явно при создании или изменении формы массива. В библиотеке ndarray для Rust формат памяти по умолчанию тоже построчный, а формат Fortran (column-major) задается отдельно (ndarray for NumPy users).
Для матрицы 2 × 3 разница видна сразу:
- row-major: [0][0], [0][1], [0][2], [1][0], [1][1], [1][2]
- column-major: [0][0], [1][0], [0][1], [1][1], [0][2], [1][2]
Формула для column-major меняется на базовый + (j × M + i) × размер элемента. Практический вывод: вложенные циклы нужно писать так, чтобы самый внутренний цикл шел по последнему индексу в порядке хранения. Формулы, работа кэш-линий и перенос кода между C, Fortran, NumPy и BLAS разобраны в статье про row-major и column-major.
Java и C# добавляют нюанс. Конструкция int[][] там означает массив ссылок на массивы, и строки лежат в разных участках кучи. Плотный блок получается у одномерного массива либо у прямоугольной формы, которую среда размещает одним куском.
Как модель реализуется в разных языках: от C до Python
Формула смещения одна, но объем контроля у языков разный. Где-то программист сам считает байты, где-то рантайм прячет арифметику и добавляет проверки.
Массивы в C и C++: ручное управление и указатели
Имя массива в выражении превращается в указатель на первый элемент, поэтому arr[i] эквивалентно *(arr + i). Указатель можно складывать с целым числом, и компилятор сам умножит его на размер элемента. Разность двух указателей даст количество элементов между ними, а не байт.
Границы не проверяются. Запись arr[5] для массива из пяти элементов компилируется без ошибок и приводит к неопределенному поведению. Ошибка может не проявиться при тесте и всплыть в продакшене. Полезные инструменты здесь: AddressSanitizer, Valgrind, статические анализаторы и сборка с -fsanitize=bounds.
Отдельный случай - динамические массивы. Их создают вручную: выделяют блок через malloc или new, хранят указатель и длину, при переполнении выделяют новый блок и копируют данные. Цена копирования и выбор коэффициента роста разобраны в статье про динамические массивы: рост, реаллокация и цена копирования.
Массивы в Java, Python и других управляемых средах
В Java массив - это объект, содержащий число переменных (компонентов); число компонентов - это длина массива, а сами компоненты адресуются целочисленными индексами от 0 до length-1 (Chapter 10. Arrays, Java Language Specification). Массивы в Java - специальные объекты с атрибутом length. Данные лежат непрерывно, индексация начинается с нуля, длина фиксируется при создании. Многомерный массив в Java - массив массивов, поэтому строки не обязательно лежат рядом.
В Python список устроен иначе: это динамический массив указателей на объекты (How is Python's List Implemented?). Каждый элемент - ссылка на PyObject, поэтому целые числа в списке лежат не подряд, а в отдельных объектах. Принцип непрерывности сохраняется, но на уровне указателей, а не значений. В исходном коде CPython список использует массив элементов типа PyObject** (ob_item), для которого выполняется перевыделение памяти при необходимости (cpython/Objects/listobject.c). Для плотного хранения однотипных чисел используют модуль array или массив NumPy, где байты значений идут подряд.
В Go срез - это структура данных, описывающая непрерывную секцию массива, который хранится отдельно от самой переменной среза (Arrays, slices (and strings): The mechanics of 'append'). Заголовок среза содержит указатель на массив, длину и ёмкость, а сами данные лежат в непрерывном блоке. В C# массив непрерывен и проверяется на границы, а Span позволяет работать с его частью без копирования.
Практический вывод для администратора и DevOps-инженера: когда профилировщик показывает промахи кэша или падение скорости на больших объемах данных, смотрите на раскладку структур в памяти и порядок обхода, а не только на алгоритм. Понимание формулы смещения помогает читать метрики, оценивать расход памяти и предсказывать, где именно упрется нагрузка.