Прошло почти 3 недели с момента публикации моего первого поста о коллекциях объектов в PHP ^[1]. За это время было сделано много работы и получено много опыта, которым я хочу поделиться. Наибольшее количество изменений претерпели карты, большая часть внимания будет уделена именно им.

В этом посте вы увидите:

• Проект и реализацию коллекций объектов в PHP.
• Тесты производительности.
• Впечатления о написании первых Unit тестов.
• Интересную информацию о работе с множествами объектов PHP.

Что было сделано?

После публикации моего прошлого поста и окончания его обсуждения, я составил план дальнейшего развития:

• Реализация возможности итерации коллекций с помощью foreach().
• Специализации основных реализаций коллекций для более удобного использования.
• Создание новой реализации интерфейса карты на основе единственного PHP массива.
• Усовершенствование алгоритмов хеширования.
• Отказ от некоторых типов данных для карт. Финальный список поддерживаемых типов выглядит так: int, string, object.
• Тестирование функциональности.
• Тестирование производительности.

Кроме вышеуказанного списка были еще кандидаты, которые не вошли в план текущего релиза:

• Функции фильтрации и сортировки.
• Утилитарные функции коллекций.

Интерфейсы коллекций

Разработанные ранее интерфейсы коллекций отреагировали достаточно стабильно на новый план развития. Диаграмма интерфейсов текущей версии выглядит так:

Как видно из диаграммы все интерфейсы коллекций наследуют интерфейс IteratorAggregate, что дает возможность выполнять обход коллекций с помощью foreach(). Проблема с warning, который выскакивает при обработке карт <объект — объект> с помощью foreach() все еще осталась, но по скольку такие ситуации действительно бывают редко, я решил закрыть на это глаза.

Реализации карт

Карты представлены реализациями HashMap, HashSet и HashTable. Каждая из данных реализаций имеет собственные специализации для упрощенного использования.

HashTable

Внутренняя структура карты HashTable построена на основе единственного PHP массива. Это дает возможность быстрой работы по ключу O(1), но плохо влияет на возможность работы по значению, которая выполняется обычным перебором O(n).

Ключи карты HashTable являются уникальными. Значения карты HashTable не являются уникальными, что позволяет ассоциировать одно значение с несколькими ключами.

Карта HashTable поддерживает строки и целые числа для ключей и строки, целые числа и объекты для значений.

Хеширование ключей и значений не выполняется. Методы getKeyHash() и getValueHash() выбрасывают исключение.

Диаграмма классов HashTable. ^[2]

HashMap & HashSet

Внутренняя структура карт HashMap и HashSet построена на основе сети ассоциативных связей. Это дает возможность реализовывать все операции карт с помощью ассоциативных выборок. Сложность работы алгоритмов карт равна O(1), что означает, что время установки/получения объектов не изменяется в зависимости от размера карт.

Ключи карты HashMap являются уникальными. Значения карты HashMap не являются уникальными, что позволяет ассоциировать одно значение с несколькими ключами.

Ключи и значения карты HashSet являются уникальными, что позволяет организовывать хранилище уникальных ассоциаций.

Карты HashMap и HashSet поддерживают строки, целые числа и объекты для ключей и значений.

Диаграмма классов HashMap. ^[3]
Диаграмма классов HashSet. ^[4]

Реализации наборов, списков и очередей

Реализация наборов претерпела некоторые косметические изменения и обросла специализациями для упрощенного использования.
Диаграмма классов наборов. ^[5]

Реализации списков и очередей остались практически без изменений.
Диаграмма классов списков и очередей. ^[6]

Тестирование функциональности

Весь представленный код покрыт PHPUnit ^[7] тестами.
Это были мои первые Unit тесты и я очень доволен полученным опытом. Данный вид тестирования позволил отловить мне порядка десяти опечаток и одну фундаментальную ошибку, для фиксации которой пришлось менять реализацию.
Хочется отметить три вещи:

1. Если вы еще не используйте Unit тесты, то начинайте прямо сейчас. Лично у меня произошла интересная ситуация: я породил достаточно много кода, который приходилось и приходится поддерживать, освоил много всяких приемчиков, которые должны были помогать это делать, но не написал ни одного Unit теста. Почему? — Просто боялся начать. Только сейчас я понял, что моя жизнь могла быть гораздо легче.
2. Написав первые несколько тестов я понял, что внутри большой неизведанный (для меня) мир. Из всего разнообразия assert*, я использовал только несколько. Код тестов часто был не эффективным и дублировался. Бегло просмотрев документацию по PHPUnit ^[8], я понял, что тесты могут быть гораздо лучше, чем те, что создал я.
3. Unit тесты не лечат от всех болезней. Мы можем протестировать метод, всю логику внутри него, мы даже имеем удобную платформу для того, чтобы тестировать определенные небольшие сценарии, но не стоит забывать и про другие методы тестирования. Из того, что можно достойно автоматизировать, я бы выбрал Behavior тесты в качестве дополнительного варианта тестирования.

Тестирование производительности

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

Объекты тестирования:

• Обычный PHP массив.
• SPL реализация массива ArrayObject ^[9].
• Реализация карты HashTable.
• Реализация карты HashSet.
• Реализация карты HashMap.

Критерии тестирования:

• Среднее время установки пары ключ / значение.
• Среднее время выборки значения по ключу.
• Среднее время выборки ключа по значению.
• Объем потребляемой оперативной памяти.

Платформу тестирования детально описывать не буду, так как не вижу в этом особого смысла. Дело в том, что данные тесты не предназначены для определения количественных характеристик, а скорее для демонстрации соотношений. Соотношения результатов тестов практически не менялись ни на разном железе, ни на разных операционных системах.
Результаты тестов в этом посте я снимал со своего ноутбука на Windows Vista 32 bit.

Тестирование времени установки пары ключ / значение

График:

Файлы тестов:

• Тест обычного PHP массива ^[10]
• Тест ArrayObject ^[11]
• Тест HashTable ^[12]
• Тест HashSet ^[13]
• Тест HashMap ^[14]

Тестирование времени выборки значения по ключу

График:

Файлы тестов:

• Тест обычного PHP массива ^[15]
• Тест ArrayObject ^[16]
• Тест HashTable ^[17]
• Тест HashSet ^[18]
• Тест HashMap ^[19]

Тестирование времени выборки ключа по значению

График:

Файлы тестов:

• Тест обычного PHP массива ^[20]
• Тест ArrayObject ^[21]
• Тест HashTable ^[22]
• Тест HashSet ^[23]
• Тест HashMap ^[24]

Тестирование объема потребляемой оперативной памяти

График:

Файлы тестов:

• Тест обычного PHP массива ^[25]
• Тест ArrayObject ^[26]
• Тест HashTable ^[27]
• Тест HashSet ^[28]
• Тест HashMap ^[29]

Некоторые интересные факты

В процессе работы всплыли некоторые интересные факты, которыми хочется поделиться.

Непостоянство spl_object_hash()

Думаю, многим знакома функция spl_object_hash() ^[30].
Оказывается у нее есть одна, на мой взгляд, не очень хорошая особенность — непостоянство хешей.

Тест непостоянства spl_object_hast():

<?php
$object1 = new stdClass();
$hash1   = spl_object_hash($object1);

unset($object1);

$object2 = new stdClass();
$hash2   = spl_object_hash($object2);

var_dump($hash1);
var_dump($hash2);
var_dump($hash1 === $hash2);

//string '000000004974d03c000000005560c408' (length=32)
//string '000000004974d03c000000005560c408' (length=32)
//boolean true

Что из этого следует и почему данная особенность неприятна?

• Нельзя опираться на spl_object_hash(), как на уникальный идентификатор объекта даже в рамках процесса.
• Нельзя сериализовывать никакие структуры данных, которые хранят хеши spl_object_hash(), без обновления хешей при десериализации.

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

Внутреннее хеширование ключей массивов

В комментариях к моему прошлому посту пользователь Athari ^[31] оставил ценный комментарий, часть которого я процитирую:

Зачем для строк вычислять md5? Похапэшные массивы — и так хэштаблицы, не нужно вычислять хэши на двух уровнях. Только память и вычислительные ресурсы впустую расходуются.

В этом действительно большая доля смысла, но все же я решил проверить.
Результаты:

• Если строковый ключ небольшой, скажем 100 символов, то вычисление его md5 хеша действительно только расходует ресурсы.
• Если строковый ключ достаточно длинный, скажем 20к символов, то размер потребляемой оперативной памяти массивом вырастает ~ на 70% по сравнению со своим md5 хешированным аналогом. При этом время установки и доступа остается соизмеримым, но, конечно, в пользу «чистого» ключа.

Хеширование массивов

Все тот же пользователь Athari ^[31] оставил еще один дельный комментарий к прошлому посту:

Вызов serialize забавен. Понимаю, «нужно» все типы поддерживать, но не такой же ценой.

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

Действительно «дорогая» цена. В текущей реализации я вообще отказался от поддержки массивов в качестве ключей карты.

Причины по которым я отказался от поддержки массивов:

• «Дорого» по производительности.
• Мало востребовано.
• Небезопасно.

Особенно хочется остановить на пункте «Небезопасно.» Дело в отсутствие обратной связи между данными и хешем (как бы «дорого» мы его не получили). Если клиентский код сохранит ссылку на массив, который мы захешировали, и изменит его, то хеш устареет. Получить информацию о том, что это тот же массив возможности уже не будет. Тоже самое относится и к другим скалярным типам данных.

Есть ли выход? Единственное, что приходит на ум, это использовать массив через объект обертку (ArrayObject, etc...). В таком случае можно хотя бы получить «непостоянный» spl_object_hash().

Заключение

Пожалуй, самый главный вопрос, на который нужно дать ответ: «Готовы ли Вы заплатить такую цену по производительности за это решение?». Я уверен, что никто не готов. И я в том числе. Когда я создал графики результатов тестирования производительности, я был удивлен. Я ожидал гораздо меньших соотношений по сравнению со стандартными реализациями, хотя прекрасно понимал, что данное решение явно проигрывает в этом аспекте. Я сперва даже пытался найти решение проблем, но, увы, ничего не вышло. Основная проблема заключается в том, что даже вызов метода является «дорогой» операцией в этом случае. Что касается объема потребляемой оперативной памяти, то до сих пор не пойму, на что расходуется столько ресурсов. Единственное полезное новшество — это двустороннее хеширование карты, что дает возможность выбирать из нее по значению в рамках O(1).

В целом, считаю, что данный проект потерпел фиаско, и причиной этому является аспект производительности.

Развитие

Исходя из моей аналитики подобное решение все же появится со временем. Лучшее место для него — пакет SPL ^[32]. Может быть это будет и не SPL, а какой-то другой PECL модуль, который со временем войдет в стандартную сборку PHP. В любом случае что-то удовлетворительное или хорошее получится только при грамотной реализации на С. Кстати, если кто-то заинтересовался данным проектом и хочет помочь реализовать его в качестве PECL модуля, буду рад сотрудничеству.

Что делать дальше?

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

Лично я решил создать более легковесные реализации, которые просто будут немного помогать в повседневной жизни и не будут чем-то большим, чем есть стандартные PHP массивы. Уже сейчас есть некоторые наброски:

Диаграмма классов:
MixedArray & ObjectArray UML Diagram ^[33]

Исходные коды:
MixedArray ^[34]
ObjectArray ^[35]

Если это кому-то интересно, пишите, я расскажу о идее более детально.

Исходные коды

https://github.com/rmk135/Rmk-Framework ^[36]

Благодарности

Благодарю всех за конструктивные комментарии к прошлому посту. Они были очень полезны. Рад буду услышать Ваше мнение еще раз.

Спасибо, что дочитали до конца и извините за обилие графики, я старался размещать ее только там, где необходимо.

Автор: rmk