git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
Derrick Stolee <derrickstolee@github.com>
Date
Sep 1, 2022, 17:03 UTC
Message-ID
<e74b326d-ce4a-31c3-5424-e35858cdb569@github.com>
In-Reply-To
<20220901045736.523371-4-shaoxuan.yuan02@gmail.com>
On 9/1/2022 12:57 AM, Shaoxuan Yuan wrote:
Show 10 quoted lines
> 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.

Show 23 quoted lines
>  		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.

Show 16 quoted lines
>  		    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
Previous: Shaoxuan YuanNext: Shaoxuan Yuan
Message 24 of 69 in “grep: integrate with sparse index”
  1. 0/2 grep: integrate with sparse indexShaoxuan Yuan, Aug 17, 2022
  2. 1/2 builtin/grep.c: add --sparse optionShaoxuan Yuan, Aug 17, 2022
  3. Derrick StoleeAug 17, 2022
  4. Junio C HamanoAug 17, 2022
  5. Victoria DyeAug 17, 2022
  6. Derrick StoleeAug 17, 2022
  7. Junio C HamanoAug 17, 2022
  8. Elijah NewrenAug 17, 2022
  9. Shaoxuan YuanAug 24, 2022
  10. Derrick StoleeAug 24, 2022
  11. 2/2 builtin/grep.c: integrate with sparse indexShaoxuan Yuan, Aug 17, 2022
  12. Derrick StoleeAug 17, 2022
  13. Shaoxuan YuanAug 24, 2022
  14. Derrick StoleeAug 25, 2022
  15. Derrick StoleeAug 17, 2022
  16. 0/2 grep: integrate with sparse indexShaoxuan Yuan, Aug 29, 2022
  17. 2/2 builtin/grep.c: integrate with sparse indexShaoxuan Yuan, Aug 29, 2022
  18. Derrick StoleeAug 30, 2022
  19. 1/2 builtin/grep.c: add --sparse optionShaoxuan Yuan, Aug 29, 2022
  20. 0/3 grep: integrate with sparse indexShaoxuan Yuan, Sep 1, 2022
  21. 1/3 builtin/grep.c: add --sparse optionShaoxuan Yuan, Sep 1, 2022
  22. 2/3 builtin/grep.c: integrate with sparse indexShaoxuan Yuan, Sep 1, 2022
  23. 3/3 builtin/grep.c: walking tree instead of expanding index with --sparseShaoxuan Yuan, Sep 1, 2022
  24. Derrick StoleeSep 1, 2022
  25. Shaoxuan YuanSep 1, 2022
  26. Junio C HamanoSep 1, 2022
  27. Junio C HamanoSep 1, 2022
  28. Shaoxuan YuanSep 1, 2022
  29. Shaoxuan YuanSep 1, 2022
  30. Victoria DyeSep 2, 2022
  31. Shaoxuan YuanSep 2, 2022
  32. 0/3 grep: integrate with sparse indexShaoxuan Yuan, Sep 3, 2022
  33. 1/3 builtin/grep.c: add --sparse optionShaoxuan Yuan, Sep 3, 2022
  34. 2/3 builtin/grep.c: integrate with sparse indexShaoxuan Yuan, Sep 3, 2022
  35. 3/3 builtin/grep.c: walking tree instead of expanding index with --sparseShaoxuan Yuan, Sep 3, 2022
  36. Junio C HamanoSep 3, 2022
  37. Shaoxuan YuanSep 8, 2022
  38. 0/3 grep: integrate with sparse indexShaoxuan Yuan, Sep 8, 2022
  39. 1/3 builtin/grep.c: add --sparse optionShaoxuan Yuan, Sep 8, 2022
  40. Victoria DyeSep 10, 2022
  41. Elijah NewrenSep 14, 2022
  42. Junio C HamanoSep 15, 2022
  43. Elijah NewrenSep 18, 2022
  44. Victoria DyeSep 18, 2022
  45. Junio C HamanoSep 19, 2022
  46. Shaoxuan YuanSep 19, 2022
  47. Ævar Arnfjörð BjarmasonSep 19, 2022
  48. Elijah NewrenSep 20, 2022
  49. Shaoxuan YuanSep 17, 2022
  50. Elijah NewrenSep 18, 2022
  51. Shaoxuan YuanSep 19, 2022
  52. Shaoxuan YuanSep 17, 2022
  53. 2/3 builtin/grep.c: integrate with sparse indexShaoxuan Yuan, Sep 8, 2022
  54. 3/3 builtin/grep.c: walking tree instead of expanding index with --sparseShaoxuan Yuan, Sep 8, 2022
  55. Junio C HamanoSep 8, 2022
  56. Derrick StoleeSep 8, 2022
  57. Junio C HamanoSep 8, 2022
  58. Shaoxuan YuanSep 8, 2022
  59. Derrick StoleeSep 9, 2022
  60. Junio C HamanoSep 13, 2022
  61. Victoria DyeSep 10, 2022
  62. 0/1 grep: integrate with sparse indexShaoxuan Yuan, Sep 23, 2022
  63. 1/1 builtin/grep.c: integrate with sparse indexShaoxuan Yuan, Sep 23, 2022
  64. Junio C HamanoSep 23, 2022
  65. Junio C HamanoSep 23, 2022
  66. Junio C HamanoSep 26, 2022
  67. Derrick StoleeSep 23, 2022
  68. Victoria DyeSep 23, 2022
  69. Junio C HamanoSep 23, 2022

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.