[devel] contents_index trie

[Mikhail Gusarov]

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

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

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