Пользователь
0,0
рейтинг
23 декабря 2012 в 21:56

Разработка → Как устроены массивы в PHP

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 =)
Никита Нефедов @nikita2206
карма
137,2
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (40)

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

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