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

> 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.

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

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

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