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