Computational complexity of rm & ls

[Chris Torek]

In article <3804 at emory.mathcs.emory.edu> arnold at mathcs.emory.edu
(Arnold D. Robbins {EUCC}) writes:
>I'll bet that if you were to 
>
>	rm `ls -f`		and
>	rm `ls -f | tac`	
>
>you'd see very interesting behavior (i.e. remove files starting with
>the first and last files in the directory, respectively), since each
>unlink has to search the directory from scratch to find the entry.
>(Actually, on 4.3 the last one would be pathologically bad, while the
>first would be really quick, due to the directory caching in namei.)

This did not match what I remembered, so I just checked.  You cannot
cache the result of a delete operation (it is senseless), so the only
thing that would affect the time is the offset cache.  Around line 370
of ufs_namei.c, one finds the following comment:

	/*
	 * If this is the same directory that this process
	 * previously searched, pick up where we last left off.
	 * We cache only lookups as these are the most common
	 * and have the greatest payoff. Caching CREATE has little
	 * benefit as it usually must search the entire directory
	 * to determine that the entry does not exist. Caching the
	 * location of the last DELETE has not reduced profiling time
	 * and hence has been removed in the interest of simplicity.
	 */

The effect unlink order would have, then, is that a forward remove
would aid each lookup by reducing the number of entries scanned.  The
effect should certainly be measurable, but probably not extreme.
-- 
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