On Tue, Oct 28, 2008 at 12:31:35PM +0600, Mikhail Gusarov wrote:
>  AT> Trie лишь оптимизирует *доступ* к contents_index (переходы типа
>  AT> многоуровнего хеша); а с точки зрения размера выгоднее
>  AT> contents_index просто сжать.
> 
> Конечно, но trie заодно уберёт огромную избыточность текущего
> contents_index. Впрочем, сжать проще.

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

>  AT> Значит, нужна нетривиальная логика сериализации trie, которая бы
>  AT> оптимизировала локальность ссылок при переходе вглубь trie на
>  AT> физических страницах.
> 
> Любая сериализация trie будет лучше, чем grep по файлу :)

С точки зрения доступа сериализации должна давать минимальное количество
page faults [*].  То есть, примерно, чтобы переход / -> /usr затрагивал
всего одну 4K страницу (которую необходимо загрузить в память с диска),
переход /usr -> /usr/share затрагивал всего одну 4K страницу и т.д.

Если на одной странице оказываются unrelated пути (напр. /usr и /etc),
то мы лишь избавляемся от лишних вызовов типа regexec(3) (как в grep),
но не можем ограничить активность ОС (ограничить фактическое потребление
памяти).  А в примитивной сериализации адреса никак не сгруппированы и
не упорядочены, то есть будет почти случайное перемешивание; так что в
памяти будет оседать большое количество лишних страниц.  То есть при
наивной сериализации попытка сколько-нибудь глубокого доступ будет
"всасывать" весь contents_index в память, а оптимизация доступа будет
идти уже на "всосанных" данных.  Тогда понятие оптимальности
раздваивается: с точки зрения userspace вместо линейного перебора
будет trie; а с точки зрения virtual memory и свопа получается
то же самое, то есть очень дорого.

[*] http://en.wikipedia.org/wiki/Page_fault