Re: git stash takes excessively long when many untracked files present

Junio C Hamano [off-list ref] writes:

I think this is wrong.

When we are looking at a directory P in the working tree, there are
three cases:

 (1) P exists in the index.  Everything inside the directory P in
     the working tree needs to go when P is checked out from the
     index.

 (2) P does not exist in the index, but there is P/Q in the index.
     We know P will stay a directory when we check out the contents
     of the index, but we do not know yet if there is a directory
     P/Q in the working tree to be killed, so we need to recurse.

 (3) P does not exist in the index, and there is no P/Q in the index
     to require P to be a directory, either.  Only in this case, we
     know that everything inside P will not be killed without
     recursing.

The patch will break with the second case, I think.

"ls-files -o" and "ls-files -k" both traverse the working tree down
to find either all untracked paths or those that will be "killed"
(removed from the working tree to make room) when the paths recorded
in the index are checked out.

It is necessary to traverse the working tree fully when enumerating
all the "other" paths, but when we are only interested in "killed"
paths, we can take advantage of the fact that paths that do not
overlap with entries in the index can never be killed.

The first one is an independent clean-up.  No public API in the
working tree traversal takes alternate in-core index, so there is no
reason to explicitly use the_index and index_* functions from the
in-core index API.

The second one is rerolled from the "something like this" patch I
sent earlier, but corrects the "we see a directory, it is not in the
index, but a file in it is" case.

And the third one adds a testcase that illustrates why the earlier
"something like this" patch is not sufficient.

These are designed to apply on top of v1.8.3, and needs a bit of
conflict resolution for the upcoming v1.8.4 codebase; I'll queue
them in 'pu' for now.

Note that t3010, especially after merged to 'pu', will use many
different ways to create a test file.  Some redirect "date" into it,
some redirect ":" into it, some "touch" it, and some just redirect
with no command.

	date >file1
	: >file2
	touch file3
	>file4

We should consolidate them all to just do ">file4" after making sure
the contents do not matter (we kind of know it already, as "date"
will output string that is not repeatable).  Use of "touch" for
anything other than updating the timestamp is especially bad, as it
is misleading.

Junio C Hamano (3):
  dir.c: use the cache_* macro to access the current index
  ls-files -k: a directory only can be killed if the index has a non-directory
  t3010: update to demonstrate "ls-files -k" optimization pitfalls

 builtin/ls-files.c                  |  2 ++
 dir.c                               | 40 +++++++++++++++++++++++++++++--------
 dir.h                               |  3 ++-
 t/t3010-ls-files-killed-modified.sh | 12 ++++++++---
 4 files changed, 45 insertions(+), 12 deletions(-)

-- 
1.8.4-rc3-232-ga8053f8

These codepaths always start from the_index and use index_*
functions, but there is no reason to do so.  Use the compatibility
cache_* macro to access the current in-core index like everybody
else.

While at it, fix typo in the comment for a function to check if a
path within a directory appears in the index.

Signed-off-by: Junio C Hamano <redacted>
---
 dir.c | 11 +++++------
 1 file changed, 5 insertions(+), 6 deletions(-)

diff --git a/dir.c b/dir.c
index a5926fb..2f82cd1 100644
--- a/dir.c
+++ b/dir.c

@@ -472,15 +472,14 @@ static void *read_skip_worktree_file_from_index(const char *path, size_t *size)
 	unsigned long sz;
 	enum object_type type;
 	void *data;
-	struct index_state *istate = &the_index;
 
 	len = strlen(path);
-	pos = index_name_pos(istate, path, len);
+	pos = cache_name_pos(path, len);
 	if (pos < 0)
 		return NULL;
-	if (!ce_skip_worktree(istate->cache[pos]))
+	if (!ce_skip_worktree(active_cache[pos]))
 		return NULL;
-	data = read_sha1_file(istate->cache[pos]->sha1, &type, &sz);
+	data = read_sha1_file(active_cache[pos]->sha1, &type, &sz);
 	if (!data || type != OBJ_BLOB) {
 		free(data);
 		return NULL;

@@ -924,13 +923,13 @@ enum exist_status {
 };
 
 /*
- * Do not use the alphabetically stored index to look up
+ * Do not use the alphabetically sorted index to look up
  * the directory name; instead, use the case insensitive
  * name hash.
  */
 static enum exist_status directory_exists_in_index_icase(const char *dirname, int len)
 {
-	struct cache_entry *ce = index_name_exists(&the_index, dirname, len + 1, ignore_case);
+	struct cache_entry *ce = cache_name_exists(dirname, len + 1, ignore_case);
 	unsigned char endchar;
 
 	if (!ce)

-- 
1.8.4-rc3-232-ga8053f8

An earlier draft of the previous step used cache_name_exists() to
check the directory we were looking at, which missed the second case
described in its log message.  Demonstrate why it is not sufficient.

Signed-off-by: Junio C Hamano <redacted>
---
 t/t3010-ls-files-killed-modified.sh | 12 +++++++++---
 1 file changed, 9 insertions(+), 3 deletions(-)

diff --git a/t/t3010-ls-files-killed-modified.sh b/t/t3010-ls-files-killed-modified.sh
index 95671c2..6ea7ca8 100755
--- a/t/t3010-ls-files-killed-modified.sh
+++ b/t/t3010-ls-files-killed-modified.sh

@@ -11,6 +11,7 @@ This test prepares the following in the cache:
     path1       - a symlink
     path2/file2 - a file in a directory
     path3/file3 - a file in a directory
+    pathx/ju    - a file in a directory
 
 and the following on the filesystem:
 

@@ -21,6 +22,7 @@ and the following on the filesystem:
     path4	- a file
     path5	- a symlink
     path6/file6 - a file in a directory
+    pathx/ju/nk - a file in a directory to be killed
 
 git ls-files -k should report that existing filesystem
 objects except path4, path5 and path6/file6 to be killed.

@@ -44,16 +46,17 @@ then
 else
 	date > path1
 fi
-mkdir path2 path3
+mkdir path2 path3 pathx
 date >path2/file2
 date >path3/file3
+>pathx/ju
 : >path7
 date >path8
 : >path9
 date >path10
 test_expect_success \
     'git update-index --add to add various paths.' \
-    "git update-index --add -- path0 path1 path?/file? path7 path8 path9 path10"
+    "git update-index --add -- path0 path1 path?/file? pathx/ju path7 path8 path9 path10"
 
 rm -fr path? ;# leave path10 alone
 date >path2

@@ -65,7 +68,7 @@ else
 	date > path3
 	date > path5
 fi
-mkdir path0 path1 path6
+mkdir -p path0 path1 path6 pathx/ju
 date >path0/file0
 date >path1/file1
 date >path6/file6

@@ -73,6 +76,7 @@ date >path7
 : >path8
 : >path9
 touch path10
+>pathx/ju/nk
 
 test_expect_success \
     'git ls-files -k to show killed files.' \

@@ -82,6 +86,7 @@ path0/file0
 path1/file1
 path2
 path3
+pathx/ju/nk
 EOF
 
 test_expect_success \

@@ -98,6 +103,7 @@ path2/file2
 path3/file3
 path7
 path8
+pathx/ju
 EOF
 
 test_expect_success \

-- 
1.8.4-rc3-232-ga8053f8

"ls-files -o" and "ls-files -k" both traverse the working tree down
to find either all untracked paths or those that will be "killed"
(removed from the working tree to make room) when the paths recorded
in the index are checked out.  It is necessary to traverse the
working tree fully when enumerating all the "other" paths, but when
we are only interested in "killed" paths, we can take advantage of
the fact that paths that do not overlap with entries in the index
can never be killed.

The treat_one_path() helper function, which is called during the
recursive traversal, is the ideal place to implement an
optimization.

When we are looking at a directory P in the working tree, there are
three cases:

 (1) P exists in the index.  Everything inside the directory P in
     the working tree needs to go when P is checked out from the
     index.

 (2) P does not exist in the index, but there is P/Q in the index.
     We know P will stay a directory when we check out the contents
     of the index, but we do not know yet if there is a directory
     P/Q in the working tree to be killed, so we need to recurse.

 (3) P does not exist in the index, and there is no P/Q in the index
     to require P to be a directory, either.  Only in this case, we
     know that everything inside P will not be killed without
     recursing.

Note that this helper is called by treat_leading_path() that decides
if we need to traverse only subdirectories of a single common
leading directory, which is essential for this optimization to be
correct.  This caller checks each level of the leading path
component from shallower directory to deeper ones, and that is what
allows us to only check if the path appears in the index.  If the
call to treat_one_path() weren't there, given a path P/Q/R, the real
traversal may start from directory P/Q/R, even when the index
records P as a regular file, and we would end up having to check if
any leading subpath in P/Q/R, e.g. P, appears in the index.

Signed-off-by: Junio C Hamano <redacted>
---
 builtin/ls-files.c |  2 ++
 dir.c              | 29 +++++++++++++++++++++++++++--
 dir.h              |  3 ++-
 3 files changed, 31 insertions(+), 3 deletions(-)

diff --git a/builtin/ls-files.c b/builtin/ls-files.c
index 2202072..c7eb6f4 100644
--- a/builtin/ls-files.c
+++ b/builtin/ls-files.c

@@ -213,6 +213,8 @@ static void show_files(struct dir_struct *dir)
 
 	/* For cached/deleted files we don't need to even do the readdir */
 	if (show_others || show_killed) {
+		if (!show_others)
+			dir->flags |= DIR_COLLECT_KILLED_ONLY;
 		fill_directory(dir, pathspec);
 		if (show_others)
 			show_other_files(dir);

diff --git a/dir.c b/dir.c
index 2f82cd1..ff768f3 100644
--- a/dir.c
+++ b/dir.c

@@ -1173,12 +1173,37 @@ static enum path_treatment treat_one_path(struct dir_struct *dir,
 					  int dtype, struct dirent *de)
 {
 	int exclude;
+	int has_path_in_index = !!cache_name_exists(path->buf, path->len, ignore_case);
+
 	if (dtype == DT_UNKNOWN)
 		dtype = get_dtype(de, path->buf, path->len);
 
 	/* Always exclude indexed files */
-	if (dtype != DT_DIR &&
-	    cache_name_exists(path->buf, path->len, ignore_case))
+	if (dtype != DT_DIR && has_path_in_index)
+		return path_none;
+
+	/*
+	 * When we are looking at a directory P in the working tree,
+	 * there are three cases:
+	 *
+	 * (1) P exists in the index.  Everything inside the directory P in
+	 * the working tree needs to go when P is checked out from the
+	 * index.
+	 *
+	 * (2) P does not exist in the index, but there is P/Q in the index.
+	 * We know P will stay a directory when we check out the contents
+	 * of the index, but we do not know yet if there is a directory
+	 * P/Q in the working tree to be killed, so we need to recurse.
+	 *
+	 * (3) P does not exist in the index, and there is no P/Q in the index
+	 * to require P to be a directory, either.  Only in this case, we
+	 * know that everything inside P will not be killed without
+	 * recursing.
+	 */
+	if ((dir->flags & DIR_COLLECT_KILLED_ONLY) &&
+	    (dtype == DT_DIR) &&
+	    !has_path_in_index &&
+	    (directory_exists_in_index(path->buf, path->len) == index_nonexistent))
 		return path_none;
 
 	exclude = is_excluded(dir, path->buf, &dtype);

diff --git a/dir.h b/dir.h
index 3d6b80c..4677b86 100644
--- a/dir.h
+++ b/dir.h

@@ -80,7 +80,8 @@ struct dir_struct {
 		DIR_HIDE_EMPTY_DIRECTORIES = 1<<2,
 		DIR_NO_GITLINKS = 1<<3,
 		DIR_COLLECT_IGNORED = 1<<4,
-		DIR_SHOW_IGNORED_TOO = 1<<5
+		DIR_SHOW_IGNORED_TOO = 1<<5,
+		DIR_COLLECT_KILLED_ONLY = 1<<6
 	} flags;
 	struct dir_entry **entries;
 	struct dir_entry **ignored;

-- 
1.8.4-rc3-232-ga8053f8