From: Tamir Duberstein Date: Mon, 08 Jun 2026 23:35:57 GMT Subject: Re: [PATCH] ref-filter: reuse --contains traversal results Message-ID: In-Reply-To: <20260608223430.GA340696@coredump.intra.peff.net> On Mon, Jun 8, 2026 at 3:34 PM Jeff King wrote: > > On Sun, Jun 07, 2026 at 08:33:29PM -0700, Tamir Duberstein wrote: > > > 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 > > the tag traversal that caches positive and negative answers across > > candidates. ee2bd06b0f (ref-filter: implement '--contains' option, > > 2015-07-07) preserved the branch and tag implementations when ref-filter > > learned --contains. 008ed7df930 (tag.c: use the correct algorithm for > > the '--contains' option, 2015-10-18) noted that they should be unified. > > > > Use the memoized traversal for every ref-filter contains check and > > remove the implementation selector. The cache records answers for one > > fixed target list, so document that callers must clear it before > > changing the list. > > The subject line obfuscated the intent here (at least for me). I think a > more clear subject would just be: "ref-filter: always use > contains_tag_algo" or something. Ack, changed to "ref-filter: memoize --contains with generations" in v2 draft. > > But more importantly, I think the analysis above is missing a key point > about why we didn't make the tag algo the default in the first place: it > is depth first, and thus slower when the merge base can be found quickly > by the breadth-first traversal. For tags, you tend to have to look at > all of history anyway (because you have at least one old tag that > requires walking back that far), but that is often not true for > branches. > > We are able to get the best of both worlds if we can cut off the > depth-first traversal early using generation numbers. > > So I think a better rule here is to tweak the selection in > commit_contains() to select the depth-first algorithm when we have > generation numbers enabled. There's a patch in an old thread, which was > revived a week or two ago by Kristofer (cc'd): > > https://lore.kernel.org/git/20260527070510.3510836-1-krka@spotify.com/ Very good catch, thank you. I reproduced the regression with a 100,000-commit history and generation numbers disabled. The parent took 13.0 ms, the unconditional depth-first version took 238.4 ms, and the generation-aware version took 9.1 ms. I didn't find a patch in that thread, so I will reroll using the memoized walk for tags or when generation numbers are enabled, while retaining the breadth-first walk otherwise. If someone else would prefer to send that patch, that is fine by me as well. > > > The memoized depth-first walk assumes acyclic ancestry, but replacement > > refs can create cycles. Track commits while they are on the walk. If a > > cycle is found, discard partial cache entries and use > > repo_is_descendant_of() for that candidate. > > I can believe that the depth-first code doesn't handle cycles well. But > if that's the case, then it's already a problem for "git tag > --contains". And we should fix it as a separate patch from enabling that > algorithm in more cases. Agreed, and Karthik flagged the same. The cycle handling is now a separate first patch. > > I'm not quite sure how ancestry should be defined in a cycle. How does > the algorithm behave now when it sees a cycle? If it loops infinitely, > we definitely would want to fix that. If not, then to some degree I > don't care too much what answer is provided, since the input is somewhat > nonsense in the first place. And if it is expensive to track, it might > not be worth inflicting that penalty on the sane cases. But it looks > like your solution is just setting an extra flag value in the slab, > which should be pretty cheap. > > > The branch and for-each-ref path passed repo_is_descendant_of() through > > a Boolean interface. In configurations where it returned -1 for missing > > ancestry, ref-filter treated the error as "contains". The memoized path > > instead fails when ancestry cannot be parsed, as git tag already did. > > During review of the 2018 reachability series, making parse failures > > fatal was explicitly deferred because that series was intended to > > preserve behavior. Unifying the implementations now makes all callers > > fail consistently instead of preserving that accidental Boolean > > interpretation. > > I think that's a good outcome. > > > The added p1500 case uses up to 8,192 packed refs along one first-parent > > history. It improves from 0.68 to 0.03 seconds. > > > > On a checkout with 62,174 remote-tracking refs, 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 > > I didn't time it, but the probable regression case is something like > this: a very deep history with a small number of branches diverging only > a few commits away. Without a commit-graph file (or one without > generation numbers), that probably makes "git branch --contains" slower. > > -Peff