Computational complexity of rm & ls

[Chuck Karish]

In article <TALE.89Mar13170500 at imagine.pawl.rpi.edu> tale at pawl.rpi.edu wrote:
>In article <9000012 at m.cs.uiuc.edu>, wsmith at m.cs.uiuc.edu writes:
>wsmith> [...]   "rm *" seems to be a common
>wsmith> enough idiom that rm could be optimized to handle that case better.

>In article <1541 at zen.UUCP> frank at zen.co.uk (Frank Wales) wrote:
>FW>Maybe adding a '-A' ... option to rm would be justified.

>In article <871 at Portia.Stanford.EDU> karish at forel.stanford.edu
>(Chuck Karish) writes:
>CK> Great, another feature!  How about using an alias instead:
>CK> 
>CK> 	alias rmall 'ls -f | xargs rm -f'

>By your own quoting, Chuck, the reason Frank suggested -A was for
>optimization.  Invoking ls to pipe to xargs which calls rm is not the
>optimum strategy.

If I understand the problem correctly, my pipeline takes an algorithm
that's exponential in time w.r.t. the number of directory entries, and
recasts it so it's linear.  Is this optimization, or not?

When I type 'rm *' the shell sorts the argument list before passing it
to rm, which does a pretty fair job of maximizing the amount of
directory scanning that rm has to do.  'ls -f' presents the arguments
to rm in directory order, so rm always seeks by exactly one directory
entry to get from one argument to the next.

If a hack is needed, it's to the shell, not to rm.  If it were possible
(is it already?) to do filename globbing without sorting, the 'ls -f'
would be unnecessary.  All accesses of large directories are expensive,
not just 'rm *'; adding a no-sort option to the shell would provide a
single feature that would help many utilities.

The '-A' option would eliminate the need for the xargs call (the
problem posed only arises in cases where the argument list is likely to
exceed ARG_MAX), but would do so only for the one special case.

	Chuck Karish	hplabs!hpda!mindcrf!karish	(415) 493-7277
			karish at forel.stanford.edu