Re: [PATCH v2 2/2] ref-filter: memoize --contains with generations

>
> Tamir Duberstein <tamird@gmail.com> writes:
>
> > On Wed, Jun 10, 2026 at 4:47 AM Karthik Nayak <karthik.188@gmail.com> wrote:
> >>
> >> Tamir Duberstein <tamird@gmail.com> writes:
> >>
> >> > git branch and git for-each-ref call repo_is_descendant_of() for
> >> > each candidate selected by --contains or --no-contains. Each call
> >> > starts a new graph walk, so refs with shared history repeatedly
> >> > traverse the same commits.
> >> >
> >> > ffc4b8012d (tag: speed up --contains calculation, 2011-06-11)
> >> > introduced a depth-first walk for git tag that caches positive and
> >> > negative answers across candidates. ee2bd06b0f (ref-filter: implement
> >> > '--contains' option, 2015-07-07) preserved both implementations when
> >> > ref-filter learned --contains.
> >> >
> >> > The memoized walk is not always faster. Without generation numbers,
> >> > a negative check can walk to the root even when the breadth-first
> >> > merge-base walk finds a nearby divergence. With generation numbers,
> >> > the depth-first walk can stop below the oldest target while still
> >> > reusing answers across candidates.
> >> >
> >> > Keep the existing memoized selection for git tag. Select it for other
> >> > ref-filter callers when generation numbers are enabled, and retain
> >> > the breadth-first walk otherwise.
> >> >
> >> > When generation numbers are unavailable, repo_is_descendant_of() can
> >> > return -1 if ancestry cannot be read. The ref-filter Boolean interface
> >> > treated that error as a match. Check it and exit instead. The memoized
> >> > path already dies on the same parse failure, so both selected paths now
> >> > fail rather than return a result.
> >> >
> >> > Add p1500 cases for up to 8,192 packed refs along one first-parent
> >> > history and for sibling refs near the tip with generation numbers
> >> > forced off.
> >> >
> >> > On a checkout with 62,174 remote-tracking refs and generation numbers
> >> > enabled, I ran:
> >> >
> >> >     hyperfine --warmup 0 --runs 3 \
> >> >         --command-name parent \
> >> >         '"$parent" branch -r --contains c78ae85f3ce7e >/dev/null' \
> >> >         --command-name this-commit \
> >> >         '"$this" branch -r --contains c78ae85f3ce7e >/dev/null'
> >> >
> >> > The results were:
> >> >
> >> >              parent       this commit
> >> >   elapsed    104.365 s     467.7 ms
> >> >   user        93.702 s     220.2 ms
> >> >   system       0.723 s     182.7 ms
> >> >
> >> > The wall-time standard deviations were 11.356 seconds and 133.8
> >> > milliseconds, respectively. Separate runs without redirection produced
> >> > the same output with SHA-256
> >> > 2466f6e2b72aa16b1a2126eddb81c8a1b2764ee251204ac034c191a925aa896f.
> >> >
> >> > Both revisions were built with the default -O2 flags using Apple
> >> > clang 21.0.0 on macOS 26.5. The machine was a MacBook Pro (Mac16,6)
> >> > with a 16-core Apple M4 Max (12 performance and four efficiency
> >> > cores) and 128 GB RAM.
> >> >
> >> > Link: https://lore.kernel.org/git/1445163904-24611-1-git-send-email-Karthik.188@gmail.com/
> >> > Link: https://lore.kernel.org/r/20230324191009.GA536967@coredump.intra.peff.net
> >> > Link: https://lore.kernel.org/git/20260527070510.3510836-1-krka@spotify.com/
> >> > Link: https://lore.kernel.org/r/20260608223430.GA340696@coredump.intra.peff.net
> >> > Suggested-by: Jeff King <peff@peff.net>
> >> > Signed-off-by: Tamir Duberstein <tamird@gmail.com>
> >> > ---
> >> >  commit-reach.c                 | 13 +++++++++--
> >> >  commit-reach.h                 |  7 ++++++
> >> >  t/perf/p1500-graph-walks.sh    | 49 +++++++++++++++++++++++++++++++++++++++++-
> >> >  t/t6301-for-each-ref-errors.sh | 22 +++++++++++++++++++
> >> >  4 files changed, 88 insertions(+), 3 deletions(-)
> >> >
> >> > diff --git a/commit-reach.c b/commit-reach.c
> >> > index 65b618959b..83a48004ef 100644
> >> > --- a/commit-reach.c
> >> > +++ b/commit-reach.c
> >> > @@ -821,9 +821,18 @@ static enum contains_result contains_tag_algo(struct commit *candidate,
> >> >  int commit_contains(struct ref_filter *filter, struct commit *commit,
> >> >                   struct commit_list *list, struct contains_cache *cache)
> >> >  {
> >> > -     if (filter->with_commit_tag_algo)
> >> > +     int result;
> >> > +
> >> > +     if (!list)
> >> > +             return 1;
> >> > +     if (filter->with_commit_tag_algo ||
> >> > +         generation_numbers_enabled(the_repository))
> >>
> >> What's stopping us from dropping `filter->with_commit_tag_algo`
> >> completely and then doing?
> >>
> >>   if (generation_numbers_enabled(the_repository))
> >>      return contains_algo(commit, list, cache) == CONTAINS_YES;
> >>   return repo_is_descendant_of(the_repository, commit, list);
> >
> > Jeff raised this distinction during the v1 review:
> >
> > https://lore.kernel.org/r/20260608223430.GA340696@coredump.intra.peff.net/
> >
> > `with_commit_tag_algo` preserves the existing behavior of `git tag` when
> > generation numbers are unavailable. `git tag --contains` has used the
> > memoized walk since ffc4b8012d (tag: speed up --contains calculation,
> > 2011-06-11). Dropping the flag would send it back through repeated
> > `repo_is_descendant_of()` walks in repositories without usable generation
> > numbers.
> >
>
> I did read that, my question is on top of that. Do we also want to use
> the non-memoized walk for 'git tag' when there are no generation numbers
> available or does that not work? If not, we should mention that too in
> the commit message.