Коллекции объектов в PHP. Часть вторая

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

    В этом посте вы увидите:
    • Проект и реализацию коллекций объектов в 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.

    HashMap & HashSet

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

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

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

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

    Диаграмма классов HashMap.
    Диаграмма классов HashSet.

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


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

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

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


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


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


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

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

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


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

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

    График:

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

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

    График:

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

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

    График:

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

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

    График:

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


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


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

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

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

    Тест непостоянства 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 оставил ценный комментарий, часть которого я процитирую:

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


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


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

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

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

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

    Причины по которым я отказался от поддержки массивов:
    • «Дорого» по производительности.
    • Мало востребовано.
    • Небезопасно.


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

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

    Заключение


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

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

    Развитие

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

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

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

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

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

    Исходные коды:
    MixedArray
    ObjectArray

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

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


    https://github.com/rmk135/Rmk-Framework

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


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

    Спасибо, что дочитали до конца и извините за обилие графики, я старался размещать ее только там, где необходимо.
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 18

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

      Тут скорее следует говорить об неуникальности хэша и в принципе поведение может неожидаемое, но документированное. Да и проблемой, по-моему, не является — если объект удалён (вернеё перенесен в мусор явно или концом области видимости), а его хэш продолжает использоваться в программе, то это явно ошибка в ней, похожая на ошибку битых указателей в C/C++. Или мне просто не приходит в голову зачем может понадобиться хэш уже недоступного объекта?
        0
        Дело в том, что клиентский код имеет возможность принудительно удалить объект без какой либо обратной связи с коллекцией, в которой хранится «непостоянный» хеш. Первый созданный после удаления объект будет иметь хеш удаленного объекта. При этом поведение коллекции является непредсказуемым.

        Считать ли это проблемой? Пожалуй, нет, если выполнять грамотное удаление объекта и всех ссылок на него, но мир PHP далек от этих проблем. По крайней мере, я редко сталкивался с тем, что что-то где-то нужно подчищать.
          +1
          А можно пример того, как «клиентский код удаляет объект без обратной связи с коллекцией»?
            0
            Да, пожалуйста:
              0
              Ох уж эти горячие клавиши…

              include '../bootstrap.php';
              
              $map = new Rmk\Collection\StringHashTable('stdClass');
              
              $object = new stdClass();
              
              $map->set('key', $object);
              
              var_dump(spl_object_hash($object));
              var_dump($object);
              var_dump($map);
              
              // Где-то в клиентском коде.
              $object = $map->get('key');
              var_dump(spl_object_hash($object));
              
              unset($object);
              
              var_dump($object);
              var_dump($map);
              
              $object = $map->get('key');
              var_dump($object);
              var_dump(spl_object_hash($object));
              


              Написав и запустив этот пример, я понял, что ошибался на счет работы unset(). Получается, что некоторые вещи, которые я написал были чушью.

              Виноват, спасибо.
                +1
                Угу, вопрос был как раз для того, чтобы было понятно почему проблемы нет.
                  0
                  Встречный вопрос:

                  получается, что нет способа удалить переменную и все ссылки на нее, кроме как удалять ссылки в их собственных областях видимости?
                    0
                    Нету, и это, в общем, логично.
                      0
                      Выучите какой-нибудь серьезный язык. Со сборкой мусора. Чтобы демоны на нем не страшно писать было. С историей, серьезным кол-вом разработчиков. Ту же Java, например. Станет лучше как программист, перестанете писать бесполезные велосипеды на PHP, а когда дойдете до статей про организацию памяти, про многопоточность и т.д., поймете что надо заниматься еще и самообразованием, в.т.ч и теоретическим.
                        0
                        Спасибо за совет.

                        Я сомневаюсь, что у меня будет возможность заняться серьезным языком. Я не жалуюсь на работу с текущими технологиями. И ее достаточно много. И, кстати, я считаю ее серьезной.

                        Порядок в мире PHP наведут, и будет это не за горами. Сейчас крупные производители фреймворков (Zend, Symfony) готовят удобные качественные решения, которые позволят подняться на более высокий уровень всем использующим их разработчикам. В некоторых областях определяться лидеры, которые займут свою нишу и вряд ли кому-то ее уступят. Отрасль «зреет».

                        Я не пытаюсь, и никогда не буду, конкурировать с качественными, устоявшимися решениями. И таких как я будет много, когда важные и нужные вопросы безоговорочно решат.

                        Данный проект был попыткой сделать что-то хорошее и высокоуровневое, то, чего я не встречал и с удовольствием бы использовал. Но он провалился по причинам, описанным выше.

                        А заниматься самообразованием конечно же нужно, только вот поможет ли мне глубокое понимание Java в моей работе с PHP? Мне кажется, что есть куда более полезные знания для меня… Например, та же документация по unset().
                          0
                          Простите, это смешно.

                          Я использую в работе Symfony. Версию 2 этого фреймворка видели? Лично у меня ощущение, что пишу на Java только с синтаксисом PHP и с худшим качеством проектирования. Даже не знаю, стоит ли спрашивать поможет ли вам в работе знание языка, где многое, что *сейчас* добавляется в мир PHP, было придумано и реализовано много лет назад.

                          Поможет ли вам знание языка с большей историей, лучше спроектированного, с большим кол-вом качественных библиотек, с большими возможностями? Вы все еще считаете, что нет?

                          Документация по unset — это лишь «как». Для того, чтобы понимать «почему», нужно изучать не PHP.

                          Вы пишите на «языке, который сделали одни дилетанты для других дилетантов»©. Продолжайте и оставайтесь дилетантом — выбор ваш.

                          Хочу заметить, что я не предлагаю отказаться от PHP. Есть области и случаи где его использование действительно будет оправдано. У этого языка есть свои достоинства как с точки зрения синтаксиса, так и с точки зрения того же найма персонала. Но надо четко понимать чем обусловлен выбор, какие плюсы и минусы есть, а не просто верить в волшебную фразу «facebook написан на PHP».
                            0
                            Я не хотел Вас рассмешить, возможно, вы не совсем так меня поняли.

                            Java бесспорно велика. И количеством светлых умов в сообществе, и качеством библиотек и даже синтаксисом. При том не только Java, С#, я, например, тоже очень уважаю. Я понимаю, что у любого умного человека можно многому научиться, и не так важно на каком или на скольких языках он умеет программировать. Дело в том, что ООП != Java; Design Patterns != Java; компонентный подход != Java. Пожалуй, все лучшее, что есть в мире программирования есть и в Java. Давайте разберемся почему так? Я вижу 2 основных критерия: много светлых голов + время. Ту историю, о которой вы говорите создали именно эти 2 фактора. Возможно, я ошибаюсь, поправьте меня.

                            Теперь вернемся к вопросу «нужно ли хорошему (а именно таким я хотел бы быть) PHP программисту изучать Java?».

                            Я считаю, что если есть стремление переходить на Java, то да. Во-первых, любые теоретические познания должны быть хорошо подкреплены практикой для достижения максимального эффекта. Эту практику нужно откуда-то брать и решение университетских задачек или написание калькуляторов (читайте велосипедов) будет слишком малым вкладом. На большее, человек, не имеющий основной работы в данной сфере, не будет способен по чисто экономическим показателям. Кушать то хочется… В итоге изучение конкретного языка, если нет цели переходить на него полностью, я, лично считаю малоэффективным. Я конечно не против иметь интересное хобби, но не более того.

                            Я использую в работе Symfony. Версию 2 этого фреймворка видели? Лично у меня ощущение, что пишу на Java только с синтаксисом PHP и с худшим качеством проектирования. Даже не знаю, стоит ли спрашивать поможет ли вам в работе знание языка, где многое, что *сейчас* добавляется в мир PHP, было придумано и реализовано много лет назад.


                            Да, я смотрел Symfony 2 и даже подумывал начать на нем новый крупный проект, но все же решил дождаться ZF2, так как я ZF Way программист и ZF мне все таки ближе. Других адекватных причин выбора Symfony для себя я не нашел. Функциональная разница, на мой взгляд, между ними ничтожно мала.

                            Опять же, вернемся к нашему вопросу. Есть адекватные причины, по которым Вы работаете с PHP & Symfony. Я уверен, что их достаточно много. Что касается Вашего недовольства Symfony (по сравнению с Java), то сейчас нельзя писать Java Way код на PHP. Нужно все таки писать PHP Way код. Живой пример этому — мой проект, о котором написана эта статья.

                            Вы пишите на «языке, который сделали одни дилетанты для других дилетантов»©. Продолжайте и оставайтесь дилетантом — выбор ваш.


                            Откровенно говоря, я не люблю такие фразы. Уж очень они похожи на:
                            не просто верить в волшебную фразу «facebook написан на PHP».


                            На текущий момент я сделал выбор вкладывать не в конкретные технологии, а в фундаментальные инженерные знания, которые != даже самым развитым технологиям.
          0
          Вообще-то хеш не может и не должен быть «уникальным». Коллизии никто не отменял.
            0
            Если строковый ключ достаточно длинный, скажем 20к символов, то размер потребляемой оперативной памяти массивом вырастает ~ на 70% по сравнению со своим md5 хешированным аналогом. При этом время установки и доступа остается соизмеримым, но, конечно, в пользу «чистого» ключа.
            если ключ больше 64 символов — значить с логикой что-то не так
              0
              Пожалуй, самый главный вопрос, на который нужно дать ответ: «Готовы ли Вы заплатить такую цену по производительности за это решение?».
              НЕТ
                +1
                Я уверен, что никто не готов. И я в том числе.
                0
                В какой программе UML диаграграммы рисовали? это автоматизированный способ (имя код — программа собрала диаграмму, или руками?
                  +1
                  Enterprise Architect

                  Все работы выполнялись вручную.

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

                  Only users with full accounts can post comments. Log in, please.