- PVSM.RU - https://www.pvsm.ru -
PHP имеет всего одну структуру данных для управления всем. array
— сложный, гибкий, гибридный, сочетает в себе поведение list
и linked map
. Но мы используем его для всего, потому что PHP придерживается прагматичного подхода: иметь предельно правильный, здравый и реалистичный способ решения проблемы, исходящий из практических, а не теоретических рассуждений. array
позволяет делать работу, хотя о нем и так много рассказывают на лекциях по информатике. Но, к сожалению, с гибкостью приходит и сложность.
Последний релиз PHP вызвал большое оживление в сообществе. Мы не могли дождаться того, чтобы начать использовать новые возможности [1] и почувствовать вкус ~2х прироста производительности [2]. Одна из причин, почему это случилось — структура array
была переработана [3]. Но массивы все также придерживаются принципа «оптимизировано для всего; оптимизировано для ничего», еще не все идеально, есть возможности для совершенствования.
А что насчет структур данных SPL? [4]
К сожалению… они ужасны. Раньше, до PHP7, они предлагали _некоторые_ преимущества, но сейчас мы дошли до точки, когда использование SPL не имеет практического смысла.
Почему мы не можем просто поправить и улучшить их?
Да, мы могли бы, но я считаю, что их дизайн и реализация настолько бедны, что лучше бы найти более современную замену.
«SPL data structures are horribly designed.»
— Anthony Ferrara
php-ds
— расширение для PHP7, добавляющее структуры данных. Этот пост кратко охватывает поведение, производительность и преимущества каждой из них. Также в конце вы найдете список ответов на ожидаемые вопросы.
Github: https://github.com/php-ds [5]
Пространство имен: Ds
Интерфейсы: Collection
, Sequence
, Hashable
Классы: Vector
, Deque
, Stack
, Queue
, PriorityQueue
, Map
, Set
Collection
— это базовый интерфейс, охватывающий общую функциональность: foreach
, echo
, count
, print_r
, var_dump
, serialize
, json_encode
, и clone
.
Sequence
описывает поведение элементов, организованных в единый, линейный размер. В некоторых языках такая структура назвается List
(список). Подобен array
, который использует инкрементальные ключи, за исключением некоторых особенностей:
[0, 1, 2, …, size - 1]
[0, size - 1]
array
как список (без ключей)SplDoublyLinkedList
и SplFixedArray
Vector
представляет собой Sequence
, объединяющую значения в непрерывный буфер, увеличивающийся и уменьшающийся автоматически. Это наиболее эффективная последовательная структура данных, поскольку индекс элемента является прямым отражением его индекса в буфере, и увеличение вектора никак не повлияет на производительность.
get
, set
, push
и pop
имеют сложность O(1)
insert
, remove
, shift
and unshift
имеют сложность O(n)
Структурой номер один в Photoshop были Вектора.
— Sean Parent, CppCon 2015 [6]
Deque
(произносится как «deck») — это последовательность значений, объединенных в непрерывный буфер, увеличивающийся и уменьшающийся автоматически. Название является общепринятым сокращением от «double-ended queue». Используется внутри DsQueue
.
Два указателя используется для отслеживания головы и хвоста. Наличие указателей позволяет изменять конец и начало буфера без необходимости перемещать другие элементы для освобождения места. Это делает shift
и unshift
настолько быстрым, что даже Vector
не может конкурировать с этим.
Доступ к значению по индексу требует вычисления соответствующей позиции в буфере: ((head + position) % capacity)
.
get
, set
, push
, pop
, shift
и unshift
имеют сложность O(1)
insert
, remove
имеют сложность O(n)
2ⁿ
)
Следующий бенчмарк показывает общее затраченное время и память, используемую для операции push
2ⁿ случайных чисел. array
, DsVector
и DsDeque
отрабатывают быстро, но SplDoublyLinkedList
стабильно показывает результат более чем в 2 раза хуже.
SplDoublyLinkedList
выделяет память для каждого значения по отдельности, поэтому и происходит ожидаемый рост по памяти. array
и DsDeque
при своей реализации выделяют память порционно для поддержания достаточного объема для 2ⁿ элементов. DsVector
имеет фактор роста 1.5, что влечет за собой увеличение количества выделений памяти, но меньший расход в целом.
Следующий бенчмарк показывает время, затраченное на unshift
единственного элемента в последовательности значений размером 2ⁿ. Время, требующееся на установку значений не учитывается.
На графике видно, что array_unshift
имеет сложность O(n)
: всякий раз, когда объем выборки удваивается, растет и время, необходимое для unshift
. Это объясняется тем, что каждый числовой показатель в диапазоне [1, size - 1]
должен быть обновлен.
Но и DsVector::unshift
также O(n)
, так почему же он намного быстрее? Имейте ввиду, что array
хранит каждое значение в bucket
вместе с его ключем и хэшем. Поэтому приходится проверять каждый элемент и обновлять хэш, если индекс является числовым. На самом деле array_unshift
выделяет новый массив для этого и заменяет старый, когда все значения скопированы.
В векторе же индекс значения — это прямое отображение его индекса в буфере, поэтому все, что нам нужно сделать — сдвинуть каждое значение в диапазоне [1, size — 1] вправо на одну позицию. Делается это при помощи всего одной операции memmove
.
DsDeque
и SplDoublyLinkedList
в свою очередь очень быстры, потому что на время для unshift
значения не влияет размер выборки, т.е. его сложность будет O(1)
.
На следующем тесте видно сколько памяти используется при 2ⁿ pop
операций. Другими словами при изменении размера от 2ⁿ до нуля
Интересно тут то, что array
всегда держит выделенную память, даже если его размер существенно уменьшается. DsVector
and DsDeque
позволяют в два раза уменьшить выделяемые ресурсы, если их размер падает ниже четверти своего текущего потенциала. SplDoublyLinkedList
освобождает память после каждого удаления из выборки, поэтому мы можем наблюдать линейное снижение.
Стек [7] — является коллекцией, организованной по принципу «последним пришёл — первым вышел» или «LIFO» (last in — first out), позволяющей получить доступ только к значению на вершине структуры. Вы можете думать о нем как об оружейном магазине [8] с динамической емкостью.
DsStack
использует внутри себя DsVector
.
SplStack
наследуется от SplDoublyLinkedList, поэтому производительность будет эквивалентна сравнению DsVector
to SplDoublyLinkedList
из предыдущих тестов. Посмотрим на время, необходимое для выполнения 2ⁿ pop
-операций, изменения размера от 2ⁿ до нуля.
Очередь [9] — тип данных с парадигмой доступа к элементам «первый пришел — первый вышел» («FIFO», «First In — First Out»). Такая коллекция позволяет получить доступ к элементам в порядке их добавления. Ее название говорит само за себя, представьте себе структуру как линию людей, стоящих в очереди на кассу в магазине.
DsQueue
использует внутри себя DsDeque
. SplQueue
наследуется от SplDoublyLinkedList
, поэтому производительность будет эквивалентна сравнению DsDeque
с SplDoublyLinkedList
, показанному в предыдущем бенчмарке.
Очередь с приоритетом очень похожа на простую очередь. Элементы помещаются в очередь с указанным приоритетом и значение с наивысшим приоритетом всегда будет в передней части. Прямой перебор очереди с приоритетом очень деструктивен, это будет последовательный вызов операций pop
, что является очень затратной операцией.
Реализация очереди с приоритетом использует max-heap.
Принцип «первый пришел — первый вышел» сохраняется для значений с одинаковым приоритетом, так что группа значений с равным приоритетом можно рассматривать как обычную очередь.
А что же с производительностью? Следующий бенчмарк показывает время и память, требующиеся для операции push
2ⁿ случайных чисел со случайным приоритетом в очередь. Те же случайные числа будут использоваться для каждого из тестов. В тесте для Queue
также генерируется случайный приоритет, хотя он и не используется.
Это, наверное, самый значимый из всех бенчмарков. DsPriorityQueue
работает более чем в два раза быстрее чем SplPriorityQueue
и использует только 5% от его памяти — это в 20 раз более эффективное решение по памяти.
Но как? Как может получиться настолько большая разница, когда SplPriorityQueue
использует аналогичную внутреннюю структуру? Все сводится к тому, как хранятся значения в паре с приоритетом. SplPriorityQueue
позволяет использовать любой тип значения для использования в качестве переменной, это приводит к тому, что в каждой паре приоритет занимает 32 байта.
DsPriorityQueue
поддерживает только целочисленные приоритеты, поэтому каждой паре выделяется 24 байта. Но это все еще недостаточная разница для объяснения результата.
Если вы посмотрите на исходный код SplPriorityQueue::insert
[10], то заметите, что он инициализирует массив для хранения пары значение-приоритет.
Т.к. массив имеет минимальную емкость 8, то для каждой пары на самом деле выделяется zval + HashTable + 8 * (Bucket + hash) + 2 * zend_string + (8 + 16) byte string payloads
= 16 + 56 + 36 * 8 + 2 * 24 + 8 + 16
= 432 байта (64 бит).
SplPriorityQueue
использует ту же внутреннюю структуру SplMaxHeap
, которая требует от значения быть типом zval
. Очевидный (но неэффективный) способ создания zval
-пары, т.к. zval
сам используется как array
.
Интерфейс, позволяющий объектам быть использованными в качестве ключей. Это альтернатива spl_object_hash
, который детерминирует объект в хэш, базирующийся на его handle:
. Это означает, что два объекта, которые считались бы равными при сравнении, не имели бы равный хэш, т.к. они не являются одним и тем же экземпляром.
Hashable
вводит только два метода: hash
и equals
. Многие другие языки поддерживают это изначально: в Java — hashCode
и equals
, или в Python ___hash___
и __eq__
. Было несколько RFC, добавляющих подобное поведение и в PHP, но ни один из не был принят.
Все структуры, будут возвращать spl_object_hash
, если ключи объектов, хранящиеся в них не реализуют в себе Hashable
.
Структуры данных, работающие с интерфейсом Hashable
: Map
и Set
.
Map
является последовательной коллекцией пар ключ-значение, практически идентичной array
в аналогичном контексте. Ключи могут быть любого типа, единственное условие — уникальность. При повторном добавлении ключа значения заменяются.
Как и в array
, порядок вставки сохраняется.
array
Hashable
put
, get
, remove
и containsKey
имеют сложность O(1)
array
при наличии ключей-объектов
Следующий бенчмарк показывает, что производительности и эффективности по памяти между array
и DsMap
идентичны. Однако, array
всегда будет держать выделенную память, когда DsMap
, в свою очередь, освободит память при падении размера ниже четверти своего потенциала.
Set
— коллекция уникальных значений. Учебники скажут вам, что в структуре Set
значения неупорядочены, если реализация не предусматривает иное. Возьмем для примера Java, java.util.Set
— это интерфейс с двумя основными реализациями: HashSet
и TreeSet
. HashSet
обеспечивает сложность O(1)
для add
и remove
, a TreeSet
обеспечивает сортированный набор данных, но сложность add
и remove
возрастает до O(log n)
.
Set
использует ту же внутреннюю структуру, что и Map
, также основываясь на array
. Это означает, что Set
может быть отсортирован за время O(n * log(n))
когда это понадобится, в остальном он такой же простой как Map
и array
.
add
, remove
и contains
имеют сложность O(1)
Hashable
SplObjectStorage
поддерживает только объекты).intersection
, difference
, union
, exclusive or
)push
, pop
, insert
, shift
или unshift
get
имеет сложность O(n)
если есть удаленные значения до момента индексации, в ином случае — O(1)
Следующий бенчмарк показывает время, затраченное на добавление 2ⁿ новых экземпляров stdClass
. Он показывает, что DsSet
немного быстрее, чем SplObjectStorage
, и использует примерно в половину меньше памяти.
Распространенным способом создания массива с уникальными значениями является array_unique
, который создает новый array
, содержащий только уникальные значения. Но важно иметь ввиду, что значения в массиве не индексируются, in_array
является линейным поиском со сложность O(n)
. array_unique
работает только со значениями, без учета ключей, каждая проверка на наличие значения массива — линейный поиск, что даем нам в сумме сложность O(n²)
по времени и O(n)
по потреблению памяти.
Сейчас около 2600 тестов. Вполне возможно, что некоторые тесты являются избыточными, но я предпочел бы косвенно проверить одну и ту же вещь дважды, чем не проверять совсем.
На момент написания этой статьи пока еще нет полной документации, но она появится вместе с первым стабильным релизом.
Однако, существуют некоторые хорошо документированные файлы-заглушки [11].
Все бенчмарки прогонялись на стандартном билде PHP 7.0.3
на 2015 Macbook Pro. Результаты могут отличаться в зависимости от версии и платформы.
Stack
, Queue
, Set
и Map
— не интерфейсы?Я не верю, что есть необходимость в какой-либо альтернативной реализации. 3 интерфейса и 7 классов — это хороший баланс между прагматизмом и специализацией.
Deque
вместо Vector
?
Если вы точно знаете, что не будете использовать shift
и unshift
, используйте Vector
. Для удобного тайпхинтинга можно указать в качестве типа Sequence
.
Дизайн API php-ds
применяет парадигму «Composition over inheritance [12].
Структуры SPL являются хорошим примером того, как наследование может быть использовано не по назначение. Например, SplStack
расширяет SplDoublyLinkedList
, который поддерживает произвольный доступ по индексу, shift
и unshift
— так что технически это не Стек [7].
Фреймворк Java-коллекций также имеет несколько интересных случаев, когда наследование порождает двусмысленность. ArrayDeque
имеет три метода добавления элементов: add
, addLast
и push
. Это не плохо, т.к. ArrayDeque
имплементирует Deque
и Queue
, что объясняет одновременное наличие addLast
и push
. Однако, все три метода сразу, делающие одно и тоже, вызывают путаницу и непоследовательность.
Старый java.util.Stack
расширял java.util.Vector
, тем самым заявляя, что „более полный и последовательный набор операций LIFO обеспечивается интерфейсом Deque
и его реализациями“, но Deque
включает в себя методы addFirst
и remove(x)
, которые не должны быть часть stack
структуры по API.
На самом деле, это справедливое замечание, но я по-прежнему считаю, что композиция больше подходит для построения структур данных. Они предназначены быть самодостаточными, подобно array
. Вы не можете отнаследоваться от array
, он вынуждает вас разрабатывать собственные API вокруг себя, используя его только для хранения фактических данных.
Наследование также вызвало бы лишние сложности во внутренней реализации.
ds
класс в глобальном пространстве имен?
Он обеспечивает альтернативный синтаксис:
Класс LinkedList
на самом деле появился первым, это казалось хорошим стартом. Но в итоге я решил удалить его, когда понял, что он не сможет конкурировать с Vector
или Deque
при любом раскладе. Две основные причины возможной поддержки: распределение накладных расходов и локальность ссылок.
В связном списке мы добавляем или убираем зарезервированную память для элемента структуры (node) всякий раз, когда значение добавляется или удаляется. Нода содержит в себе два указателя (в случае с двусвязным списком), чтобы ссылаться на предыдущую и последующую ноды. Обе структуры, Vector
и Deque
, выделяют буфер памяти заранее, поэтому нет необходимости делать это настолько часто. Они также не нуждаются в дополнительных указателях, чтобы знать какое значение до и какое после, тем самым снижаются накладные расходы.
Только когда коллекция очень мала. Верхней границей количества памяти для Vector
будет (1.5 * (size - 1)) * zval
байт, не менее *10 * zval*. В двусвязном списке же будет использоваться (size * (zval + 8 + 8))
. Поэтому связный список будет использовать меньше памяти, чем Vector
только тогда, когда его размер меньше 6 элементов.
Узлы связного списка обладают плохой пространственной локальность. Это означает, что физическое расположение узла в памяти может быть далеко от прилегающих узлов. Таким образом итерации по связному списку скачут по памяти вместо использования кэша процессора. Значительное преимущество Vector
и Deque
: элементы физически находятся рядом друг с другом.
»Несмежность данных в структурах является корнем всех зол производительности. Конкретно, пожалуйста, скажите нет связным спискам"
«Нет почти ничего вреднее из того что вы можете сделать чтобы убить все плюсы современных микропроцессоров, чем использовать связный список»
— Chandler Carruth (CppCon 2014 [13])
Производительность не должна быть вашим главным приоритетом. Код должен быть последовательным, ремонтопригодным, надежным, предсказуемым, безопасным и легко понимаемым. Но это не означает, что производительность «не важна».
Мы тратим много времени, пытаясь уменьшить размер своих ассетов, делаем сравнительный анализ фреймворков и придумываем бессмысленные микро-оптимизации:
Но в конечном итоге двухкратный прирост производительности, который приносит с собой PHP7 почему-то всех взбудоражил. Абсолютно для всех это — одно из главных преимуществ для перехода с PHP5.
Эффективный код позволяет снизить нагрузку на наши сервера. уменьшить время ответа наших API и веб-страниц и снижает время работы наших утилит для разработки. Высокая производительность важна, но поддерживаемость кода все же стоит во главе.
Автор: iGusev
Источник [22]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/struktury-danny-h/116339
Ссылки в тексте:
[1] новые возможности: http://php.net/manual/en/migration70.new-features.php
[2] ~2х прироста производительности: https://www.reddit.com/r/PHP/comments/3q2brz/how_is_php_7_twice_as_fast/
[3] структура array
была переработана: https://nikic.github.io/2014/12/22/PHPs-new-hashtable-implementation.html
[4] структур данных SPL?: http://php.net/manual/en/spl.datastructures.php
[5] https://github.com/php-ds: https://github.com/php-ds
[6] CppCon 2015: https://youtu.be/sWgDk-o-6ZE?t=21m52s
[7] Стек: https://ru.wikipedia.org/wiki/%D0%A1%D1%82%D0%B5%D0%BA
[8] оружейном магазине: https://upload.wikimedia.org/wikipedia/commons/6/6c/Single_row_box_magazine.svg
[9] Очередь: https://ru.wikipedia.org/wiki/Очередь_(программирование)
[10] исходный код SplPriorityQueue::insert
: http://lxr.php.net/xref/PHP_7_0/ext/spl/spl_heap.c#629
[11] хорошо документированные файлы-заглушки: https://github.com/php-ds/ds/tree/master/php/include
[12] «Composition over inheritance: https://en.wikipedia.org/wiki/Composition_over_inheritance
[13] CppCon 2014: https://youtu.be/fHNmRkzxHWs?t=34m42s
[14] print vs echo, which one is faster?: http://fabien.potencier.org/print-vs-echo-which-one-is-faster.html
[15] The PHP Ternary Operator: Fast or not?: http://fabien.potencier.org/the-php-ternary-operator-fast-or-not.html
[16] The PHP Benchmark: setting the record straight: http://www.phpbench.com/
[17] Disproving the Single Quotes Performance Myth: https://nikic.github.io/2012/01/09/Disproving-the-Single-Quotes-Performance-Myth.html
[18] Twitter: https://twitter.com/rudi_theunissen
[19] Reddit: https://www.reddit.com/r/PHP/comments/44qsco/efficient_data_structures_for_php_7/
[20] Room 11: http://chat.stackoverflow.com/rooms/11/php
[21] github.com/php-ds/benchmarks: https://github.com/php-ds/benchmarks
[22] Источник: https://habrahabr.ru/post/280262/
Нажмите здесь для печати.