Computational complexity of rm & ls

[Guy Harris]

 >>Under SysV directories never shrink by themselves, so access efficiency
 >>depends on how many files have ever been in that directory at once
 >>instead of how many are currently there.  If you have a scheme to
 >>determine which of 100 directories a particular file will be stored
 >>under, that calculation is almost certain to be faster than a search
 >>of many hundreds of extra files in the same directory.
 >
 >Nonsense.  System V directories don't shrink, but they don't grow unless
 >they need to, either.  System V can and will fill in holes in directories.

System V will fill in holes, so will most other UNIX systems. 
Nevertheless, the claim that Les Mikesell makes is not "nonsense";
directory searches go all the way out to the end of the directory, and
if the directory once held 10,000 entries, then unless your system
shrinks directories, the search will have to scan through all 10,000 of
those entries, even if they're empty.  A directory name lookup cache
can alleviate this problem; I think the DNLC in S5R4 will be used both
with the V7 (System V) file system and the Berkeley (UFS) file system
(which, in S5R4, should shrink directories as per 4.3BSD).