| Message ID | 20220817075633.217934-3-shaoxuan.yuan02@gmail.com (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | grep: integrate with sparse index | expand |
On 8/17/2022 3:56 AM, Shaoxuan Yuan wrote: > Turn on sparse index and remove ensure_full_index(). > > Change it to only expands the index when using --sparse. > > The p2000 tests demonstrate a ~99.4% execution time reduction for > `git grep` using a sparse index. > > Test HEAD~1 HEAD > ----------------------------------------------------------------------------- > 2000.78: git grep --cached bogus (full-v3) 0.019 0.018 (-5.2%) > 2000.79: git grep --cached bogus (full-v4) 0.017 0.016 (-5.8%) > 2000.80: git grep --cached bogus (sparse-v3) 0.29 0.0015 (-99.4%) > 2000.81: git grep --cached bogus (sparse-v4) 0.30 0.0018 (-99.4%) Good results. I think we could get interesting results even with the --sparse option if you go another step further (perhaps as a patch after this one). > > Optional reading about performance test results > ----------------------------------------------- > Notice that because `git-grep` needs to parse blobs in the index, the > index reading time is minuscule comparing to the object parsing time. > And because of this, the p2000 test results cannot clearly reflect the > speedup for index reading: combining with the object parsing time, > the aggregated time difference is extremely close between HEAD~1 and > HEAD. > > Hence, the results presenting here are not directly extracted from the > p2000 test results. Instead, to make the performance difference more > visible, the test command is manually ran with GIT_TRACE2_PERF in the > four repos (full-v3, sparse-v3, full-v4, sparse-v4). The numbers here > are then extracted from the time difference between "region_enter" and > "region_leave" of label "do_read_index". This is a good point, but I don't recommend displaying them as if they were the output of a "./run HEAD~1 HEAD -- p2000-sparse-operations.sh" command. Instead, point out that the performance test does not show a major improvement and instead you have these "Before" and "After" results from testing manually and extracting trace2 regions. > @@ -519,11 +519,15 @@ static int grep_cache(struct grep_opt *opt, > strbuf_addstr(&name, repo->submodule_prefix); > } > > + prepare_repo_settings(repo); > + repo->settings.command_requires_full_index = 0; > + The best pattern is to put this in cmd_grep() immediately after parsing options. This guarantees that we don't parse and expand the index in any other code path. > if (repo_read_index(repo) < 0) > die(_("index file corrupt")); > > - /* TODO: audit for interaction with sparse-index. */ > - ensure_full_index(repo->index); > + if (grep_sparse) > + ensure_full_index(repo->index); > + As mentioned before, this approach is the simplest way to make the case without --sparse faster, but the case _with_ --sparse will still be slow. The way to fix this would be to modify this portion of the loop: 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))) { by adding an initial case if (S_ISSPARSEDIR(ce->ce_mode)) { hit |= grep_tree(opt, &ce->oid, name.buf, 0, name.buf); } 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))) { and appropriately implement "grep_tree()" to walk the tree at ce->oid to find all matching files within, then call grep_oid() for each of those paths. Bonus points if you recognize that the pathspec uses prefix checks that allow pruning the search space and not parsing all of the trees recursively. But that can definitely be delayed for a future enhancement. > +test_expect_success 'grep expands index using --sparse' ' > + init_repos && > + > + # With --sparse and --cached, do not ignore sparse entries and > + # expand the index. > + test_all_match git grep --sparse --cached a > +' Here, you're testing that the behavior matches, but not testing that the index expands. (It does describe why you didn't include it in the later ensure_not_expanded tests.) > + > +test_expect_success 'grep is not expanded' ' > + init_repos && > + > + ensure_not_expanded grep a && > + ensure_not_expanded grep a -- deep/* && > + # grep does not match anything per se, so ! is used It can be helpful to say why: # All files within the folder1/* pathspec are sparse, # so this command does not find any matches. > + ensure_not_expanded ! grep a -- folder1/* > +' Thanks, -Stolee
On 8/17/2022 10:23 PM, Derrick Stolee wrote: > On 8/17/2022 3:56 AM, Shaoxuan Yuan wrote: >> Turn on sparse index and remove ensure_full_index(). >> >> Change it to only expands the index when using --sparse. >> >> The p2000 tests demonstrate a ~99.4% execution time reduction for >> `git grep` using a sparse index. >> >> Test HEAD~1 HEAD >> ----------------------------------------------------------------------------- >> 2000.78: git grep --cached bogus (full-v3) 0.019 0.018 (-5.2%) >> 2000.79: git grep --cached bogus (full-v4) 0.017 0.016 (-5.8%) >> 2000.80: git grep --cached bogus (sparse-v3) 0.29 0.0015 (-99.4%) >> 2000.81: git grep --cached bogus (sparse-v4) 0.30 0.0018 (-99.4%) > > Good results. > > I think we could get interesting results even with the --sparse > option if you go another step further (perhaps as a patch after > this one). OK. >> >> Optional reading about performance test results >> ----------------------------------------------- >> Notice that because `git-grep` needs to parse blobs in the index, the >> index reading time is minuscule comparing to the object parsing time. >> And because of this, the p2000 test results cannot clearly reflect the >> speedup for index reading: combining with the object parsing time, >> the aggregated time difference is extremely close between HEAD~1 and >> HEAD. >> >> Hence, the results presenting here are not directly extracted from the >> p2000 test results. Instead, to make the performance difference more >> visible, the test command is manually ran with GIT_TRACE2_PERF in the >> four repos (full-v3, sparse-v3, full-v4, sparse-v4). The numbers here >> are then extracted from the time difference between "region_enter" and >> "region_leave" of label "do_read_index". > > This is a good point, but I don't recommend displaying them as if they > were the output of a "./run HEAD~1 HEAD -- p2000-sparse-operations.sh" > command. Instead, point out that the performance test does not show a > major improvement and instead you have these "Before" and "After" results > from testing manually and extracting trace2 regions. OK. >> @@ -519,11 +519,15 @@ static int grep_cache(struct grep_opt *opt, >> strbuf_addstr(&name, repo->submodule_prefix); >> } >> >> + prepare_repo_settings(repo); >> + repo->settings.command_requires_full_index = 0; >> + > > The best pattern is to put this in cmd_grep() immediately after parsing > options. This guarantees that we don't parse and expand the index in any > other code path. Got it. >> if (repo_read_index(repo) < 0) >> die(_("index file corrupt")); >> >> - /* TODO: audit for interaction with sparse-index. */ >> - ensure_full_index(repo->index); >> + if (grep_sparse) A side note: this condition should be `grep_sparse && cached`. >> + ensure_full_index(repo->index); >> + > As mentioned before, this approach is the simplest way to make the case > without --sparse faster, but the case _with_ --sparse will still be slow. > The way to fix this would be to modify this portion of the loop: I'm not sure. If --sparse here means we want to expand the index, it is expected to be slow (ensure_full_index is slow), isn't it? > 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))) { > > by adding an initial case > > if (S_ISSPARSEDIR(ce->ce_mode)) { > hit |= grep_tree(opt, &ce->oid, name.buf, 0, name.buf); > } 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))) { > > and appropriately implement "grep_tree()" to walk the tree at ce->oid to > find all matching files within, then call grep_oid() for each of those > paths. Tree walking is faster, yes. So, for this approach to be faster, I think you are suggesting we should not expand the index, even when --sparse is given? Instead, we just rely on the tree walking logic, right? > Bonus points if you recognize that the pathspec uses prefix checks that > allow pruning the search space and not parsing all of the trees > recursively. But that can definitely be delayed for a future enhancement. OK. >> +test_expect_success 'grep expands index using --sparse' ' >> + init_repos && >> + >> + # With --sparse and --cached, do not ignore sparse entries and >> + # expand the index. >> + test_all_match git grep --sparse --cached a >> +' > > Here, you're testing that the behavior matches, but not testing that the > index expands. (It does describe why you didn't include it in the later > ensure_not_expanded tests.) I was trying to "imply" the index expansion because of the behavior match. Yes, I think the test should be more explicit. >> + >> +test_expect_success 'grep is not expanded' ' >> + init_repos && >> + >> + ensure_not_expanded grep a && >> + ensure_not_expanded grep a -- deep/* && >> + # grep does not match anything per se, so ! is used > > It can be helpful to say why: > > # All files within the folder1/* pathspec are sparse, > # so this command does not find any matches. OK. -- Thanks, Shaoxuan
On 8/24/22 5:06 PM, Shaoxuan Yuan wrote: > On 8/17/2022 10:23 PM, Derrick Stolee wrote: >> On 8/17/2022 3:56 AM, Shaoxuan Yuan wrote: >>> Turn on sparse index and remove ensure_full_index(). >>> - /* TODO: audit for interaction with sparse-index. */ >>> - ensure_full_index(repo->index); >>> + if (grep_sparse) > > A side note: this condition should be `grep_sparse && cached`. > >>> + ensure_full_index(repo->index); >>> + >> As mentioned before, this approach is the simplest way to make the case >> without --sparse faster, but the case _with_ --sparse will still be slow. >> The way to fix this would be to modify this portion of the loop: > > I'm not sure. If --sparse here means we want to expand the index, it > is expected to be slow (ensure_full_index is slow), isn't it? > >> 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))) { >> >> by adding an initial case >> >> if (S_ISSPARSEDIR(ce->ce_mode)) { >> hit |= grep_tree(opt, &ce->oid, name.buf, 0, name.buf); >> } 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))) { >> >> and appropriately implement "grep_tree()" to walk the tree at ce->oid to >> find all matching files within, then call grep_oid() for each of those >> paths. > > Tree walking is faster, yes. So, for this approach to be faster, I > think you are suggesting we should not expand the index, even when > --sparse is given? Instead, we just rely on the tree walking logic, > right? Yes. Tree walking is a sizeable portion of the cost of expanding the index, but we also avoid constructing the new index _and_ we can use the t1092 tests to show that we are satisfying the behavior without resorting to ensure_full_index(). It shows that we are doing the "most correct" thing. Walking trees also provides the way to speed up when focused on a pathspec, since maybe the pathspec reduces the scope of the tree search automatically (from existing tree-walking logic). Expanding the index means "walk all the trees, then scan all the files" when there might be better things to do instead. Thanks, -Stolee
diff --git a/builtin/grep.c b/builtin/grep.c index 61402e8084..cbaab604fd 100644 --- a/builtin/grep.c +++ b/builtin/grep.c @@ -519,11 +519,15 @@ static int grep_cache(struct grep_opt *opt, strbuf_addstr(&name, repo->submodule_prefix); } + prepare_repo_settings(repo); + repo->settings.command_requires_full_index = 0; + if (repo_read_index(repo) < 0) die(_("index file corrupt")); - /* TODO: audit for interaction with sparse-index. */ - ensure_full_index(repo->index); + 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]; diff --git a/t/perf/p2000-sparse-operations.sh b/t/perf/p2000-sparse-operations.sh index fce8151d41..9a466fcbbe 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 bogus test_done diff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh index a6a14c8a21..a9bb6734f6 100755 --- a/t/t1092-sparse-checkout-compatibility.sh +++ b/t/t1092-sparse-checkout-compatibility.sh @@ -1972,4 +1972,21 @@ test_expect_success 'sparse index is not expanded: rm' ' ensure_not_expanded rm -r deep ' +test_expect_success 'grep expands index using --sparse' ' + init_repos && + + # With --sparse and --cached, do not ignore sparse entries and + # expand the index. + test_all_match git grep --sparse --cached a +' + +test_expect_success 'grep is not expanded' ' + init_repos && + + ensure_not_expanded grep a && + ensure_not_expanded grep a -- deep/* && + # grep does not match anything per se, so ! is used + ensure_not_expanded ! grep a -- folder1/* +' + test_done
Turn on sparse index and remove ensure_full_index(). Change it to only expands the index when using --sparse. The p2000 tests demonstrate a ~99.4% execution time reduction for `git grep` using a sparse index. Test HEAD~1 HEAD ----------------------------------------------------------------------------- 2000.78: git grep --cached bogus (full-v3) 0.019 0.018 (-5.2%) 2000.79: git grep --cached bogus (full-v4) 0.017 0.016 (-5.8%) 2000.80: git grep --cached bogus (sparse-v3) 0.29 0.0015 (-99.4%) 2000.81: git grep --cached bogus (sparse-v4) 0.30 0.0018 (-99.4%) Optional reading about performance test results ----------------------------------------------- Notice that because `git-grep` needs to parse blobs in the index, the index reading time is minuscule comparing to the object parsing time. And because of this, the p2000 test results cannot clearly reflect the speedup for index reading: combining with the object parsing time, the aggregated time difference is extremely close between HEAD~1 and HEAD. Hence, the results presenting here are not directly extracted from the p2000 test results. Instead, to make the performance difference more visible, the test command is manually ran with GIT_TRACE2_PERF in the four repos (full-v3, sparse-v3, full-v4, sparse-v4). The numbers here are then extracted from the time difference between "region_enter" and "region_leave" of label "do_read_index". Helped-by: Derrick Stolee <derrickstolee@github.com> Signed-off-by: Shaoxuan Yuan <shaoxuan.yuan02@gmail.com> --- builtin/grep.c | 8 ++++++-- t/perf/p2000-sparse-operations.sh | 1 + t/t1092-sparse-checkout-compatibility.sh | 17 +++++++++++++++++ 3 files changed, 24 insertions(+), 2 deletions(-)