Re: [devel] contents_index trie

[Alexey Tourbin <at@altlinux.ru>]

[-- Attachment #1: Type: text/plain, Size: 2432 bytes --]

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 блок (последний - для
> вычитываяния имени пакета) даже при тривиальной сериализации, которая
> просто не даёт узлу пересечь границу блока.
> 
> В случае несильного ветвления лексикографическая сортировка даст ещё
> большую экономию (последовательные узлы окажутся в одном или соседних
> дисковых блоках).

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]