From: Tamir Duberstein Date: Thu, 11 Jun 2026 20:10:30 GMT Subject: Re: [PATCH v2 2/2] ref-filter: memoize --contains with generations Message-ID: In-Reply-To: On Thu, Jun 11, 2026 at 1:16 AM Karthik Nayak wrote: > > Tamir Duberstein writes: > > > On Wed, Jun 10, 2026 at 4:47 AM Karthik Nayak wrote: > >> > >> Tamir Duberstein 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 > >> > Signed-off-by: Tamir Duberstein > >> > --- > >> > 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. We should keep the memoized walk for git tag. In git.git, with commit graphs disabled, hyperfine measured: git -c core.commitGraph=false tag --contains HEAD~200 git -c core.commitGraph=false for-each-ref \ --contains HEAD~200 refs/tags/ at 478.9 ms and 4.861 s, respectively. The second command takes the non-memoized path, so memoization is about 10 times faster for this workload. I added the rationale to the commit message in v3.