Re: [PATCH 3/3] Avoid doing extra 'lstat()'s for d_type if we have an up-to-date cache entry

Linus Torvalds [off-list ref] writes:

On Thu, 9 Jul 2009, Junio C Hamano wrote:

quoted

I was wondering if we could also say that D exists as a directory when we
know there is D/F in the index and is up to date.

Yeah, that would probably be a good thing, but is slightly slower to look 
up (we have the name hashing for the case-ignoring code anyway, but that 
only works for exact names, so you can't look up directories that way).

You'd have to use the regular binary search for that (or we'd have to 
change it to hash directories too - which we might want to do for other 
reasons, but don't do now).

Something like this?

Yeah, in Dmitry's response that crossed with this update patch from you,
he says lstat() on directories are still problem---it would be interesting to
hear what he sees after applying this patch and retesting.

+static int get_index_mode(const char *path, int len)
+{
+	int pos;
+	struct cache_entry *ce;
+
+	ce = cache_name_exists(path, len, 0);
+	if (ce) {
+		if (ce_uptodate(ce))
+			return ce->ce_mode;

You return ce->ce_mode for up-to-date entries.  I do not remember what
ce_uptodate(ce) says for gitlinks, but ce->ce_mode for them would be
160000 that is not very kosher to give to S_ISDIR().  I realize that this
worry actually applies to your patch from yesterday, the one Dmitry
already tested.

+		return 0;
+	}
+
+	/* Try to look it up as a directory */
+	pos = cache_name_pos(path, len);
+	if (pos >= 0)
+		return 0;

How can this find an exact entry for the path?  Assuming that the name
hash cache_name_exists() is not out of sync?  Shouldn't this be a BUG()
instead of "It somehow exists as a blob or submodule, and we'll let the
regular lstat() codepath take care of it by returning 0"?

+	pos = -pos-1;
+	while (pos < active_nr) {
+		ce = active_cache[pos++];
+		if (strncmp(ce->name, path, len))
+			break;
+		if (ce->name[len] > '/')
+			break;
+		if (ce->name[len] < '/')
+			continue;
+		if (!ce_uptodate(ce))
+			break;	/* continue? */

I think this should be continue, as the directory D you are interested in
may have two files, one modified, the other uptodate.

+		return S_IFDIR;
+	}
+	return 0;
+}
+
 static int get_dtype(struct dirent *de, const char *path, int len)
 {
 	int dtype = de ? DTYPE(de) : DT_UNKNOWN;
-	struct cache_entry *ce;
 	struct stat st;
 
 	if (dtype != DT_UNKNOWN)
 		return dtype;
-	ce = cache_name_exists(path, len, 0);
-	if (ce && ce_uptodate(ce))
-		st.st_mode = ce->ce_mode;
-	else if (lstat(path, &st))
+	st.st_mode = get_index_mode(path, len);
+	if (!st.st_mode && lstat(path, &st))
 		return dtype;
 	if (S_ISREG(st.st_mode))
 		return DT_REG;

On Thu, 9 Jul 2009, Junio C Hamano wrote:

quoted

+
+	/* Try to look it up as a directory */
+	pos = cache_name_pos(path, len);
+	if (pos >= 0)
+		return 0;

How can this find an exact entry for the path?  Assuming that the name
hash cache_name_exists() is not out of sync?

Hopefully it would never trigger. But I'd rather write robust code that 
doesn't make any fancy assumptions. Keep it simple - and keep it working 
even if surprising things happen. 

quoted

+		if (!ce_uptodate(ce))
+			break;	/* continue? */

I think this should be continue, as the directory D you are interested in
may have two files, one modified, the other uptodate.

The thing is, the directory may have subdirectories, and there may be 
tens of thousands of files there. And maybe this gets called by code that 
hasn't done any cache preloading at all, so nothing will be up-to-date.

Do we want to loop over thousands of entries? Or do we want to loop as 
little as possible, and just say "most of the time the first entry will be 
representative".

But I did put the 'continue' in a comment, because it's not a correctness 
issue, it's a gut feel. 

			Linus

quoted

+	ce = cache_name_exists(path, len, 0);
+	if (ce) {
+		if (ce_uptodate(ce))
+			return ce->ce_mode;

You return ce->ce_mode for up-to-date entries.  I do not remember what
ce_uptodate(ce) says for gitlinks, but ce->ce_mode for them would be
160000 that is not very kosher to give to S_ISDIR().  I realize that this
worry actually applies to your patch from yesterday, the one Dmitry
already tested.

Yeah. I guess we don't have a lot of coverage for subprojects.

Here's an alternative version that just makes the thing return the DT_xyz 
flag rather than the mode (and it returns DT_REG for symlinks too, because 
it knows nobody cares - we only really care about "directory or not")

		Linus

---
 dir.c |   47 ++++++++++++++++++++++++++++++++++++++++++-----
 1 files changed, 42 insertions(+), 5 deletions(-)

diff --git a/dir.c b/dir.c
index 8a9e7d8..e05b850 100644
--- a/dir.c
+++ b/dir.c

@@ -566,18 +566,55 @@ static int in_pathspec(const char *path, int len, const struct path_simplify *si
 	return 0;
 }
 
+static int get_index_dtype(const char *path, int len)
+{
+	int pos;
+	struct cache_entry *ce;
+
+	ce = cache_name_exists(path, len, 0);
+	if (ce) {
+		if (!ce_uptodate(ce))
+			return DT_UNKNOWN;
+		if (S_ISGITLINK(ce->ce_mode))
+			return DT_DIR;
+		/*
+		 * Nobody actually cares about the
+		 * difference between DT_LNK and DT_REG
+		 */
+		return DT_REG;
+	}
+
+	/* Try to look it up as a directory */
+	pos = cache_name_pos(path, len);
+	if (pos >= 0)
+		return DT_UNKNOWN;
+	pos = -pos-1;
+	while (pos < active_nr) {
+		ce = active_cache[pos++];
+		if (strncmp(ce->name, path, len))
+			break;
+		if (ce->name[len] > '/')
+			break;
+		if (ce->name[len] < '/')
+			continue;
+		if (!ce_uptodate(ce))
+			break;	/* continue? */
+		return DT_DIR;
+	}
+	return DT_UNKNOWN;
+}
+
 static int get_dtype(struct dirent *de, const char *path, int len)
 {
 	int dtype = de ? DTYPE(de) : DT_UNKNOWN;
-	struct cache_entry *ce;
 	struct stat st;
 
 	if (dtype != DT_UNKNOWN)
 		return dtype;
-	ce = cache_name_exists(path, len, 0);
-	if (ce && ce_uptodate(ce))
-		st.st_mode = ce->ce_mode;
-	else if (lstat(path, &st))
+	dtype = get_index_dtype(path, len);
+	if (dtype != DT_UNKNOWN)
+		return dtype;
+	if (lstat(path, &st))
 		return dtype;
 	if (S_ISREG(st.st_mode))
 		return DT_REG;

On Thu, 9 Jul 2009, Linus Torvalds wrote:

Here's an alternative version that just makes the thing return the DT_xyz 
flag rather than the mode (and it returns DT_REG for symlinks too, because 
it knows nobody cares - we only really care about "directory or not")

Btw, I'm wondering whether this "look if 'dir/file' exists in index and is 
up-to-date" is really safe.

We don't really verify the whole path when we mark things ce_uptodate(). 
Part of what read_directory() does is to find directory entries, and in 
the process things like "git add" will notice if there's a conflict with 
existing index entries.

So if a directory has changed into a symlink to a directory, this 
particular optimization will actually hide that, I suspect. I haven't 
tested, though. But it might be worth-while to see what happens when you 
had a directory structure, and then do

	mkdir dir
	touch dir/a
	touch dir/b
	git add dir

	mv dir new-dir
	ln -s new-dir dir
	git status

Quite frankly, I'd personally be perfectly ok with git _not_ noticing 
subtle things like this automatically, but..

		Linus

On Thu, Jul 09, 2009 at 09:32:03AM -0700, Junio C Hamano wrote:

Yeah, in Dmitry's response that crossed with this update patch from you,
he says lstat() on directories are still problem---it would be interesting to
hear what he sees after applying this patch and retesting.

With this patch, I see one 'stat' less for each directory, which on my
repo resulted in about 10.7% less 'stat' or 4.8% less of the total
number of syscalls. The total run time decreased by 4.6%.

Still, there are many stats for directories -- for each directory I see
2 + number of subdirectories it has, but I am not sure about its cause.

There is one strange thing though. Before that patch the number of
'open' for each directory was always the same in each run. But after
that patch, it slightly differs in each run... Comparing with results
without this patch, the number of open for some directories in some
be less by one... which is puzzling...


Dmitry

Dmitry Potapov <dpotapov <at> gmail.com> writes:

With this patch, I see one 'stat' less for each directory, which on my
repo resulted in about 10.7% less 'stat' or 4.8% less of the total
number of syscalls. The total run time decreased by 4.6%.

Still, there are many stats for directories -- for each directory I see
2 + number of subdirectories it has, but I am not sure about its cause.

That would probably be the fact that in cygwin 1.5, a stat() of a directory
results in querying all the contents of the directory so as to correctly
populate the st_link member based on the number of subdirectories.  In cygwin
1.7, in addition to adding the d_type member to readdir, stat was also changed
to blindly return st_link of 1 for all directories rather than wasting time
populating the st_link member (since Windows provides no efficient way of
accessing that number).

-- 
Eric Blake

On Fri, Jul 10, 2009 at 01:05:13AM +0400, Dmitry Potapov wrote:

There is one strange thing though. Before that patch the number of
'open' for each directory was always the same in each run. But after
that patch, it slightly differs in each run... Comparing with results
without this patch, the number of open for some directories in some
be less by one... which is puzzling...

It appears that is a purely Windows thing... It seems extra opens for
directories inside of the working tree are caused by Windows Prefetcher.
http://en.wikipedia.org/wiki/Prefetcher

Accordingly to the Process Monitor, during start-up, it opens and reads
most directories in the repo that have subdirectories but sometimes it
skips some of them... So, the patch works as expected... Perhaps, I
should disable this prefetcher for testing to get more reproduceable
results. Anyway, this prefetecher does not issue QueryOpen (stat) for
files in the repo, so my numbers for 'stat' are not affected by it.


Dmitry

On Thu, Jul 09, 2009 at 09:52:24PM +0000, Eric Blake wrote:

Dmitry Potapov <dpotapov <at> gmail.com> writes:

quoted

With this patch, I see one 'stat' less for each directory, which on my
repo resulted in about 10.7% less 'stat' or 4.8% less of the total
number of syscalls. The total run time decreased by 4.6%.

Still, there are many stats for directories -- for each directory I see
2 + number of subdirectories it has, but I am not sure about its cause.

That would probably be the fact that in cygwin 1.5, a stat() of a directory
results in querying all the contents of the directory so as to correctly
populate the st_link member based on the number of subdirectories.

We do not use lstat or fstat provided by Cygwin. Instead of it, we use
their fast and dirty analogues, which you can find in compat/cygwin.c
(they do not provide all information that normal functions provide, but
this information is sufficient for Git.

But we still use readdir() from Cygwin and that may be source of extra
syscalls that I observe...

Dmitry

On Fri, Jul 10, 2009 at 03:30:24AM +0400, Dmitry Potapov wrote:

But we still use readdir() from Cygwin and that may be source of extra
syscalls that I observe...

opendir gives an extra 'stat' before opening directory
readdir produces one more extra 'stat' on the parent directory before
        returning '..'
open(.gitignore) does one extra 'stat' on the directory where it tries
        to open .gitignore (it did not exist in my tests)

So, the number of 'stat' on each directory is 2 plus the number of
subidectories that it has. Thus, the total number of 'stat' for all
directories is 3 multiple the number of directories in your repo. All
those 'stat' are artifacts of Cygwin. Also, you have 2 open per each
directory and one of them are redundant (at least, for Git purposes).
Overall (including syscalls for .gitignore), you have the following
number of syscalls for each directory in your repo:
  5 - QueryOpen (stat)
  3 - CreateFile (open)
  2 - CloseFile (close)
  1 - QueryFileInternalInformationFile

Here is the detail listing of testing of read_directory_recursive:
=====
opendir(.)
	QueryOpen,E:\dpotapov\repo
	CreateFile,E:\dpotapov\repo
first readdir call
	QueryDirectory,E:\dpotapov\repo
second readdir call that returns '..'
	QueryOpen,E:\dpotapov
	CreateFile,E:\dpotapov
	QueryFileInternalInformationFile,E:\dpotapov
	CloseFile,E:\dpotapov
open(.gitignore) -- .gitignore does not exist
	QueryOpen,E:\dpotapov\repo\.gitignore
	QueryOpen,E:\dpotapov\repo\.gitignore.lnk
	QueryOpen,E:\dpotapov\repo
	CreateFile,E:\dpotapov\repo\.gitignore
stat for untracked file
	QueryOpen,E:\dpotapov\repo\bar
opendir(dir1)
	QueryOpen,E:\dpotapov\repo\dir1
	CreateFile,E:\dpotapov\repo\dir1
first readdir call
	QueryDirectory,E:\dpotapov\repo\dir1
second readdir call that returns '..'
	QueryOpen,E:\dpotapov\repo
	CreateFile,E:\dpotapov\repo
	QueryFileInternalInformationFile,E:\dpotapov\repo
	CloseFile,E:\dpotapov\repo
open(.gitignore) -- .gitignore does not exist
	QueryOpen,E:\dpotapov\repo\dir1\.gitignore
	QueryOpen,E:\dpotapov\repo\dir1\.gitignore.lnk
	QueryOpen,E:\dpotapov\repo\dir1
	CreateFile,E:\dpotapov\repo\dir1\.gitignore
last readdir call that returns NULL
	QueryDirectory,E:\dpotapov\repo\dir1
closedir
	CloseFile,E:\dpotapov\repo\dir1
stat for some modified file
	QueryOpen,E:\dpotapov\repo\foo
last readdir call that returns NULL
	QueryDirectory,E:\dpotapov\repo
closedir
	CloseFile,E:\dpotapov\repo
=====

Dmitry