chris@mimsy.UUCP (Chris Torek) (12/23/88)
In article <580@redsox.UUCP> campbell@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@mimsy.umd.edu Path: uunet!mimsy!chris