Почему одна вставка в PHP‑массив может стоить 100 мс

На примере PHP хорошо видно, как внутренние оптимизации динамически типизированного языка развиваются и усложняются.

PHP‑массив выглядит универсальным, но внутри него скрыто множество оптимизаций и ветвлений, в их числе оптимизации для хранения и работы с массивами: Packed List & HashTable. Взаимодействие между ними и copy‑on‑write дают иногда неожиданное и непрозрачное поведение с точки зрения PHP программиста.

ВНИМАНИЕ! Примеры гиперболизированы и редко встречаются в реальности. Они намеренно показывают худший кейс для наглядности.

Пример 1. Массив — это List, HashTable или что‑то ещё?

В PHP массив — Швейцарский нож. Внутри данные могут храниться по‑разному: это может быть упакованный список: [1,2,3], а может быть ассоциативный массив (хеш‑таблица): [‘key’ => 123].
Это создает довольно интересные ситуации, например посмотрите на код ниже.

// Создаем последовательный массив без дырок$length = 10000000; // 10 000 000$arr = [];for ($i = 0; $i < $length; $i++) {    $arr[] = $i;}elapsedDebug(function () use (&$arr, $length) {    // Вставляем элемент, который порождает разрыв между ключами    $arr[$length*10] = 123;    // ИЛИ Вставляем элемент со строковым ключом    // $arr['test_string'] = 123;});// PHP 5.6.40   | Elapsed: 0.007 ms    | Peak RAM:  1426 MB// PHP 7.2.34   | Elapsed: 103.956 ms  | Peak RAM:  1090 MB// PHP 8.1.34   | Elapsed: 117.026 ms  | Peak RAM:  1154 MB// PHP 8.2.32   | Elapsed: 99.345 ms   | Peak RAM:   898 MB// PHP 8.3.30   | Elapsed: 102.610 ms  | Peak RAM:   898 MB// PHP 8.4.20   | Elapsed: 99.213 ms   | Peak RAM:   898 MB// PHP 8.5.8RC1 | Elapsed: 95.777 ms   | Peak RAM:   898 MB

В данном примере мы создаем обычный список [1,2,3], а после добавляем заведомо большой ключ, по сравнению с последним.
Тем самым обычный упакованный массив‑список 0-10_000_000 превращается в список с дыркой
0-10_000_000, 100_000_000
Такая же ситуация при создании строкового ключа.

Из‑за этого строчка с вставкой одного лишь элемента может занимать до 100ms, что очень даже много. Если после вставки попытаться вставить ещё один ключ, например 1_000_000_000 или другой строковый ключ, то вставка будет моментальной.

А что в Xdebug?

Так‑с. Внутри функции elapsedDebug — ничего интересного кроме вывода. Внутри нашей анонимной функции, в которой происходит вставка — тоже пусто.

Это происходит поскольку Xdebug обычно отслеживает трейсы и функции, а не присвоение переменных. А включение отслеживания присвоений раздувает трейсы до гигабайтов.
А если представить, что у вас сложный код, разная логика, то можно получить рандомные всплески времени скрипта, которые отловить крайне сложно. Например если бы такой элемент был вставлен самым первым, то такого всплеска бы не было.

Так почему? И почему на php5.6 такой проблемы нет?

Как видно, разница в потреблении памяти между php5.6 и php7.2 довольно велика. Снизилась аж на 24%, что весьма неплохо. В этом и проблема. Дело в том, что в php5.6 это были простые данные key => value, это было просто и удобно, но за это платили памятью и накладными расходами по вставке элементов.

В php7 же было сделано множество оптимизаций, в том числе более оптимизированная форма массива — упакованный список (packed list). Теперь язык начал стараться упаковать как можно сильнее эти данные, особенно в нем появилась проверка на неразрывные ключи, поскольку вставка $arr[] = $int означает вставить следующий ключ.

По сути в php7+ у нас сначала внутри выглядит так [0,1,2 ...], при попытке вставить разрыв, происходит полное пересоздание массива в хеш‑таблицу вида [0=>0, 1=>1 ...], что занимает много времени.

Что интересно, unset($arr[100]) не поменяет структуру массива на HashTable, поскольку ключ помечается удаленным, но при этом это перестает быть неразрывным массивом, но всё ещё является упакованной структурой, это может менять логику некоторых функций, которые проверяют именно на неразрывный список.

По итогу получаем следующее представление форм массивов:

HashTable — более универсальное представление, когда есть дырки, строковые ключи или непоследовательные индексы.

Packed List — упакованный список с последовательными целочисленными ключами от 0. Возможны дырки, созданные через unset

Пример 2. А если копнуть ещё глубже, будет ли видно дно?

Не уходим далеко и продолжаем цепочку. Как будет меняться производительность если мы начнем работать с такими массивами? Ох, тут множество интересных комбинаций

Для начала, создадим тестовые массивы.

// $arrList - последовательные массивы$length = 100000; // 100 000$arrList = [];for ($i = 0; $i < $length; $i++) {    $arrList[] = $i;}// $arrTable - массивы хеш-таблицы$arrTable = ['a' => 1];for ($i = 0; $i < $length; $i++) {    $arrTable[] = $i;}

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

// Попробуем классику, совместить два последовательных массиваelapsedDebug(function () use ($arrList1, $arrList2) {    array_merge($arrList1, $arrList2);});// PHP 5.6.40   | Elapsed: 96.458 ms   | Peak RAM: 460.5 MB// PHP 7.2.34   | Elapsed: 14.417 ms   | Peak RAM: 130.01 MB// PHP 8.1.34   | Elapsed: 15.898 ms   | Peak RAM: 130.01 MB// PHP 8.2.32   | Elapsed: 8.411 ms    | Peak RAM: 66.01 MB// PHP 8.3.30   | Elapsed: 7.882 ms    | Peak RAM: 66.01 MB// PHP 8.4.20   | Elapsed: 8.605 ms    | Peak RAM: 66.01 MB// PHP 8.5.8RC1 | Elapsed: 7.853 ms    | Peak RAM: 66.01 MB// Теперь интереснее, две хеш-таблицыelapsedDebug(function () use ($arrTable1, $arrTable2) {    array_merge($arrTable1, $arrTable2);});// PHP 5.6.40   | Elapsed: 93.519 ms   | Peak RAM: 460.5 MB// PHP 7.2.34   | Elapsed: 21.282 ms   | Peak RAM:   148 MB// PHP 8.1.34   | Elapsed: 20.922 ms   | Peak RAM:   164 MB// PHP 8.2.32   | Elapsed: 24.637 ms   | Peak RAM:   164 MB// PHP 8.3.30   | Elapsed: 25.161 ms   | Peak RAM:   164 MB// PHP 8.4.20   | Elapsed: 23.728 ms   | Peak RAM:   164 MB// PHP 8.5.8RC1 | Elapsed: 22.809 ms   | Peak RAM:   164 MB

Неплохо. Снова видно, что в php5.6 массивы мержаться соизмеримо и пиковая память не отличается. Далее же видно, что в php8.2 неплохо поработали с оптимизацией памяти мержа списков.

И теперь можно переходить к самому интересному, что если мержить список и хеш‑таблицу?

// Первым - последовательный массивelapsedDebug(function () use ($arrList, $arrTable) {    array_merge($arrList, $arrTable);});// Первым хеш-таблицуelapsedDebug(function () use ($arrTable, $arrList) {    array_merge($arrTable, $arrList);});Аналогично для операции $arr1 + $arr2  // Первым - последовательный массив (array_plus: $arr1 + $arr2)elapsedDebug(function () use ($arrList, $arrTable) {    $arrList + $arrTable;});// Первым хеш-таблицу (array_plus: $arr1 + $arr2)elapsedDebug(function () use ($arrTable, $arrList) {    $arrTable + $arrList;});

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

Интересно, что $arr1 + $arr2 также имеет разрыв, но не такой же как при array_merge. Важно заметить, что это не одинаковые операции, array_merge более сложный и вполне нормально, что он тратит больше памяти и времени при прямом сравнении.

Почему?

Под капотом там довольно интересно. По сути, там несколько логик мержа, в зависимости от типов массивов в аргументах. Конкретно тут логика строится по первому аргументу.

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

Пример 3. Не модифицируй аргумент функции

С мержами разобрались, но вот такие вот большие массивы‑списки, где в конце добавляется дырка или строковый ключ — довольно специфично. Подойдем к более насущному кейсу, который может быть у вас.

Предположим, у вас есть большой массив, вы передаете его в функцию — всё хорошо, всё работает, пока вы не сделаете маленькое изменение для удобства внутри функции.

// array size = 10 000 000// Наша хорошая функцияfunction goodFunc($arr) {    // Мы добавили костыль, в массив для дальнейших подсчетов    // добавлено это число    $someVirtualPayload = 123;    $arr[] = $someVirtualPayload;    // Дальше идет обработка массива}elapsedDebug(function () use ($arr) {    goodFunc($arr);});// PHP 5.6.40   | Elapsed: 448.260 ms  | Peak RAM: 2393.75 MB// PHP 7.2.34   | Elapsed: 74.961 ms   | Peak RAM: 1026.01 MB// PHP 8.1.34   | Elapsed: 77.254 ms   | Peak RAM: 1026.01 MB// PHP 8.2.32   | Elapsed: 40.413 ms   | Peak RAM: 514.01 MB // PHP 8.3.30   | Elapsed: 39.689 ms   | Peak RAM: 514.01 MB // PHP 8.4.20   | Elapsed: 40.029 ms   | Peak RAM: 514.01 MB // PHP 8.5.8RC1 | Elapsed: 41.055 ms   | Peak RAM: 514.01 MB

И мы видим просто лавинообразные цифры по памяти, особенно для php5.6
Опытные коллеги уже заметили в чем тут проблема, несмотря на то, что в функцию передается $arr как аргумент, на самом деле, туда передается сам $arr массив, тут работает механизм copy‑on‑write: значение не копируется сразу при передаче в функцию, но при попытке изменить массив внутри функции может произойти полное копирование.

Поэтому, несмотря на то, что кажется удобным добавить какой‑то костыль или виртуальное число, которое должно влиять на результат функции и хорошо ложится, крайне рекомендуется избегать такие модификации.

Если попробовать передавать его как ссылку &$arr, в таком случае при изменении внутри функции копирования не будет, но изменится содержимое $arr вне функции.
Но это не рекомендуется, поскольку это требует менять на ссылку во всей цепочке. Если позже его вызовут без ссылки, как пример ниже:

// Добавили ссылку тутfunction goodFunc(&$arr) {    $someVirtualPayload = 123;    $arr[] = $someVirtualPayload;}// Но забыли тутelapsedDebug(function () use ($arr) {    goodFunc($arr);});

То это всё ещё не решает проблему, ведь в elapsedDebug $arr — это не ссылка.

Итог

По данным тестам видно, что основные оптимизации были произведены в php7, в php8 же похоже было добавлено больше веток под конкретные кейсы и оптимизирована сама работа с массивами для тяжелых операций мержа, базовых операций вставки, размеры структур массивов.

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

Нужно ли это вам? В большинстве случаев — нет. Но для работы с большими данными, с использованием Legacy кода бизнес логики — полезно знать, если вылезет.

Тесты и скрипты на Гитхабе.