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

From: Junio C Hamano <gitster@pobox.com>
Date: Jul 9, 2009, 23:37 UTC
Message-ID: <7vd489zavf.fsf@alter.siamese.dyndns.org>
In-Reply-To: <4A5670F3.9020309@gnu.org>

Paolo Bonzini <bonzini@gnu.org> writes:

Show 18 quoted lines

>> +		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().