Re: [PATCH v3 3/3] builtin/grep.c: walking tree instead of expanding index with --sparse

[Victoria Dye <vdye@github.com>]

Shaoxuan Yuan wrote:
> Before this patch, whenever --sparse is used, `git-grep` utilizes the
> ensure_full_index() method to expand the index and search all the
> entries. Because this method requires walking all the trees and
> constructing the index, it is the slow part within the whole command.
> 
> To achieve better performance, this patch uses grep_tree() to search the
> sparse directory entries and get rid of the ensure_full_index() method.
> 
> Why grep_tree() is a better choice over ensure_full_index()?
> 
> 1) grep_tree() is as correct as ensure_full_index(). grep_tree() looks
>    into every sparse-directory entry (represented by a tree) recursively
>    when looping over the index, and the result of doing so matches the
>    result of expanding the index.
> 
> 2) grep_tree() utilizes pathspecs to limit the scope of searching.
>    ensure_full_index() always expands the index when --sparse is used,
>    that means it will always walk all the trees and blobs in the repo
>    without caring if the user only wants a subset of the content, i.e.
>    using a pathspec. On the other hand, grep_tree() will only search
>    the contents that match the pathspec, and thus possibly walking fewer
>    trees.
> 
> 3) grep_tree() does not construct and copy back a new index, while
>    ensure_full_index() does. This also saves some time.

Would you mind adding some 'ensure_not_expanded' cases to 't1092' to codify
this (probably in the 'grep is not expanded' test created in patch 2)? If
I'm understanding this patch correctly, you've updated 'git grep' so that it
*never* needs to expand the index. In that case, it would be good to
exercise a bunch of 'git grep' options (pathspecs inside and outside the
sparse cone, wildcard pathspecs, etc.) to confirm that.

> 
> ----------------
> Performance test
> 
> - Summary:
> 
> p2000 tests demonstrate a ~91% execution time reduction for
> `git grep --cached --sparse <pattern> -- <pathspec>` using tree-walking
> logic.
> 
> Test                                                                          HEAD~   HEAD
> ---------------------------------------------------------------------------------------------------
> 2000.78: git grep --cached --sparse bogus -- f2/f1/f1/builtin/* (full-v3)     0.11    0.09 (≈)
> 2000.79: git grep --cached --sparse bogus -- f2/f1/f1/builtin/* (full-v4)     0.08    0.09 (≈)
> 2000.80: git grep --cached --sparse bogus -- f2/f1/f1/builtin/* (sparse-v3)   0.44    0.04 (-90.9%)
> 2000.81: git grep --cached --sparse bogus -- f2/f1/f1/builtin/* (sparse-v4)   0.46    0.04 (-91.3%)

These are fantastic results!

> 
> - Command used for testing:
> 
> 	git grep --cached --sparse bogus -- f2/f1/f1/builtin/*
> 
> The reason for specifying a pathspec is that, if we don't specify a
> pathspec, then grep_tree() will walk all the trees and blobs to find the
> pattern, and the time consumed doing so is not too different from using
> the original ensure_full_index() method, which also spends most of the
> time walking trees. However, when a pathspec is specified, this latest
> logic will only walk the area of trees enclosed by the pathspec, and the
> time consumed is reasonably a lot less.
> 
> That is, if we don't specify a pathspec, the performance difference [1]
> is quite small: both methods walk all the trees and take generally same
> amount of time (even with the index construction time included for
> ensure_full_index()).

This makes sense, thanks for the thorough explanation of the results.

> 
> [1] Performance test result without pathspec:
> 
> 	Test                                                    HEAD~  HEAD
> 	-----------------------------------------------------------------------------
> 	2000.78: git grep --cached --sparse bogus (full-v3)     6.17   5.19 (≈)
> 	2000.79: git grep --cached --sparse bogus (full-v4)     6.19   5.46 (≈)
> 	2000.80: git grep --cached --sparse bogus (sparse-v3)   6.57   6.44 (≈)
> 	2000.81: git grep --cached --sparse bogus (sparse-v4)   6.65   6.28 (≈)
> 
> Suggested-by: Derrick Stolee <derrickstolee@github.com>
> Helped-by: Derrick Stolee <derrickstolee@github.com>
> Helped-by: Victoria Dye <vdye@github.com>
> Signed-off-by: Shaoxuan Yuan <shaoxuan.yuan02@gmail.com>
> ---
>  builtin/grep.c                    | 32 ++++++++++++++++++++++++++-----
>  t/perf/p2000-sparse-operations.sh |  1 +
>  2 files changed, 28 insertions(+), 5 deletions(-)
> 
> diff --git a/builtin/grep.c b/builtin/grep.c
> index a0b4dbc1dc..8c0edccd8e 100644
> --- a/builtin/grep.c
> +++ b/builtin/grep.c
> @@ -522,9 +522,6 @@ static int grep_cache(struct grep_opt *opt,
>  	if (repo_read_index(repo) < 0)
>  		die(_("index file corrupt"));
>  
> -	if (grep_sparse)
> -		ensure_full_index(repo->index);
> -
>  	for (nr = 0; nr < repo->index->cache_nr; nr++) {
>  		const struct cache_entry *ce = repo->index->cache[nr];
>  
> @@ -537,8 +534,26 @@ static int grep_cache(struct grep_opt *opt,
>  
>  		strbuf_setlen(&name, name_base_len);
>  		strbuf_addstr(&name, ce->name);
> +		if (S_ISSPARSEDIR(ce->ce_mode)) {
> +			enum object_type type;
> +			struct tree_desc tree;
> +			void *data;
> +			unsigned long size;
> +			struct strbuf base = STRBUF_INIT;
> +
> +			strbuf_addstr(&base, ce->name);
> +
> +			data = read_object_file(&ce->oid, &type, &size);
> +			init_tree_desc(&tree, data, size);
>  
> -		if (S_ISREG(ce->ce_mode) &&
> +			/*
> +			 * sneak in the ce_mode using check_attr parameter
> +			 */
> +			hit |= grep_tree(opt, pathspec, &tree, &base,
> +					 base.len, ce->ce_mode);
> +			strbuf_release(&base);
> +			free(data);
> +		} else if (S_ISREG(ce->ce_mode) &&
>  		    match_pathspec(repo->index, pathspec, name.buf, name.len, 0, NULL,
>  				   S_ISDIR(ce->ce_mode) ||
>  				   S_ISGITLINK(ce->ce_mode))) {
> @@ -598,7 +613,14 @@ static int grep_tree(struct grep_opt *opt, const struct pathspec *pathspec,
>  		int te_len = tree_entry_len(&entry);
>  
>  		if (match != all_entries_interesting) {
> -			strbuf_addstr(&name, base->buf + tn_len);
> +			if (S_ISSPARSEDIR(check_attr)) {
> +				// object is a sparse directory entry
> +				strbuf_addbuf(&name, base);
> +			} else {
> +				// object is a commit or a root tree
> +				strbuf_addstr(&name, base->buf + tn_len);
> +			}

Hmm, I'm not entirely sure I follow what's going on with 'name'. I'll try to
talk myself through it.

Stepping back a bit in the context of 'grep_tree()': the goal of the
function is, given a tree descriptor 'tree', to recursively scan the tree to
find any 'grep' matches within items matching 'pathspec'. It is also called
with a strbuf 'base', a length 'tn_len', and a boolean 'check_attr'; it's
not immediately clear to me what those args are or what they do. What I can
see is that:

- 'check_attr' is true iff the "tree" being grepped is actually a commit. 
- both non-recursive callers ('grep_object()' and 'grep_submodule()') call
  'grep_tree()' with 'tn_len == base.len'.

Stepping into 'grep_tree()', we iterate over the entries *inside of* 'tree'.
We assign the length of the tree entry's path to 'te_len'. Notably, a tree
entry's path *not* the path from the root of the repo to the entry - it's
just the filename of the entry (e.g., for entry 'folder1/a', the path is
'a').

Next, we skip the first 'tn_len' characters of 'base->buf' and assign that
value to 'name'. Because 'tn_len == base.len', for this first iteration,
it's an empty string. Then, we check if the tree entry is interesting with
path 'name'. But 'name' is an empty string, so 'tree_entry_interesting()'
thinks the tree entry is at the root of the repository, even if it isn't!

At this point, I think I've figured out what the deal with 'base' is. Before
this patch, only 'grep_object()' and 'grep_submodule()'. In the former case,
it's either "<objectname>:", or empty; in the latter, it's the path to the
submodule. Both of those are things you'd want to skip to get the correct
path to the tree entry for 'tree_entry_interesting()', but it isn't true in
your case; you need the path from the repository root to your tree for
'tree_entry_interesting()' to work properly. 

Based on all of that, I *think* you can drop the 'check_attr' changes to
'grep_tree()' and update how you provide 'base' and 'tn_len' so
1) 'base' is the path to the tree root, and 2) 'tn_len' is 0 so that full
path is provided to 'tree_entry_interesting()':

----->8----->8----->8----->8----->8----->8----->8----->8----->8----->8-----
diff --git a/builtin/grep.c b/builtin/grep.c
index 8c0edccd8e..85c83190f1 100644
--- a/builtin/grep.c
+++ b/builtin/grep.c
@@ -546,11 +546,7 @@ static int grep_cache(struct grep_opt *opt,
 			data = read_object_file(&ce->oid, &type, &size);
 			init_tree_desc(&tree, data, size);
 
-			/*
-			 * sneak in the ce_mode using check_attr parameter
-			 */
-			hit |= grep_tree(opt, pathspec, &tree, &base,
-					 base.len, ce->ce_mode);
+			hit |= grep_tree(opt, pathspec, &tree, &base, 0, 0);
 			strbuf_release(&base);
 			free(data);
 		} else if (S_ISREG(ce->ce_mode) &&
@@ -613,14 +609,6 @@ static int grep_tree(struct grep_opt *opt, const struct pathspec *pathspec,
 		int te_len = tree_entry_len(&entry);
 
 		if (match != all_entries_interesting) {
-			if (S_ISSPARSEDIR(check_attr)) {
-				// object is a sparse directory entry
-				strbuf_addbuf(&name, base);
-			} else {
-				// object is a commit or a root tree
-				strbuf_addstr(&name, base->buf + tn_len);
-			}
-
 			match = tree_entry_interesting(repo->index,
 						       &entry, &name,
 						       0, pathspec);
-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<----- 

I still find all of this confusing, and it's possible I'm still not properly
understanding how 'name' and 'tn_len' are supposed to be used. Regardless, I
*am* fairly certain that finding the right values for those args is the
going to be the cleanest (and least fragile) way to handle sparse
directories, rather than using the 'check_attr' arg for something it isn't.

It might take some time + lots of debugging/experimenting, but it's really
important that the implementation you settle on is something you (and,
ideally, the readers of your patches) confidently and completely understand,
rather than something that seems to work but doesn't have a clear
explanation. As always, I'm happy to help if you'd like another set of eyes
on the problem!

> +
>  			match = tree_entry_interesting(repo->index,
>  						       &entry, &name,
>  						       0, pathspec);
> diff --git a/t/perf/p2000-sparse-operations.sh b/t/perf/p2000-sparse-operations.sh
> index fce8151d41..a0b71bb3b4 100755
> --- a/t/perf/p2000-sparse-operations.sh
> +++ b/t/perf/p2000-sparse-operations.sh
> @@ -124,5 +124,6 @@ test_perf_on_all git read-tree -mu HEAD
>  test_perf_on_all git checkout-index -f --all
>  test_perf_on_all git update-index --add --remove $SPARSE_CONE/a
>  test_perf_on_all "git rm -f $SPARSE_CONE/a && git checkout HEAD -- $SPARSE_CONE/a"
> +test_perf_on_all git grep --cached --sparse bogus -- "f2/f1/f1/builtin/*"
>  
>  test_done