[devel] contents_index trie

[Alexey Tourbin]

On Tue, Oct 28, 2008 at 01:19:20PM +0600, Mikhail Gusarov wrote:
> Twas brillig at 10:04:13 28.10.2008 UTC+03 when at на altlinux.ru did gyre and gimble:
> 
>  AT> С точки зрения доступа сериализации должна давать минимальное
>  AT> количество page faults [*].  То есть, примерно, чтобы переход / ->
>  AT> /usr затрагивал всего одну 4K страницу (которую необходимо
>  AT> загрузить в память с диска), переход /usr -> /usr/share затрагивал
>  AT> всего одну 4K страницу и т.д.
> 
>  AT> Если на одной странице оказываются unrelated пути (напр. /usr и
>  AT> /etc), то мы лишь избавляемся от лишних вызовов типа regexec(3)
>  AT> (как в grep), но не можем ограничить активность ОС (ограничить
>  AT> фактическое потребление памяти).
> 
> Не понимаю, почему так. Возьмём путь длиной в 40 символов (для простоты
> - 40 байтов). Для того, чтобы добраться до его конца, нам нужно
> прочитать 40 узлов.

Нужно не прочитать 40 узлов, а выполнить 40 разыменоваываний (dereferencing "->").
То, что разыменовывание означает чтение узла, это и есть оптимистическое
предоложение о том, что у нас есть фс-подобная структура с локальными
переходами между узлами.  Но на самом деле её нет.  Мы прсто сдампили
память.  Так что чтение "узла /usr" может дать чтение порядка 700
страниц (ls -l /usr |wc -c).

Точнее, это сильно зависит от способа организации ссылок.
Но при использовании malloc(3) вариантов мало.

     +---+                    +--------+
/usr | * | --> адрес страницы | /share | -> ...
     +---+                    +--------+
     | * |`
     +---+ `-> адрес страницы +--------+
     | * |`                   | /bin   | -> ...
     +---+ `		      +--------+
            `-> ...

Дело в том, что тут strcmp можно сделать на на стадии /usr, а только
после подгрузки всех детей /usr.

Надо подумать.

> Каждый узел - это, максимум, 256 x (байт, указатель
> на заголовок следующего блока, бит статуса), т.е. укладывается в 4k с
> запасом. Бит статуса можно изжить с помощью заголовка "имена начинаются
> со смещения 0xabcde".
> 
> Таким образом, для lookup'а придётся поднять 41 блок (последний - для
> вычитываяния имени пакета) даже при тривиальной сериализации, которая
> просто не даёт узлу пересечь границу блока.
> 
> В случае несильного ветвления лексикографическая сортировка даст ещё
> большую экономию (последовательные узлы окажутся в одном или соседних
> дисковых блоках).
----------- следующая часть -----------
Было удалено вложение не в текстовом формате...
Имя     : =?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/d276d519/attachment-0001.bin>