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

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