Re: [devel] contents_index trie

[Mikhail Gusarov <dottedmag@altlinux.org>]

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

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 узлов. Каждый узел - это, максимум, 256 x (байт, указатель
на заголовок следующего блока, бит статуса), т.е. укладывается в 4k с
запасом. Бит статуса можно изжить с помощью заголовка "имена начинаются
со смещения 0xabcde".

Таким образом, для lookup'а придётся поднять 41 блок (последний - для
вычитываяния имени пакета) даже при тривиальной сериализации, которая
просто не даёт узлу пересечь границу блока.

В случае несильного ветвления лексикографическая сортировка даст ещё
большую экономию (последовательные узлы окажутся в одном или соседних
дисковых блоках).

-- 

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