| Message ID | 20220901045736.523371-4-shaoxuan.yuan02@gmail.com (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | grep: integrate with sparse index | expand |
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
Shaoxuan Yuan <shaoxuan.yuan02@gmail.com> writes: > 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. When you encounter a "sparsedir" (i.e. a tree recorded in index), you should know the path leading to that directory. Even though I no longer remember the details of the implementations of grep_$where() which I did long time ago, I think grep_tree() should know how to pass the leading path down, as that is the most natural way to implement the recursive behaviour. This patch should be able to piggyback on that. > @@ -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); > > + /* > + * sneak in the ce_mode using check_attr parameter > + */ > + hit |= grep_tree(opt, pathspec, &tree, &base, > + base.len, ce->ce_mode); OK. Instead of inventing a new "base" strbuf, we could reuse existing name while running the grep_tree() and restore it after it returns, and I suspect that the end result would be more in line with how grep_cache() uses that "name" buffer for all the cache entries. But that is not a correctness issue (it is move about preventing from making the code worse). > @@ -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 No // comments, please.
Junio C Hamano <gitster@pobox.com> writes: > Shaoxuan Yuan <shaoxuan.yuan02@gmail.com> writes: > >> 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. > > When you encounter a "sparsedir" (i.e. a tree recorded in index), > you should know the path leading to that directory. Even though I no > longer remember the details of the implementations of grep_$where() > which I did long time ago, I think grep_tree() should know how to > pass the leading path down, as that is the most natural way to > implement the recursive behaviour. This patch should be able to > piggyback on that. To avoid unnecessary scare, the above is just me "thinking aloud", after reading the proposed log message, and agreeing with the direction taken by this patch. Not giving a suggestion to go different route or anything like that. I should have said "OK" or something at the end of the paragraph. Thanks for working on this topic.
On 9/1/2022 10:03 AM, Derrick Stolee wrote: > 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 "...": OK. > > 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. Yeah that's why I wrote "sneak in". > 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? Agree. > 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: I think they are no difference between these two implementations, at least according to my intention. > 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. OK. > 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: Yes, I was trying to use a narrower pathspec to show a difference that looks better. > 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 Thanks, Shaoxuan
On 9/1/2022 10:17 AM, Junio C Hamano wrote: > Shaoxuan Yuan <shaoxuan.yuan02@gmail.com> writes: > >> 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. > > When you encounter a "sparsedir" (i.e. a tree recorded in index), > you should know the path leading to that directory. Even though I no > longer remember the details of the implementations of grep_$where() > which I did long time ago, I think grep_tree() should know how to > pass the leading path down, as that is the most natural way to > implement the recursive behaviour. This patch should be able to > piggyback on that. Yes, though this commit [1] from 6 years ago started to assume that grep_tree() only accepts root tree or commit, so the function fails to process a tree like "sparsedir". It's the pathspec matching base that was messed up. The support for a tree that is not at root-level was added in this series. [1] 74ed43711fd1cd7ce155d338f87ebe52cb74d9e2 >> @@ -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); >> >> + /* >> + * sneak in the ce_mode using check_attr parameter >> + */ >> + hit |= grep_tree(opt, pathspec, &tree, &base, >> + base.len, ce->ce_mode); > > OK. Instead of inventing a new "base" strbuf, we could reuse > existing name while running the grep_tree() and restore it after it > returns, and I suspect that the end result would be more in line > with how grep_cache() uses that "name" buffer for all the cache > entries. But that is not a correctness issue (it is move about > preventing from making the code worse). Oh right, thanks for the suggestion! >> @@ -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 > > No // comments, please. OK. Thanks, Shaoxuan
On 9/1/2022 10:27 AM, Junio C Hamano wrote: > Junio C Hamano <gitster@pobox.com> writes: > >> Shaoxuan Yuan <shaoxuan.yuan02@gmail.com> writes: >> >>> 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. >> >> When you encounter a "sparsedir" (i.e. a tree recorded in index), >> you should know the path leading to that directory. Even though I no >> longer remember the details of the implementations of grep_$where() >> which I did long time ago, I think grep_tree() should know how to >> pass the leading path down, as that is the most natural way to >> implement the recursive behaviour. This patch should be able to >> piggyback on that. > > To avoid unnecessary scare, the above is just me "thinking aloud", > after reading the proposed log message, and agreeing with the > direction taken by this patch. Not giving a suggestion to go > different route or anything like that. I should have said "OK" or > something at the end of the paragraph. > > Thanks for working on this topic. Thank you! :-)
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
On 9/1/2022 8:28 PM, Victoria Dye wrote: > 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. Sure! >> >> ---------------- >> 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 I was confused for quite a while about the meaning of these args, too. I think 'base' is the object's ref or SHA, e.g. HEAD, HEAD~, or a <SHA>. Before this patch, the object was expected to be a root tree or a commit. I _think_ 'base' can also be "<submodule>/", e.g. "sub/" when grepping a submodule. 'tn_len' stands for "tree_name_len"? 'check_attr', as you wrote below, is for "commit or not", at lease that was all its use case before this patch. > see is that: > > - 'check_attr' is true iff the "tree" being grepped is actually a commit. I think this is correct. Though as Derrick Stolee said here [1], this patch is abusing the 'check_attr' (passing 'ce_mode' through it), and if that caused any confusions, my apologies. [1] https://lore.kernel.org/git/e74b326d-ce4a-31c3-5424-e35858cdb569@github.com > - 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'). Yes. > 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! Yes, that is the reason why it kept ignoring sub-root-level trees: the pathspec can never match a tree that is not at root level if this root-level assumption exists. > 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 Yep, this resonates with my reply above! > 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. Well said! I think this phrasing is very accurate. > 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<----- Thank you for this diff! I think this is also what Derrick suggested in his review. In fact, this approach is more to the root of the problem: the expected format of the path/base. > 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. Right. > 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! Right. I admit that the approach I was taking is pretty shady. The way suggested by you and Derrick is more explainable and to-the-point. Lesson learned! Thanks, Shaoxuan
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); + } + 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
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(-)