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

[Derrick Stolee <derrickstolee@github.com>]

On 9/1/2022 12:57 AM, Shaoxuan Yuan wrote: 
> 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%)
> 
> - Command used for testing:
> 
> 	git grep --cached --sparse bogus -- f2/f1/f1/builtin/*

It's good to list this command after the table. It allows you to shrink
the table by using "...":

Test                                HEAD~   HEAD
---------------------------------------------------------
2000.78: git grep ... (full-v3)     0.11    0.09 (≈)
2000.79: git grep ... (full-v4)     0.08    0.09 (≈)
2000.80: git grep ... (sparse-v3)   0.44    0.04 (-90.9%)
2000.81: git grep ... (sparse-v4)   0.46    0.04 (-91.3%)

This saves horizontal space without losing clarity. The test numbers help,
too.

>  		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) &&

I think this is a good setup for transitioning from the index scan
to the tree-walking grep_tree() method. Below, I recommend calling
the method slightly differently, though.

>  		    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);
> +			}
> +

I think this is abusing the check_attr too much, since this will also
trigger a different if branch further down the method.

These lines are the same if tn_len is zero, so will it suffice to pass
0 for that length? You are passing base.len when you call it, so maybe
that should be zero?

When I apply this change, all tests pass, so if there _is_ something
different between the two implementations, then it isn't covered by
tests:

diff --git a/builtin/grep.c b/builtin/grep.c
index 8c0edccd8e..fc4adf876a 100644
--- a/builtin/grep.c
+++ b/builtin/grep.c
@@ -549,8 +549,7 @@ static int grep_cache(struct grep_opt *opt,
 			/*
 			 * 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,13 +612,7 @@ 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);
-			}
+			strbuf_addstr(&name, base->buf + tn_len);
 
 			match = tree_entry_interesting(repo->index,
 						       &entry, &name,

> +test_perf_on_all git grep --cached --sparse bogus -- "f2/f1/f1/builtin/*"

We can't use this path in general, because we don't always run the test
using the Git repository as the test repo (see GIT_PERF_[LARGE_]REPO
variables in t/perf/README).

We _can_ however use the structure that we have implied in our construction,
which is to use a path that we know exists and is still outside of the
sparse-checkout cone. Truncating to "f2/f1/f1/*" is sufficient for this.

Modifying the test and running them on my machine, I get:

Test                               HEAD~1            HEAD
----------------------------------------------------------------------------
2000.78: git grep ... (full-v3)    0.19(0.72+0.18)   0.18(0.84+0.13) -5.3%  
2000.79: git grep ... (full-v4)    0.17(0.83+0.16)   0.19(0.84+0.14) +11.8% 
2000.80: git grep ... (sparse-v3)  0.35(1.02+0.13)   0.15(0.85+0.15) -57.1% 
2000.81: git grep ... (sparse-v4)  0.37(1.06+0.12)   0.15(0.89+0.15) -59.5%

So, it's still expensive to do the blob search over a wider pathspec than
the test as you designed it, but this will work for other repo, such as the
Linux kernel:

Test                                HEAD~1             HEAD
------------------------------------------------------------------------------
2000.78: git grep ... (full-v3)     3.16(19.37+2.55)   2.56(15.24+1.76) -19.0%
2000.79: git grep ... (full-v4)     2.97(17.84+2.00)   2.59(15.51+1.89) -12.8%
2000.80: git grep ... (sparse-v3)   8.39(24.74+2.34)   2.13(16.03+1.72) -74.6%
2000.81: git grep ... (sparse-v4)   8.39(24.73+2.40)   2.16(16.14+1.90) -74.3%

Thanks,
-Stolee