Leaf directories (Re: Why is find so slow)

[Chris Torek]

>In article <26981 at mimsy.umd.edu> I demonstrate how to avoid extra
`stat' calls on Unix systems that happen also to be POSIX conformant.
(I am told that POSIX requires links, but not `..' links, so the code
that says `nsubdirs = st.st_nlink - 2' is Unix-specific.)  An important
feature of the algorithm is that stat()s stop as soon as all
subdirectories have been found.

In article <9959 at jpl-devvax.JPL.NASA.GOV> lwall at jpl-devvax.JPL.NASA.GOV
(Larry Wall) writes:
>If find is done this way, it would behoove us to sort subdirectories
>before filenames in each directory so that nsubdirs goes to 0 as soon
>as possible.

Yes.  Note that `restore'ing a file system Just Happens to do this.
(Actually, it does it for an obvious reason---the data `dump' writes
is in this order---but it turns out to be convenient.)  You can also
write a program that marches through a directory tree, moving all
subdirectories to the front---it looks something like this:

	# untested shell script to move files after directories
	# does not work in / or at mount points
	# does not handle file names with embedded shell metacharacters
	dirs=
	files=
	for i in `ls -a | tail +2`; do
		if [ -d $i ]; then
			dirs="$dirs $i"
			(cd $i; sh move_them_around)
		else
			files="$files $i"
		fi
	done
	mkdir ../move_tmp.$$
	case "$dirs" in "");; *) mv $dirs ../move_tmp.$$;; esac
	case "$files" in "");; *) mv $files ../move_tmp.$$;; esac
	here=`pwd | sed -e 's,.*/,,`
	cd ..
	rmdir $here; mv move_tmp.$$ $here

This can all be done better in perl. :-)
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 405 2750)
Domain:	chris at cs.umd.edu	Path:	uunet!mimsy!chris