git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH] ref-filter: reuse --contains traversal results

From
Tamir Duberstein <tamird@gmail.com>
Date
Jun 8, 2026, 23:35 UTC
Message-ID
<CAJ-ks9ng3Obv8jydYiBD4kxmTSZCJX8xNb0YihNeSW8_8WL5Ew@mail.gmail.com>
In-Reply-To
<20260608223430.GA340696@coredump.intra.peff.net>
On Mon, Jun 8, 2026 at 3:34 PM Jeff King <peff@peff.net> wrote:
Show 23 quoted lines
>
> 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.
Show 18 quoted lines
>
> 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.

Show 10 quoted lines
>
> > 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.

Show 46 quoted lines
>
> 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
Previous: Jeff KingNext: Jeff King
Message 5 of 7 in “ref-filter: reuse --contains traversal results”
  1. ref-filter: reuse --contains traversal resultsTamir Duberstein, Jun 8, 2026
  2. Karthik NayakJun 8, 2026
  3. Tamir DubersteinJun 8, 2026
  4. Jeff KingJun 8, 2026
  5. Tamir DubersteinJun 8, 2026
  6. Jeff KingJun 8, 2026
  7. Tamir DubersteinJun 8, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.