[devel] contents_index trie

[Alexey Tourbin]

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
----------- следующая часть -----------
Было удалено вложение не в текстовом формате...
Имя     : =?iso-8859-1?q?=CF=D4=D3=D5=D4=D3=D4=D7=D5=C5=D4?=
Тип     : application/pgp-signature
Размер  : 197 байтов
Описание: =?iso-8859-1?q?=CF=D4=D3=D5=D4=D3=D4=D7=D5=C5=D4?=
Url     : <http://lists.altlinux.org/pipermail/devel/attachments/20081028/8c209ba6/attachment.bin>