faster name lookups for SysV (was libraries)

[Chris Torek]

In article <580 at redsox.UUCP> campbell at redsox.UUCP (Larry Campbell) writes:
>Why not keep directories sorted?  In SysV filesystems this is easy and
>relatively inexpensive, since you can assume a fixed 16 bytes per name.
>I am also assuming that lookups outnumber creations to a huge degree,
>which I'm sure is the case.

As far as I know, this is true for everything except /tmp (where
lookups average only a few times more common).  Unfortunately, a
complete sorting would require nontrivial changes, as it is hard inside
the kernel to move text from one file system block to another.  Still,
at 16 bytes per entry, and 512 or 1024 bytes per block, one could
easily keep each block sorted, and reduce each block scan from 32 or 64
string comparisons to 5 or 6.

>Then namei becomes a binary search.

Or a piecewise binary search (one block at a time).

If you are stuck with SysV file systems, and have source, try adding
partial sorting to your namei and see if performance improves.
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain:	chris at mimsy.umd.edu	Path:	uunet!mimsy!chris