Как устроены массивы в PHP

    В прошлой статье я рассказывал о переменных, теперь пойдет речь о массивах.

    Что такое массивы на уровне PHP?


    На уровне PHP, массив — это упорядоченный список скрещенный с мэпом. Грубо говоря, PHP смешивает эти два понятия, в итоге получается, с одной стороны, очень гибкая структура данных, с другой стороны, возможно, не самая оптимальная, точнее, как выразился Anthony Ferrara:
    PHP arrays are a great one-size-fits-all data structure. But like all one-size-fits-all <anything>, jack-of-all-trades usually means master of none.

    Ссылка на письмо



    (на картине изображен HashTable с Bucket-ами, В. Васнецов)

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

    // time.php
    $ar = array();
    $t = 0;
    
    for ($i = 0; $i < 9000; ++$i) {
        $t = microtime(1);
        $ar[] = 1;
        echo $i . ":" . (int)((microtime(1) - $t) * 100000000) . "\n";
    }
    
    // memory.php
    $ar = array();
    $m = 0;
    
    for ($i = 0; $i < 9000; ++$i) {
        $m = memory_get_usage();
        $ar[] = 1;
        echo $i . ":" . (memory_get_usage() - $m) . "\n";
    }
    


    Запускаем эти скрипты php time.php > time и php memory.php > memory, и нарисуем графики по ним, ибо данных много и смотреть на цифры долго (данные по времени были собраны много раз и выровнены, чтобы избежать лишних скачков на графике).


    (по оси X — кол-во эл-тов в массиве)

    Как видно, на обоих графиках есть скачки и по потребляемой памяти и по использованному времени, и эти скачки происходят в одни и те же моменты.
    Дело в том, что на уровне C (да и вообще на системном уровне), не бывает массивов, с нефиксированным размером. Каждый раз, когда вы создаете массив в C, вы должны указать его размер, чтобы система знала, сколько нужно памяти на него выделить.
    Тогда как это реализовано в PHP и как объянить те скачки на графике?
    Когда вы создаете пустой массив, PHP создает его с определенным размером. Если вы заполняете массив и в какой-то момент достигаете и превышаете этот размер, то создается новый массив с вдвое большим размером, все элементы копируются в него и старый массив уничтожается. Вообще, это стандартный подход.

    И как это реализовано?


    На самом деле, для реализации массивов в PHP, используется вполне себе стандартная структура данных Hash Table, о деталях реализации которой мы и поговорим.

    Hash Table хранит в себе указатель на самое первое и последнее значения (нужно для упорядочивания массивов), указатель на текущее значение (используется для итерации по массиву, это то, что возвращает current()), кол-во элементов, представленых в массиве, массив указателей на Bucket-ы (о них далее), и еще кое-что.

    Зачем
        нам
            ведра нужны
    и куда
        нам
            их ложить


    В Hash Table есть две главные сущности, первая — это собственно сам Hash Table, и вторая — это Bucket (далее ведро, чтобы не заскучали).

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

    Таким образом, когда вы добавляете новый элемент в массив, если такого ключа там еще нет, то под него создается новое ведро и добавляется в Hash Table.

    Но что самое интересное — это как в Hash Table хранятся эти ведра.

    Как было сказано выше, у HT есть некий массив указателей на ведра, при этом ведра доступны в этом массиве по некоему индексу, а этот индекс можно вычислить зная ключ ведра. Звучит немного сложно, но на самом деле, все гораздо проще чем кажется. Попробуем разобрать, как происходит получение элемента по ключу из HT:

    • Если ключ строковый — то происходит хеширование строки до integer-a (используется алгоритм хеширования DJBX33A):
      • Первоначальное значение хеша взято за магические 5381
      • На каждый символ ключа умножаем хеш на 33 и прибавляем номер символа по ASCII
    • На полученый числовой ключ накладывается маска (bitwise and), которая всегда равна размеру массива (который с ведрами) минус 1
    • В итоге этот ключ можно использовать как индекс, чтобы вытащить нужный указатель на Bucket из массива

    Про маску: допустим массив указателей содержит 4 элемента, таким образом маска равна трем, то есть 11 в двоичной системе.
    Теперь если в качестве ключа у нас получится число вроде 123 (1111011), то после наложения маски мы получим 3 (3 & 123), это число уже можно будет использовать как индекс.

    После этого попробуем добавить в Hash Table, с маской 3, элементы с ключами 54 и 90. А оба этих ключа после наложения маски будут равны двойки.

    Что делать с коллизиями?


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



    Вернемся к нашему кейсу с ключами 54 и 90, и маской 3. После того, как вы добавите 54, структура HT будет выглядеть примерно так:

    {
        nTableSize: 4,        // размер массива указателей на ведра
        nTableMask: 3,        // маска
        nNumOfElements: 1,    // число элементов в HT
        nNextFreeElement: 55, // это будет использовано тогда, когда вы захотите добавить элемент в конец массива (без ключа)
        ...,
        arBuckets: [
            NULL,
            NULL,
            0xff0, // представим, что это указатель на Bucket, а сам он описан ниже
            NULL
        ]
    }
    
    0xff0: {
        h: 54,         // числовой ключ
        nKeyLength: 0, // это длина ключа, в случае когда он строковый
        pData: 0xff1,  // указатель на значение, в данном случае на структуру zval
        ...
    }
    


    Теперь добавим элемент с ключом 90, теперь все будет выглядеть примерно так:

    {
        nTableSize: 4,
        nTableMask: 3,
        nNumOfElements: 2,
        nNextFreeElement: 91,
        ...,
        arBuckets: [
            NULL,
            NULL,
            0xff0, // здесь все так же всего один Bucket
            NULL
        ]
    }
    
    0xff0: {
        h: 54,
        pListNext: 0xff2, // здесь хранится указатель на следующий Bucket по порядку (для итерирования)
        pNext: 0xff2,     // а сюда попал новый Bucket с таким же хешем
        ...
    }
    
    0xff2: {
        h: 90,
        pListLast: 0xff0, // это предыдущий элемент
        pLast: 0xff0,     // а это тот же предыдущий элемент
        ...
    }
    


    Теперь давайте добавим несколько элементов до переполнения nTableSize (напомню, что переполнение будет только тогда, когда nNumOfElements > nTableSize).
    Добавим элементы с ключами 0, 1, 3 (такие, которых еще не было, и после наложения масок они останутся теми же), вот что будет:

    {
        nTableSize: 8,         // теперь размер вдвое больше (прям как в той рекламе)
        nTableMask: 7,
        nNumOfElements: 5,
        nNextFreeElement: 91,  // это число осталось неизменным
        ...,
        arBuckets: [ // теперь некоторые ведра переместились на новые места, с учетом новой маски и следовательного нового индекса
            0xff3, // key = 0
            0xff4, // key = 1
            0xff2, // key = 90 - теперь здесь сидит ключ 90 (его индекс 90 & 7 = 2), а его бывший сосед съехал на 6-й индекс
            0xff5, // key = 3
            NULL,
            NULL,
            0xff0, // key = 54
            NULL
        ]
    }
    
    0xff0: {
        h: 54,
        pListNext: 0xff2, // порядок остался тот же, поэтому это значение неизменно
        pNext: NULL,     // а здесь теперь ничего
        ...
    }
    
    0xff2: {
        h: 90,
        pListNext: 0xff3,
        pListLast: 0xff0,
        pLast: NULL,
        ...
    }
    
    0xff3: {
        h: 0,
        pListNext: 0xff4,
        pListLast: 0xff2,
        ...
    }
    
    0xff4: {
        h: 1,
        pListNext: 0xff5,
        pListLast: 0xff3,
        ...
    }
    
    0xff5: {
        h: 3,
        pListNext: NULL, // он был добавлен последним
        pListLast: 0xff4,
        ...
    }
    


    То, что происходит после переполнения массива, называется rehash. По сути это итерирование по всем существующим ведрам (через pListNext), назначение их соседей (коллизий) и добавление ссылок на них в arBuckets.

    А как же на самом деле происходит получение элемента по ключу? К предыдущему алгоритму добавится еще кое что:
    • Если ключ строковый — то происходит хеширование строки до integer-a (используется алгоритм хеширования DJBX33A):
      • Первоначальное значение хеша взято за магические 5381
      • На каждый символ ключа умножаем хеш на 33 и прибавляем номер символа по ASCII
    • На полученый числовой ключ накладывается маска (bitwise and), которая всегда равна размеру массива (который с ведрами) минус 1
    • Вытаскиваем ведро по индексу
    • Если ключ этого ведра равен искомому — поиск завершен, иначе:
    • В цикле берем ведро из pNext (если существует) и смотрим равен ли ключ

    Так до тех пор, пока либо не закончатся ведра в pNext (тогда будет выкинут Notice), либо пока не будет найдено совпадение.

    Стоит отметить, что в PHP почти все посторено на одной этой структуре HashTable: все переменные, лежащие в каком-либо scope-е, на самом деле лежат в HT, все методы классов, все поля классов, даже сами дефинишины классов лежат в HT, это на самом деле очень гибкая структура. Помимо прочего, HT обеспечивает практически одинаковую скорость выборки/вставки/удаления и сложность всех троих является O(1), но с оговоркой на небольшой оверхед при коллизиях.

    Кстати, здесь я реализовал Hash Table в самом PHP. Ну, то есть, имплементировал PHP-шные массивы в PHP =)
    Поделиться публикацией
    Похожие публикации
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 40
    • –17
      *на первой картине изображена баба с коромыслом автор — Воснецов…
      • +4
        Васнецов он…
        • +2
          Ох, я плох в искусстве.
          • +2
            Я похоже тоже…
            • 0
              А он там даже копирайт поставил ) слева снизу.
              • 0
                Да-да! Я видел, но так и не разглядел что там написано, увы.
        • +1
          Дежавю?
          • 0
            Где?
            • +1
              Так дежавю же_). Всмысле пруфа нету — но вроде как был.
          • +2
            Обычно buckets в русскоязычной литературе называют «корзинами», а не «вёдрами».
            • 0
              Бабу с корзинами Васнецов, к сожалению, не написал ((
            • –1
              Увеличивается в два раза при заполнении для амортизации операции выделения памяти, а не потому что в нет массивов с нефиксированным размером.
              Если нужна матчасть, гуглите амортизационный анализ.
              • 0
                в C нет массивов*
                • 0
                  В реализации по большей части для того, чтобы уменьшить число коллизий и соответственно уменьшить число итераций по сколлайденным бакетам при поиске.
                  • +3
                    Может расскажете нам про амортизацию выделения памяти под массив для бакетов хэштаблицы? Гугл особо делиться информацией не хочет.
                    Или Вы имели ввиду, что амортизацией является именно удвоение массива, а не, скажем, инкрементальное увелечение? В таком случае да, я даже не знал что у этого действия есть свое название и как-то глупо было бы увеличивать массив инкрементально, поэтому я не стал вдаваться в детали очевидного решения.
                  • –4
                    И вообще хотя бы про хэштаблицы — это же совсем базовые вещи. При чём тут вообще PHP?
                    • +4
                      Гм… Что значит причем тут пхп? Загляните в заголовок, там сюрприз =)
                      • –3
                        Это базовая структура данных сделанная в пхп так же как в во всех других языках, правда немного через задницу, как это обычно в пхп.
                        • 0
                          Через задницу т.к. это комбинированная структура. Я смотрю, что даже автор к примеру не знает как организовать эффективный список на основе массива.
                  • +2
                    Что-то вы про классический hash table слишком подробно расписали, а чем PHP-шная реализация отличается от классической не отметили.
                    Я, например, не понял чем обеспечивается упорядоченность массива после сортировки… pListNext может ссылаться на элемент из другой корзины? Получается, что эффективная итерация в обратном порядке невозможна?
                    • 0
                      А, блин. Понял. Тут в одной структуре скрестили практически независимые друг от друга хеш-таблицу (h, pData) и двусвязный список (pListNext, pListLast)…
                      И почему назвали pListLast а не pListPrev…

                      Чувствую оверхед на это должен быть приличный (по 3 указателя на каждый элемент против 1 на классическую hash table и 0 для массива). Ну и поиск по числовому индексу в такой структуре происходит через хеш-таблицу тоже, что не очень круто.

                      Кстати, кто-то объяснит зачем им понадобился именно двусвязный список? Или это исключительно для удаления элементов?
                      • 0
                        pListLast меня тоже сначала смутил… И не понятно зачем нужен pLast (могли бы и односвязным списком для сколлайденых обойтись)

                        А в чем проблема поиска по числовому индексу через хештаблицу? Он не может быть реализован иначе т.к. массив в пхп это еще и мэп и вы можете использовать не только последовательные ключи.

                        Двусвязный так же и сортировку упрощает. На самом деле в бакете в пхп, так на память, где-то шесть членов и примерно десять в хештаблице (в структурах), это об экономии памяти.
                        • 0
                          Проблема поиска по числовому индексу в том, что это намного медленнее, чем в массивах в более типизированных языках. Я всё думал, может в пхп всё же массивы реализованы в комбинации обычный массив (для целых индексов) + хэш… Но в такой реализации непонятно как реализовать: $m[0] = $m[10000000] = «ok». Всё же надеялся, что светлые умы что-нибудь да придумали)
                          • 0
                            Я не знаю такого алгоритма, который был бы в данном случае оптимальнее, чем open addressed hash table. А если в пхп нужен обычный массив (не такой, где при размере в 100 элементов можно пользоваться ключом больше 99), то можно юзать SplFixedArray.
                    • 0
                      Для повышения кругозора можете сравнить, как реализуются словари в Python — blip.tv/pycon-us-videos-2009-2010-2011/pycon-2010-the-mighty-dictionary-55-3352147
                      • 0
                        О, это же Open adressed hash tables en.wikipedia.org/wiki/Open_addressing
                        Даже не подозревал что они используются. Это и про python 2.7 и про 3.x?
                        • 0
                          Linear Probing используется в стандартном Java-классе IdentityHashMap.
                          • 0
                            Брэндон делал замеры для доклада на 2.6.
                        • 0
                          Я решил не возвращаться к нашему кейсу с ключами 54 и 90… А вообще спасибо, мне нравятся ваши статьи, довольно интересно заглядывать внутрь.
                          • +1
                            Не очень понял график с памятью. Типа при 4096 элементах памяти требуется дофига, а при 4097 уже с гулькин нос? И вообще научитесь подписывать оси на графике. Это ж технический пост, а не какой-то дешёвый маркетинг.
                            • 0
                              4096-8191 элементов потребляется одинаковое количество памяти. Графики можете в виде лестницы представить.
                              • +1
                                А вот вы неправы. Я вчитался в детали и запустил тест. График в статье показывает разницу до и после вставки определённого элемента и падает он не до нуля, а до 132-136. А график кумулятивного потребления памяти выглядел бы так:

                                (по вертикали общий объём памяти в байтах)
                                Заметьте, совсем другая картина: нет никаких ужасающих скачков. Сами корзины едят гораздо больше памяти, чем собственно хэш-таблица.
                                • +1
                                  Вот оно что. Да, недопонял я этот момент. Спасибо
                                • 0
                                  Интересно ещё представить график в другом виде, как я это делал в своей недавней статье:

                                  По вертикали отношение используемой памяти в байтах к числу элементов в массиве, то есть количество байт на элемент. Тестировалось на PHP 5.3.2-1ubuntu4.14 (i686).
                                  Видно, что в пределе расширение хэш-таблицы вызывает прыжки на 4 байта, со 140 до 144, вызывая трёхпроцентные колебания вокруг общего среднего. Кстати, интересен вопрос, почему у маленьких таблиц затраты на запись от 132, а дальше нижний порог доходит до 140.
                                • 0
                                  Да, простите за хреновые графики. Просто так долго искал тулзу, которая способна построить график по, хотя бы, 1000 точек (тобишь не юзает гугловские чарты, которые вываливаются в 400 из-за длинных урлов), что терпения уже еле хватало на детали.
                                  Кстати если кто-нибудь подскажет действительно хорошую тулзу для чартов, буду признателен.
                                  • +1
                                    Я использую неправославный Excel, но вообще люди любят gnuplot.
                              • +1
                                Асимптотика O(1) при работе с массивами радует.
                                • 0
                                  Когда читаю книги о том же PHP, всегда, когда сталкивался вновь с теми же массивами (циклы, функции и тп.), хотелось видеть не только описание на примере, но также пару строк о том, где эти массивы применяются при разработке приложений. Ведь, легче разобраться в том, что понятно, как и где это можно будет применить на практике.

                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.