> I think I found the general area of the problem, though I don't know the 
> code well-enough to continue. The fts source has the following comment:
> 
>  * The real slowdown in walking the tree is the stat calls.  If FTS_NOSTAT is
>  * set and it's a physical walk (so that symbolic links can't be directories),
>  * we can do things quickly.  First, if it's a 4.4BSD file system, the type
>  * of the file is in the directory entry.  Otherwise, we assume that the number
>  * of subdirectories in a node is equal to the number of links to the parent.
>  * The former skips all stat calls.  The latter skips stat calls in any leaf
>  * directories and for any files after the subdirectories in the directory have
>  * been found, cutting the stat calls by about 2/3. 
> 
> I think the problem is that the code's making an assumption which isn't 
> true for this NFS server. Unfortunately I don't understand the code 
> well-enough to know what exactly that assumption is. :-)

iirc, fts assumes that, number of sub directory == (nlink - 2).
ie. scanning a directory, if it has already found (nlink - 2) sub directories,
it consider that none of subsequent entries is a directory (and optimize
out stat() calls).

in the case of "mkdir -p foo/bar/baz; rm -r foo",
i guess, fts considered that "foo/bar" was not a directory.

YAMAMOTO Takashi