| Message ID | 20220908001854.206789-4-shaoxuan.yuan02@gmail.com (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | grep: integrate with sparse index | expand |
Shaoxuan Yuan <shaoxuan.yuan02@gmail.com> writes: > + > + /* > + * NEEDSWORK: when reading a submodule, the sparsity settings in the > + * superproject are incorrectly forgotten or misused. For example: > + * > + * 1. "command_requires_full_index" > + * When this setting is turned on for `grep`, only the superproject > + * knows it. All the submodules are read with their own configs > + * and get prepare_repo_settings()'d. Therefore, these submodules > + * "forget" the sparse-index feature switch. As a result, the index > + * of these submodules are expanded unexpectedly. Is this fundamental, or is it just this version of the patch is incomplete in that it still does not propagate the bit from the_repository->settings to submodule's settings? Should a change to propagate the bit be included for this topic to be complete? To put it another way, when grep with this version of the patch recurses into a submodule, does it work correctly even without flipping command_requires_full_index on in the "struct repository" instance for the submodule? If so, then the NEEDSWORK above may be just performance issue. If it behaves incorrectly, then it means we cannot safely make "git grep" aware of sparse index yet. It is hard to tell which one you meant in the above. I think the same question needs to be asked for other points (omitted from quoting) in this list. Thanks.
On 9/8/2022 1:59 PM, Junio C Hamano wrote: > Shaoxuan Yuan <shaoxuan.yuan02@gmail.com> writes: > >> + >> + /* >> + * NEEDSWORK: when reading a submodule, the sparsity settings in the >> + * superproject are incorrectly forgotten or misused. For example: >> + * >> + * 1. "command_requires_full_index" >> + * When this setting is turned on for `grep`, only the superproject >> + * knows it. All the submodules are read with their own configs >> + * and get prepare_repo_settings()'d. Therefore, these submodules >> + * "forget" the sparse-index feature switch. As a result, the index >> + * of these submodules are expanded unexpectedly. > > Is this fundamental, or is it just this version of the patch is > incomplete in that it still does not propagate the bit from > the_repository->settings to submodule's settings? Should a change > to propagate the bit be included for this topic to be complete? > > To put it another way, when grep with this version of the patch > recurses into a submodule, does it work correctly even without > flipping command_requires_full_index on in the "struct repository" > instance for the submodule? If so, then the NEEDSWORK above may be > just performance issue. If it behaves incorrectly, then it means > we cannot safely make "git grep" aware of sparse index yet. It is > hard to tell which one you meant in the above. > > I think the same question needs to be asked for other points > (omitted from quoting) in this list. I think this comment is misplaced. It should either be contained in the commit message or placed closer to this diff hunk: >> @@ -537,8 +561,20 @@ 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; >> + >> + data = read_object_file(&ce->oid, &type, &size); >> + init_tree_desc(&tree, data, size); >> >> - if (S_ISREG(ce->ce_mode) && >> + hit |= grep_tree(opt, pathspec, &tree, &name, 0, 0); >> + strbuf_setlen(&name, name_base_len); >> + strbuf_addstr(&name, ce->name); >> + free(data); >> + } else if (S_ISREG(ce->ce_mode) && The conclusion we were trying to reach is that you (Junio) correctly identified a bug in how we were calling grep_tree() in this hunk in its v4 form. HOWEVER: it "doesn't matter" because the sparse index doesn't work at all within a submodule. Specifically, if a super-repo does not enable sparse-checkout, but the submodule _does_, then we don't know how Git will behave currently. His reasonings go on to explain why the situation is fraught: * command_requires_full_index is set in a builtin only for the top-level project, so when we traverse into a submodule, we don't re-check if the current builtin has integrated with sparse index and expand a sparse index to a full one. * core_apply_sparse_checkout is a global not even associated with a repository struct. What happens when a super project is not sparse but a submodule is? Or vice-versa? I honestly don't know, and it will require testing to find out. Shaoxuan's comment is attempting to list the reasons why submodules do not currently work with sparse-index, and specifically that we can add tests that _should_ exercise this code in a meaningful way, but because of the current limitations of the codebase, the code isn't actually exercised in that scenario. In order to actually create a test that demonstrates how submodules and sparse-checkout work with this logic, we need to do some serious refactoring of the sparse-checkout logic to care about the repository struct, along with some other concerns specifically around the sparse index. This doesn't seem appropriate for the GSoC timeline or even for just this topic. Victoria and I have noted this issue down and will try to find time to investigate further, with a target of being able to actually exercise this grep_tree() call within a sparse index in a submodule, giving us full confidence that name_base_len is the correct value to put in that parameter. Thanks, -Stolee
Derrick Stolee <derrickstolee@github.com> writes: > HOWEVER: it "doesn't matter" because the sparse index doesn't work > at all within a submodule. Specifically, if a super-repo does not > enable sparse-checkout, but the submodule _does_, then we don't > know how Git will behave currently. His reasonings go on to explain > why the situation is fraught: > > * command_requires_full_index is set in a builtin only for the > top-level project, so when we traverse into a submodule, we don't > re-check if the current builtin has integrated with sparse index > and expand a sparse index to a full one. Correct. Is it sufficient to propagate the bit from the_repository->settings to repo->settings of the submodule, or is there more things needed to fix it? > * core_apply_sparse_checkout is a global not even associated with > a repository struct. What happens when a super project is not > sparse but a submodule is? Or vice-versa? I honestly don't know, > and it will require testing to find out. Naïvely, I would think that we should just treat a non-sparse case as a mere specialization where the sparse cone covers everything, but there may be pitfalls. > Shaoxuan's comment is attempting to list the reasons why submodules > do not currently work with sparse-index, "do not currently work" in a sense that it produces wrong result, or it just expands in-core index unnecessarily before applying pathspec to produce the right result in an inefficient way? If it is "functionally broken", is there a simple way out to give us correct result even if it becomes less efficient? Like "we scan the index and we see we have some submodules---so we disable the sparse handling"? > Victoria and I have noted this issue down and will try to find time > to investigate further, with a target of being able to actually > exercise this grep_tree() call within a sparse index in a submodule, > giving us full confidence that name_base_len is the correct value to > put in that parameter. OK.
On 9/8/2022 1:56 PM, Junio C Hamano wrote: >> Shaoxuan's comment is attempting to list the reasons why submodules >> do not currently work with sparse-index, > > "do not currently work" in a sense that it produces wrong result, or > it just expands in-core index unnecessarily before applying pathspec > to produce the right result in an inefficient way? It's the latter situation. It expands the index inefficiently though, the results are correct. The other problem is that, there is no sparse directories in an expanded index, thus we cannot test how does the grep_tree() approach (introduced in the third patch) work within submodules.
On 9/8/2022 4:56 PM, Junio C Hamano wrote: > Derrick Stolee <derrickstolee@github.com> writes: > >> HOWEVER: it "doesn't matter" because the sparse index doesn't work >> at all within a submodule. Specifically, if a super-repo does not >> enable sparse-checkout, but the submodule _does_, then we don't >> know how Git will behave currently. His reasonings go on to explain >> why the situation is fraught: >> >> * command_requires_full_index is set in a builtin only for the >> top-level project, so when we traverse into a submodule, we don't >> re-check if the current builtin has integrated with sparse index >> and expand a sparse index to a full one. > > Correct. > > Is it sufficient to propagate the bit from the_repository->settings > to repo->settings of the submodule, or is there more things needed > to fix it? Likely that would suffice, but before we do that, we need to add a lot of tests to be sure our previous sparse index integrations do the right thing when within submodules. >> * core_apply_sparse_checkout is a global not even associated with >> a repository struct. What happens when a super project is not >> sparse but a submodule is? Or vice-versa? I honestly don't know, >> and it will require testing to find out. > > Naïvely, I would think that we should just treat a non-sparse case > as a mere specialization where the sparse cone covers everything, > but there may be pitfalls. I worry about how this works if the super-project and the submodule differ in the core.sparseCheckout config, but both have sparse-checkout files. Will one or the other cause the sparse-checkout patterns to be enabled despite the repo-local config? I honestly have no idea, and I don't think we have tests that protect this scenario. That's the kind of direction I would start in this investigation. Thanks, -Stolee
Shaoxuan Yuan wrote: > + > + /* > + * NEEDSWORK: when reading a submodule, the sparsity settings in the > + * superproject are incorrectly forgotten or misused. For example: > + * > + * 1. "command_requires_full_index" > + * When this setting is turned on for `grep`, only the superproject > + * knows it. All the submodules are read with their own configs > + * and get prepare_repo_settings()'d. Therefore, these submodules > + * "forget" the sparse-index feature switch. As a result, the index > + * of these submodules are expanded unexpectedly. > + * > + * 2. "core_apply_sparse_checkout" > + * When running `grep` in the superproject, this setting is > + * populated using the superproject's configs. However, once > + * initialized, this config is globally accessible and is read by > + * prepare_repo_settings() for the submodules. For instance, if a > + * submodule is using a sparse-checkout, however, the superproject > + * is not, the result is that the config from the superproject will > + * dictate the behavior for the submodule, making it "forget" its > + * sparse-checkout state. > + * > + * 3. "core_sparse_checkout_cone" > + * ditto. These are interesting observations, thank you for describing the behavior in detail. - #1 might seem like an easy fix - since 'command_requires_full_index' is tied to the command (not properties of the repo), the logical thing to do would be to propagate the value from the superproject to the subproject. However, that fix will undoubtedly expose lots of places where we're not handling the sparse index correctly in submodules. Since this isn't a problem introduced by your patch series, I'm content leaving this for a later series. - #2 is an odd situation, but I'm guessing that the effect here will be minimal (since, regardless of the 'core_*' sparse-checkout globals, 'SKIP_WORKTREE' will still be applied to - and respected on - entries in the index). It's more worrisome for commands that recurse submodules and *write* the index (e.g., 'git read-tree'), but that's also outside the scope of this series. Given this information, I think your approach is (for the time being) a safe one. Beyond the submodule issues, I'm happy with the rest of your 'grep_tree()' updates. > diff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh > index 63becc3138..fda05faadf 100755 > --- a/t/t1092-sparse-checkout-compatibility.sh > +++ b/t/t1092-sparse-checkout-compatibility.sh > @@ -1987,7 +2000,48 @@ test_expect_success 'grep is not expanded' ' > > # All files within the folder1/* pathspec are sparse, > # so this command does not find any matches > - ensure_not_expanded ! grep a -- folder1/* > + ensure_not_expanded ! grep a -- folder1/* && > + > + # test out-of-cone pathspec with or without wildcard > + ensure_not_expanded grep --sparse --cached a -- "folder1/a" && > + ensure_not_expanded grep --sparse --cached a -- "folder1/*" && > + > + # test in-cone pathspec with or without wildcard > + ensure_not_expanded grep --sparse --cached a -- "deep/a" && > + ensure_not_expanded grep --sparse --cached a -- "deep/*" Thanks for the new tests (re: [1])! [1] https://lore.kernel.org/git/4b65d7dc-e711-43a6-8763-62be79a3e4a9@github.com/ > +' > + > +# NEEDSWORK: when running `grep` in the superproject with --recurse-submodules, > +# Git expands the index of the submodules unexpectedly. Even though `grep` > +# builtin is marked as "command_requires_full_index = 0", this config is only > +# useful for the superproject. Namely, the submodules have their own configs, > +# which are _not_ populated by the one-time sparse-index feature switch. > +test_expect_failure 'grep within submodules is not expanded' ' > + init_repos_as_submodules && > + > + # do not use ensure_not_expanded() here, becasue `grep` should be > + # run in the superproject, not in "./sparse-index" > + GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \ > + git grep --sparse --cached --recurse-submodules a -- "*/folder1/*" && > + test_region ! index ensure_full_index trace2.txt > +' So this test is *only* demonstrating that the submodules' indexes are expanded (incorrectly, hence the 'test_expect_failure'); it doesn't show that 'git grep' returns the correct results... > + > +# NEEDSWORK: this test is not actually testing the code. The design purpose > +# of this test is to verify the grep result when the submodules are using a > +# sparse-index. Namely, we want "folder1/" as a tree (a sparse directory); but > +# because of the index expansion, we are now grepping the "folder1/a" blob. > +# Because of the problem stated above 'grep within submodules is not expanded', > +# we don't have the ideal test environment yet. > +test_expect_success 'grep sparse directory within submodules' ' > + init_repos_as_submodules && > + > + cat >expect <<-\EOF && > + full-checkout/folder1/a:a > + sparse-checkout/folder1/a:a > + sparse-index/folder1/a:a > + EOF > + git grep --sparse --cached --recurse-submodules a -- "*/folder1/*" >actual && > + test_cmp actual expect > ' ...but this test *does* show that those results are correct. I think it was a good decision to keep the two separate, since only the index expansion behavior is wrong (thus warranting the 'test_expect_failure'). The output of 'git grep' is still what we want it to be, so it gets a 'test_expect_success'. > > test_done
Derrick Stolee <derrickstolee@github.com> writes: > On 9/8/2022 1:59 PM, Junio C Hamano wrote: >> Shaoxuan Yuan <shaoxuan.yuan02@gmail.com> writes: >> >>> + >>> + /* >>> + * NEEDSWORK: when reading a submodule, the sparsity settings in the >>> + * superproject are incorrectly forgotten or misused. For example: >>> + * >>> + * 1. "command_requires_full_index" >>> + * When this setting is turned on for `grep`, only the superproject >>> + * knows it. All the submodules are read with their own configs >>> + * and get prepare_repo_settings()'d. Therefore, these submodules >>> + * "forget" the sparse-index feature switch. As a result, the index >>> + * of these submodules are expanded unexpectedly. >> ... > I think this comment is misplaced. It should either be contained in > the commit message or placed closer to this diff hunk: OK, so given what you wrote below, except for such a minor shuffling, the current series is ready to go? Thanks. > ... > Shaoxuan's comment is attempting to list the reasons why submodules > do not currently work with sparse-index, and specifically that we > can add tests that _should_ exercise this code in a meaningful way, > but because of the current limitations of the codebase, the code > isn't actually exercised in that scenario. > > In order to actually create a test that demonstrates how submodules > and sparse-checkout work with this logic, we need to do some serious > refactoring of the sparse-checkout logic to care about the repository > struct, along with some other concerns specifically around the sparse > index. This doesn't seem appropriate for the GSoC timeline or even for > just this topic.
diff --git a/builtin/grep.c b/builtin/grep.c index a0b4dbc1dc..9a01932253 100644 --- a/builtin/grep.c +++ b/builtin/grep.c @@ -460,6 +460,33 @@ static int grep_submodule(struct grep_opt *opt, * subrepo's odbs to the in-memory alternates list. */ obj_read_lock(); + + /* + * NEEDSWORK: when reading a submodule, the sparsity settings in the + * superproject are incorrectly forgotten or misused. For example: + * + * 1. "command_requires_full_index" + * When this setting is turned on for `grep`, only the superproject + * knows it. All the submodules are read with their own configs + * and get prepare_repo_settings()'d. Therefore, these submodules + * "forget" the sparse-index feature switch. As a result, the index + * of these submodules are expanded unexpectedly. + * + * 2. "core_apply_sparse_checkout" + * When running `grep` in the superproject, this setting is + * populated using the superproject's configs. However, once + * initialized, this config is globally accessible and is read by + * prepare_repo_settings() for the submodules. For instance, if a + * submodule is using a sparse-checkout, however, the superproject + * is not, the result is that the config from the superproject will + * dictate the behavior for the submodule, making it "forget" its + * sparse-checkout state. + * + * 3. "core_sparse_checkout_cone" + * ditto. + * + * Note that this list is not exhaustive. + */ repo_read_gitmodules(subrepo, 0); /* @@ -522,9 +549,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 +561,20 @@ 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; + + data = read_object_file(&ce->oid, &type, &size); + init_tree_desc(&tree, data, size); - if (S_ISREG(ce->ce_mode) && + hit |= grep_tree(opt, pathspec, &tree, &name, 0, 0); + strbuf_setlen(&name, name_base_len); + strbuf_addstr(&name, ce->name); + 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))) { diff --git a/t/perf/p2000-sparse-operations.sh b/t/perf/p2000-sparse-operations.sh index fce8151d41..3242cfe91a 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/*" test_done diff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh index 63becc3138..fda05faadf 100755 --- a/t/t1092-sparse-checkout-compatibility.sh +++ b/t/t1092-sparse-checkout-compatibility.sh @@ -162,6 +162,19 @@ init_repos () { git -C sparse-index sparse-checkout set deep } +init_repos_as_submodules () { + git reset --hard && + init_repos && + git submodule add ./full-checkout && + git submodule add ./sparse-checkout && + git submodule add ./sparse-index && + + git submodule status >actual && + grep full-checkout actual && + grep sparse-checkout actual && + grep sparse-index actual +} + run_on_sparse () { ( cd sparse-checkout && @@ -1987,7 +2000,48 @@ test_expect_success 'grep is not expanded' ' # All files within the folder1/* pathspec are sparse, # so this command does not find any matches - ensure_not_expanded ! grep a -- folder1/* + ensure_not_expanded ! grep a -- folder1/* && + + # test out-of-cone pathspec with or without wildcard + ensure_not_expanded grep --sparse --cached a -- "folder1/a" && + ensure_not_expanded grep --sparse --cached a -- "folder1/*" && + + # test in-cone pathspec with or without wildcard + ensure_not_expanded grep --sparse --cached a -- "deep/a" && + ensure_not_expanded grep --sparse --cached a -- "deep/*" +' + +# NEEDSWORK: when running `grep` in the superproject with --recurse-submodules, +# Git expands the index of the submodules unexpectedly. Even though `grep` +# builtin is marked as "command_requires_full_index = 0", this config is only +# useful for the superproject. Namely, the submodules have their own configs, +# which are _not_ populated by the one-time sparse-index feature switch. +test_expect_failure 'grep within submodules is not expanded' ' + init_repos_as_submodules && + + # do not use ensure_not_expanded() here, becasue `grep` should be + # run in the superproject, not in "./sparse-index" + GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \ + git grep --sparse --cached --recurse-submodules a -- "*/folder1/*" && + test_region ! index ensure_full_index trace2.txt +' + +# NEEDSWORK: this test is not actually testing the code. The design purpose +# of this test is to verify the grep result when the submodules are using a +# sparse-index. Namely, we want "folder1/" as a tree (a sparse directory); but +# because of the index expansion, we are now grepping the "folder1/a" blob. +# Because of the problem stated above 'grep within submodules is not expanded', +# we don't have the ideal test environment yet. +test_expect_success 'grep sparse directory within submodules' ' + init_repos_as_submodules && + + cat >expect <<-\EOF && + full-checkout/folder1/a:a + sparse-checkout/folder1/a:a + sparse-index/folder1/a:a + EOF + git grep --sparse --cached --recurse-submodules a -- "*/folder1/*" >actual && + test_cmp actual expect ' 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 ~71% execution time reduction for `git grep --cached --sparse bogus -- "f2/f1/f1/*"` using tree-walking logic. However, notice that this result varies depending on the pathspec given. See below "Command used for testing" for more details. Test HEAD~ HEAD ------------------------------------------------------- 2000.78: git grep ... (full-v3) 0.35 0.39 (≈) 2000.79: git grep ... (full-v4) 0.36 0.30 (≈) 2000.80: git grep ... (sparse-v3) 0.88 0.23 (-73.8%) 2000.81: git grep ... (sparse-v4) 0.83 0.26 (-68.6%) - Command used for testing: git grep --cached --sparse bogus -- "f2/f1/f1/*" 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. Generally speaking, because the performance gain is acheived by walking less trees, which are specified by the pathspec, the HEAD time v.s. HEAD~ time in sparse-v[3|4], should be proportional to "pathspec enclosed area" v.s. "all area", respectively. Namely, the wider the <pathspec> is encompassing, the less the performance difference between HEAD~ and HEAD, and vice versa. That is, if we don't specify a pathspec, the performance difference [1] is indistinguishable: 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 (hence walking all trees): Command used: git grep --cached --sparse bogus Test HEAD~ HEAD --------------------------------------------------- 2000.78: git grep ... (full-v3) 6.17 5.19 (≈) 2000.79: git grep ... (full-v4) 6.19 5.46 (≈) 2000.80: git grep ... (sparse-v3) 6.57 6.44 (≈) 2000.81: git grep ... (sparse-v4) 6.65 6.28 (≈) -------------------------- NEEDSWORK about submodules There are a few NEEDSWORKs that belong to improvements beyond this topic. See the NEEDSWORK in builtin/grep.c::grep_submodule() for more context. The other two NEEDSWORKs in t1092 are also relative. 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 | 44 +++++++++++++++++-- t/perf/p2000-sparse-operations.sh | 1 + t/t1092-sparse-checkout-compatibility.sh | 56 +++++++++++++++++++++++- 3 files changed, 96 insertions(+), 5 deletions(-)