Массивы в PHP — это не массивы

Эти два массива содержат один и тот же миллион целых чисел под одними и теми же ключами в одинаковом порядке, и  ===  подтверждает, что они равны. Один из них занимает 16,0 МБ, а другой — 40,0 МБ.

 <?php

declare(strict_types=1);

$baseline = memory_get_usage();
$packed = range(0, 999_999);
printf("packed  %s bytes\n", number_format(memory_get_usage() - $baseline));

$baseline = memory_get_usage();
$hashed = range(0, 999_999);
$hashed['total'] = 0;
unset($hashed['total']);
printf("hashed  %s bytes\n", number_format(memory_get_usage() - $baseline));

var_dump($packed === $hashed); 

 packed  16,793,680 bytes
hashed  41,943,120 bytes
bool(true) 

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

Одна структура, две компоновки

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

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

 <?php

declare(strict_types=1);

$stock = ['widget' => 4, 'anvil' => 19, 'rope' => 7];
$stock['crate'] = 2;

foreach ($stock as $sku => $count) {
    echo $sku, ' ', $count, PHP_EOL;
} 

 widget 4
anvil 19
rope 7
crate 2 

Эта гарантия порядка крайне важна для огромного количества PHP-кода, и именно по этой причине структура не может быть простым вектором. Каждый элемент несёт в себе служебную информацию, обеспечивающую работу порядка и произвольных ключей, — из неё в основном и состоят 40 МБ выше.

От чего отказывается упакованная компоновка

Когда ключами являются целые числа от нуля по порядку, движок переходит на упакованную компоновку (packed layout): он хранит значения подряд и вычисляет ключ исходя из позиции. Здесь нет бакетов и индексного массива, поэтому чтение — это смещение, а не поиск по хэшу.

При измерениях на PHP 8.5.9, arm64, NTS, сборка Homebrew, на ноутбуке Apple M4 Pro под управлением macOS при 1 миллионе элементов: упакованная форма занимала 16,79 байта на элемент, а хэшированная — 41,94 (разница в 2,5 раза). Шестнадцать из этих байтов — это размер одного слота значения в 64-битной сборке, а остальное — ключ, хэш и индекс, которые упакованная форма не хранит. Обе цифры включают ёмкость, которую массив выделил, но не заполнил, поэтому значение для packed-формы не равно ровно 16. Каждая цифра памяти ниже представляет собой одно точное измерение, а не медиану: повторные запуски возвращают байтово-идентичные значения, так что дисперсии нет.

Накладные расходы на элемент размываются тем, что именно вы храните в элементах. Повторение измерения на тех же 1 млн элементов с фиксированными 6-символьными строками в качестве значений дало 49,59 против 74,74 байта на элемент — соотношение 1,51 вместо 2,50. Разница между компоновками не изменилась: 25,15 байта, ровно столько же, сколько было с целыми числами. При шестнадцати символах это 64,79 против 89,94 (соотношение 1,39), и разница всё ещё 25,15 байта. Накладные расходы относятся к самой таблице и являются фиксированной платой за элемент; соотношение же зависит от того, что вы помещаете в элементы.

Что разрушает packed-компоновку, а что нет

Общепринятое мнение гласит, что  unset()  в середине списка ломает упакованную компоновку. На этой сборке это не так. Я применил каждую операцию к новому  range(0, N - 1)  и определил компоновку по размеру памяти массива, где две формы различаются более чем в два раза:

На двух из них стоит остановиться.  ksort()  преобразовал массив, который уже был отсортирован по ключам — сортировке нечего было менять, но это всё равно обошлось в 25 МБ на миллионе элементов. А целочисленный ключ за концом массива допускается до границы, которая отслеживает выделенную ёмкость массива, а не количество элементов: добавление индекса N к списку из миллиона элементов оставило его упакованным, в то время как индекс 10N преобразовал его. Где именно находится эта граница и почему, я не стал выяснять в исходном коде на C.

Одна операция, отсутствующая в таблице, не меняет компоновку, но стоит дороже любого перехода в ней: обход массива с помощью  foreach ($rows as &$row)  оставляет его упакованным, но при этом добавляет по 32 байта к каждому элементу, что на этом миллионе целых чисел превышает расходы хэшированной формы.

А вот что делает  unset()  взамен — вообще ничего не меняет в расходе памяти:

 <?php

declare(strict_types=1);

$rows = range(0, 999_999);
$before = memory_get_usage();

for ($i = 0; $i < 500_000; $i++) {
    unset($rows[$i * 2]);
}

printf("after unsetting half: %+d bytes, %d elements left\n", memory_get_usage() - $before, count($rows));

$rows = array_values($rows);
printf("after array_values():  %+d bytes, %d elements left\n", memory_get_usage() - $before, count($rows)); 

 after unsetting half: +0 bytes, 500000 elements left
after array_values():  -8388576 bytes, 500000 elements left 

Полмиллиона элементов исчезли, но массив не освободил ни байта памяти. Пересборка освободила 8 МБ, потому что память выделялась под то, что осталось, а не под то, что было раньше.

Цена компоновки зависит от того, как вы её читаете

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

В этой таблице используется 1 048 576 элементов вместо миллиона выше, и это изменение намеренное: строки со случайным доступом индексируют массив с помощью линейного конгруэнтного генератора с маской по размеру массива, а маска состоит из одних единиц только тогда, когда размер является степенью двойки. При одном миллионе  & 999999  имеет двенадцать установленных бит и задействует 512 отдельных слотов — рабочий набор, который помещается в кэш и ничего не говорит о случайном доступе. Те же ключи, те же значения, тот же порядок вставки, то же количество, 15 чередующихся прогонов для каждого варианта,  opcache.jit=disable  на протяжении всего теста. Каждый прогон выводит свой размер памяти, поэтому различие двух компоновок подтверждается в момент замера времени. Каждая ячейка — это медиана по 15 прогонам, а полный диапазон указан в скобках:

Строки последовательного чтения различаются на 6% с диапазонами, которые едва соприкасаются, так что это следует трактовать как незначительный эффект, который данный метод едва способен зафиксировать. Четырёхкратное увеличение количества чтений за итерацию расширяет разницу до 8,9% с явно разделяющимися диапазонами, что говорит о том, что оверхед цикла размывал реальную разницу при выборке.

Случайный доступ — вот ключевая строка. При 2,35x, когда два диапазона нигде не пересекаются, а вариант с четырьмя чтениями за итерацию сходится на 2,36x, хэшированная компоновка стоит более чем вдвое дороже — на таблице размером 40 МБ, где почти каждый поиск приводит к кэш-промаху, а у хэшированной формы есть ещё один уровень косвенности для промаха. Запись показывает 1,21x.

Таким образом, хэшированный список из миллиона целых чисел стоит в 2,5 раза больше памяти, около 6% при последовательном сканировании и более чем вдвое больше при произвольных поисках. Проход, который обходит массив от начала до конца, этого почти не замечает; проход, прыгающий по массиву, платит двойную цену. Память расходуется в любом случае, а нагрузка на память — это одна из тех издержек, которые не устраняются ни OPcache, ни JIT.

Альтернативы и условия их применения

 SplFixedArray  хранит 16 байт на элемент, как и packed-массив. Его преимущество в том, что он выделяет ровно тот размер, который вы запросили, тогда как обычный массив округляет свою ёмкость в большую сторону: при миллионе элементов он составил 0,95x от packed-массива, при 1 048 576 — ровно 1,00x, а при 1 048 577 (на один элемент больше точки удвоения) — 0,50x. По сравнению с хэшированной формой он меньше в 2,62x, 2,50x и 5,00x при тех же трёх размерах (последнее — потому что ёмкость хэшированного массива там также удваивается). Он также имеет фиксированную длину и лишён семантики массива, поэтому подходит для буфера известного размера, а не для рабочего списка.

Генератор обходит этот вопрос стороной. Итерация по миллиону значений через генератор удерживала 960 байт в пике против 16,0 МБ для материализованного списка, поскольку одновременно существует только одно значение. Условие состоит в том, что достаточно одного прохода: ничто нельзя посчитать, отсортировать или прочитать дважды.

Третий вариант — вообще не строить список. Запрос, который возвращает 50 000 строк для того, чтобы приложение посчитало сумму по колонке, материализует 50 000 массивов ради получения одного числа, а виртуальная машина обходит их по одному опкоду за раз.

Что с этим делать

Обращайтесь к цифрам памяти до того, как смотреть на компоновку.  memory_get_peak_usage(true)  на реалистичном наборе данных покажет, являются ли массивы проблемой в принципе, и для большинства приложений, хранящих несколько тысяч строк, ответ будет «нет». Разница в 25,15 байта выше — это цифра для миллиона элементов; при нескольких тысячах строк округление ёмкости смещает её, и для размеров от 1000 до 8193 я намерял от 20 до 48 байт на элемент. Ничто из этого не оправдывает переписывание кода.

Где компоновка действительно заслуживает внимания, так это при произвольном чтении большого массива. Это единственный шаблон выше, который стоил более чем вдвое дороже, поэтому если на «горячем» пути обращения происходят к разбросанным позициям в списке из сотен тысяч элементов, проверьте, не преобразовало ли что-то его и не возвращает ли  array_values()  всё в исходное состояние.

Когда количество элементов велико, посчитайте их, прежде чем оптимизировать байты. Сокращение накладных расходов на элемент вдвое спасёт половину; отказ от материализации списка спасёт практически всё, и приведенные выше измерения разводят эти два варианта на четыре порядка. Используйте  SplFixedArray , когда длина известна и фиксирована, генератор — когда достаточно одного прохода, и  array_values()  — когда долгоживущий массив удерживает ёмкость, которая ему больше не нужна.

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