Массивы и строки под капотом: Память и базовые операции

Статические массивы: Физическая непрерывность и арифметика указателей

Когда начинающий разработчик пишет arr = [1, 2, 3] в Python, ему кажется, что он создает гибкую, резиновую структуру, которая умеет расти, сжиматься и хранить что угодно. Эта абстракция невероятно удобна, но она скрывает суровую аппаратную реальность. На уровне процессора и оперативной памяти никаких «резиновых списков» не существует. Чтобы понять, почему одни алгоритмы работают на миллионах записей за миллисекунды, а другие заставляют сервер зависать, необходимо спуститься на уровень железа и разобрать самую фундаментальную структуру данных в информатике — статический массив.

Физическая непрерывность как фундамент

Оперативная память (RAM) компьютера не имеет встроенной структуры папок, деревьев или таблиц. Физически это колоссальная, одномерная лента байтов, где каждый байт имеет свой уникальный порядковый номер — физический адрес.

Статический массив — это строго непрерывный блок на этой ленте. Когда программа запрашивает создание массива из 10 целых чисел, операционная система ищет на ленте памяти свободный участок нужного размера и резервирует его целиком.

Ключевое слово здесь — непрерывность. Элементы массива располагаются в памяти вплотную друг к другу, без единого зазора. Если первый элемент лежит по адресу 1000, а каждый элемент занимает 4 байта, то второй элемент гарантированно начнется с адреса 1004, третий — с 1008, и так далее.

!Непрерывное выделение памяти в сравнении с фрагментированным

Эта физическая монолитность порождает два критических свойства статического массива:

Фиксированный размер. Массив нельзя просто «растянуть». Если мы заняли блок с адреса 1000 по 1040, то байт по адресу 1041 может быть уже отдан другой переменной, сетевому буферу или даже другой программе. Попытка записать туда данные приведет к повреждению чужой информации или аварийному завершению программы (Segmentation fault).

Однородность данных. Чтобы математика смещений работала, каждый элемент массива должен занимать строго одинаковое количество байтов. Массив 32-битных целых чисел состоит из блоков по 4 байта. Массив 64-битных чисел с плавающей точкой — из блоков по 8 байт. Смешивать размеры в классическом статическом массиве невозможно.

Арифметика указателей и цена доступа

В предыдущем курсе мы установили, что доступ к элементу по индексу работает за константное время благодаря математической формуле: . Теперь рассмотрим механику этого процесса детальнее.

Процессору не нужно перебирать элементы один за другим, чтобы найти пятый. Ему нужно только одно: адрес начала массива (указатель на нулевой элемент). Этот базовый адрес хранится в переменной, которая представляет массив.

Допустим, мы работаем с массивом 64-битных целых чисел (каждое занимает 8 байт). Базовый адрес массива в оперативной памяти — 4096. Нам нужно прочитать значение arr[3].

Процессор выполняет арифметику указателей:

Берет индекс: 3.

Умножает на размер типа данных: байта. Это смещение (offset) от начала массива.

Прибавляет смещение к базовому адресу: .

За одну процессорную инструкцию вычисляется точный физический адрес нужного байта, после чего контроллер памяти напрямую считывает данные, начиная с адреса 4120.

!Визуализация арифметики указателей

Именно поэтому индекс в программировании традиционно начинается с нуля. Индекс — это не порядковый номер элемента в бытовом понимании, это множитель смещения. Для нулевого элемента смещение равно . Мы обращаемся прямо к базовому адресу. Если бы индексы начинались с единицы, процессору пришлось бы при каждом обращении делать дополнительную операцию вычитания: . В масштабах миллиардов операций в секунду это стало бы неоправданной тратой ресурсов.

Пространственная локальность: Скрытый козырь массивов

Математическая константность — это теоретическая модель. На практике скорость работы алгоритма сильно зависит от архитектуры процессора, в частности, от кэш-памяти (L1, L2, L3).

Оперативная память работает медленно по меркам процессора. Если процессор будет ждать данные из RAM при каждом обращении к arr[i], он будет простаивать большую часть времени. Чтобы решить эту проблему, инженеры внедрили механизм кэширования.

Когда процессор запрашивает байт по адресу 1000, контроллер памяти не приносит ему один байт. Он захватывает целую «кэш-линию» (cache line) — обычно это блок в 64 байта, в который попадает запрошенный адрес и соседние с ним данные. Контроллер переносит этот блок в сверхбыстрый кэш L1 внутри самого процессора.

Здесь физическая непрерывность статического массива раскрывает свою главную силу — пространственную локальность (Spatial Locality).

Если мы итерируемся по массиву 32-битных чисел (по 4 байта каждое) и читаем arr[0], процессор загружает в кэш не только нулевой элемент, но и следующие 15 элементов (64 байта / 4 байта = 16 элементов). Когда на следующей итерации цикла код запрашивает arr[1], процессору вообще не нужно обращаться к оперативной памяти. Данные уже лежат в кэше L1, доступ к которому занимает доли наносекунды. Следующие 15 обращений будут практически бесплатными.

Именно поэтому алгоритмы, работающие с непрерывными массивами, на практике выполняются в разы быстрее, чем алгоритмы с той же асимптотической сложностью , но работающие с данными, разбросанными по памяти (например, в связных списках или графах, где каждый узел выделяется в случайном месте кучи). В алгоритмических секциях FAANG понимание пространственной локальности часто становится ключом к оптимизации систем, работающих с высокой нагрузкой (HighLoad).

Как Python обходит ограничения статики

Глядя на строгие правила статических массивов (один тип данных, фиксированный размер), возникает закономерный вопрос: как тогда работает стандартный list в Python? Ведь мы можем написать my_list = [42, "hello", True] и спокойно добавлять туда новые элементы.

Секрет в том, что стандартный список Python — это массив указателей, а не массив самих значений.

Под капотом интерпретатора CPython (написанного на языке C) список реализован поверх настоящего статического массива. Но этот массив хранит не числа и не строки. Он хранит адреса памяти (ссылки), по которым лежат реальные объекты.

В 64-битной системе любой адрес памяти занимает ровно 8 байт. Когда вы создаете my_list = [42, "hello", True], Python делает следующее:

Выделяет где-то в памяти объект целого числа 42.

Выделяет в другом месте памяти строковый объект "hello".

Запрашивает у системы непрерывный статический массив из трех 8-байтовых ячеек.

В первую ячейку записывает адрес объекта 42, во вторую — адрес строки, в третью — адрес объекта True.

Условие однородности статического массива соблюдено: все элементы весят ровно по 8 байт (это адреса). Арифметика указателей работает безупречно. Чтобы найти my_list[1], процессор вычисляет смещение , считывает из массива адрес и затем делает прыжок по этому адресу к реальной строке "hello".

За эту гибкость приходится платить. Мы теряем пространственную локальность. Да, сами ссылки лежат в памяти непрерывно и быстро загружаются в кэш процессора. Но объекты, на которые они указывают, разбросаны по всей оперативной памяти. Когда процессор читает адрес строки "hello", ему приходится делать дорогой запрос к RAM, чтобы получить сами символы. Кэш-линия заполняется мусором из соседних байтов, которые не имеют отношения к нашему списку.

Если в Python требуется максимальная производительность и работа с миллионами чисел, стандартный list становится узким местом из-за фрагментации памяти и накладных расходов на объекты. В таких случаях инженеры используют модуль array из стандартной библиотеки или библиотеку NumPy. Они создают настоящие классические статические массивы на уровне языка C, где числа лежат непрерывно, без оберток в виде Python-объектов, возвращая программе всю мощь кэша процессора.

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