Низкоуровневая реализация префиксного дерева trie на PHP

[johovich]

А какой смысл? Короче просто бинарного файла все равно не будет. Насколько я знаю, messagePack даёт возможность сериализации, но никакой новой структуры данных не даёт.

[johovich]

Если что-то готовое брать. Наверное лучше всего будет взять что-то типа структуры vector из проекта php-ds. Недавно натолкнулся, очень перспективно выглядит, там через php расширение, поэтому скорость, как у ракеты.

[johovich]

Мы о разных вещах говорим видимо. В каком качестве ты предлагаешь использовать msgpack? Насколько я знаком с msgpack, он позволяет сериализовывать примитивные типы и массивы. Проще говоря, этакий json или serialize только быстрее. Главная проблема в PHP не в хранении, с хранением вполне успешно справляется serialize/unserialize json encode/decode или var_export/eval, есть из чего выбрать. Главная проблема в отсутствии структур для эффективной работы с большими данными. Как тут msgpack поможет?

[johovich]

Я совсем не против msgpack и даже использую его для хранения файлового кеша. Если его можно использовать и в каком-то другом качестве — отлично. Но я так и не понял, что он будет делать в trie. У меня сейчас словарь записан в виде строки бинарных данных, если получится сделать компактнее, чем 154 байт на узел — это все равно будет строка бинарных данных, которая в ходе работы программы не становится массивом или объектом. Вот есть сущность словаря — узел, который состоит из маски и ссылок, которые просты куски по 3 байта. Что может msgpack? Сохранить на диск? Ок. А дальше? msgpack_unpack() даёт мне массив на 2гб? Или он может какой-то свой объект для хранения предложить? Эффективность — когда для хранения 10 байт я трачу 15. У меня сейчас неэффективно, потому что 400байт на 1 слово, весь словарь 150мб, но если я беру массив, то там ещё хуже с эффективностью.

[Deosis]

Можно вместо 46 указателей хранить 1 указатель и все дочерние записи располагать подряд.
Выигрыш будет тем больше, чем полнее дерево.
ПС. Посчитал, выигрыш по памяти будет, даже если у родителя только 2 ребенка.

[johovich]

Да, отличная идея. Но места резервировать под всех возможных детей? Как бы этого не делать?

[johovich]

Реплицировать, добавлять новых детей и писать в конец? А как же быть с теми узлами, которые на него ссылаются? Сейчас связь односторонняя. Родители знают своих детей, но не наоборот. Что бы с этим придумать.

[Yeah]

А теперь переписать это все на zephir и скомпилить в виде расширения. Интересно, на сколько выростет скорость?

[acdee]

По битовое смещение не должно «вау» как прибавить в скорости, но так или иначе ускорение ожидаемо. Хотя по мне так и не велико.

[johovich]

Вау или не вау, но побайтовая распаковка со смещением и последующим сложением делает на 10% быстрее, чем unpack('P'). А вот substr(pack('P'),0,6) на полпроцента, но быстрее связки chr($int). chr($int >> 8) ....

[mcferden]

Не силен в PHP, хотелось бы прояснить 2 момента:
1) Правильно ли я понимаю, что узлы хранятся в одном непрерывном блоке памяти? Тогда получается, что при вставке нового узла из-за добавления ссылки придется двигать какую-то часть этого блока?
2) Не совсем понятно, как работают ссылки через смещения. Опять же, узлы же должны двигаться?

[johovich]

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

Но вот сейчас начал пробовать по схеме с переменной длиной узла, когда свободного места не будет на всех детей. Сразу застрял. Как раз проблема с тем, что придётся менять адреса у других узлов, мало того, что это долго, так ещё непонятно как узнать кто является родителем узла.

[johovich]

Ссылки сейчас даже без смещения. Само смещение вычисляется из ссылки. Вот к примеру нужен узел с индексом 121. Считаем его смещение: offset = 121 * 154

[johovich]

Люди, кто в Си шарит, можете посмотреть как хранится узел и ссылки в этой сишной реализации? github.com/Ethiraric/libTrie

[avallac]

Из статьи совершенно непонятно, что есть ключевой характеристикой данного решения(скорость/объем/простота реализации). Это важно, потому, что они взаимоисключающие. А тут получается и не то и не се. Основной мой язык программирования PHP, но для данной задачи он подходит слабо. Я сам не так давно делал многопотоковый неблокирующий индекс на основе сжатого префиксного дерева. Реализовал на С с pthread. Так как у меня ключевая метрика это объем памяти, то ноды переменной длины и проблемы с фрагментацией в комплекте. И да, индекс занимают в 3 раза меньший объем чем исходные данные. Дедупликация данных это основная фишка префиксного дерева.

[johovich]

В данной версии — скорость и простота. Сейчас переделываю немного, скорость будет чуть ниже, сложность чуть выше, а памяти будет жрать где-то в 13 раз меньше.

[avallac]

Если нужна скорость, пишите на чем-то более низкоуровневом, например на С. Это не так сложно и страшного в этом ничего нет. Заодно будет очень серьезный выигрыш по памяти. Можно реализовать экстеншин к PHP, а можно сделать сетевое хранилище.

[johovich]

Надеюсь сумею переписать после на Си, если хорошо заработает. А эту либу оставлю как полифил.

[avallac]

Пишите сразу. Это будет гораздо полезнее.

[johovich]

попробую теперь переписать. Закончил версию 0.1.0. Теперь узлы отделены от ссылок. Каждый узел 6 байт маска + 3 байта ссылка на блок ссылок. Сами ссылки на детей этого узла занимают места столько, сколько этих детей существует, по 3 байта каждый ребенок.
Но скорость снизилась слишком сильно. 42.5 тыс. слов в секунду при поиске. Надо теперь точно сделать на Си. Что посоветуешь посмотреть по части Си расширений для PHP?

[avallac]

Мой выбор было сделать полноценный сервис к которому PHP ходит по TCP. Потому, что я сразу делал с оглядкой на кластеризацию (Уже сейчас у меня 3 сервера суммарно с 400 GB ОЗУ) Так что по написанию модулей тебе не подскажу.