Re: [PATCH 4/3] Avoid using 'lstat()' to figure out directories

Paolo Bonzini [off-list ref] writes:

quoted

+		if (ce->name[len]>  '/')
+			break;
+		if (ce->name[len]<  '/')
+			continue;

What about

	if (ce->name[len] < '/') {
		if (strchr(ce->name + len + 1, '/'))
			break;
		else
			continue;
	}

to just punt if we'd go into a directory?  I'm not much worried about
accessing foo-0001, foo-0002, foo-0003 while looking for foo/a (that
would be O(number of files in a directory), which is bearable), but
risking to go down a huge subtree is not very nice.

I am not so sure about "go down" part.  After all, what the loop does is
to scan an array of pointers to cache entries and the "continue" causes
the loop to iterate until you find a path that is in the directory in
question.  It is all in userspace code walking on a flat namespace and
there is no "we are going down into a subdirectory and need to open
another directory node" kind of overhead associated with it.

How expensive is it to do this, compared to an lstat() on a system that
does not have dtype in "struct stat" (which means "lstat() is very cheap
on Linux" does not even get into the picture)?  IOW, how many cache
entries can we afford to check their names with strncmp, before the cost
of doing so gets more expensive than a single lstat() on say Cygwin?

I am hoping that the userland is userland and even on Windows it will run
at full CPU speed, while lstat() may need to pay penalty on Windows due to
POSIXy emulation layer, so the tradeoff might turn out to be that we can
afford to test quite many cache entries and still win if we can save a
single lstat().