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

>
> On Mon, Jun 08, 2026 at 07:36:35PM -0700, Tamir Duberstein wrote:
>
> > 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.
>
> Heh. Without the original repo, this sha256 hash is meaningless to us,
> isn't it? Ditto for the sha1 the earlier command.

>
> >  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))
> >               return contains_tag_algo(commit, list, cache) == CONTAINS_YES;
> > -     return repo_is_descendant_of(the_repository, commit, list);
> > +
> > +     result = repo_is_descendant_of(the_repository, commit, list);
> > +     if (result < 0)
> > +             exit(128);
> > +     return result;
>
> There's a little more going on here than I expected from the commit
> message. Is it important for us to short-circuit the empty list and just
> return 1? Or did the existing helper functions already handle that?
>
> Looking at contains_tag_algo(), I think it would actually return
> CONTAINS_NO here (though I didn't test it). So this is actually a change
> in behavior for "git tag" if that's correct. I doubt it is triggerable
> in practice, though, as we would simply never call commit_contains() in
> the first place with an empty list. But if we are going to add in this
> logic, I think it makes sense to do so as a separate commit (describing
> what it is doing and why it's not (yet) a triggerable bug).
>
> Checking the result of repo_is_descendant_of() makes sense, as discussed
> earlier. But probably that should come as its own patch, since it's an
> independent bug-fix. I'm also tempted to say it should call die()
> instead of a direct exit, though it does look like the error exit paths
> from repo_is_descendant_of() would all have produced their own messages.

>
>
> And one side note. While looking at the implementation of
> repo_is_descendant_of(), I did notice something curious: it also
> switches algorithms based on the presence of generation numbers! So it
> should also be cutting off the traversal early when possible. But I
> guess its main problem is that we call it independently for each
> candidate, so it may traverse the same (useful) stretch of history
> multiple times.
>
> So probably an alternative approach to this patch would be feeding all
> of the candidates at once, the way we do with reach_filter() via
> filter_refs(). I'm not sure if we have the right functions available for
> that (naively, --contains and --merged are inversions of each other, so
> swapping the arguments to tips_reachable_from_bases() might work, but I
> didn't think very hard on it).

>
> I wonder if that might perform better or worse. I'm content to leave it
> for another day, though, as switching to the memoizing depth-first algo
> here is a pretty easy change.
>
> > -     commit=$(git commit-tree $(git rev-parse HEAD^{tree})) &&
> > +     git rev-list --first-parent --max-count=8192 HEAD >contains-commits &&
> > +     test_file_not_empty contains-commits &&
> > +     git update-ref refs/contains-perf-base "$(tail -n 1 contains-commits)" &&
> > +     awk "{
> > +             printf \"update refs/contains-perf/%04d %s\\n\", NR, \$1
> > +     }" contains-commits |
> > +             git update-ref --stdin &&
> > +     git pack-refs --include "refs/contains-perf/*" &&
>
> My head almost exploded reading the embedded quoting in that awk
> invocation. But I can't think offhand of a better way to do it. You
> can't use test_seq because it needs both the number and the original
> string. You can do it with sed, but it probably ends up even more
> unreadable.
>
> But OK, we are making a bunch of refs based on first-parent history.
>
> > +     tree=$(git rev-parse HEAD^{tree}) &&
> > +     base=$(git rev-parse HEAD) &&
> > +     target=$(echo target | git commit-tree "$tree" -p "$base") &&
> > +     git update-ref refs/contains-diverged/target "$target" &&
> > +     for i in $(test_seq 1 4)
> > +     do
> > +             commit=$(echo candidate-$i |
> > +                     git commit-tree "$tree" -p "$base") &&
> > +             git update-ref refs/contains-diverged/candidate-$i "$commit" ||
> > +             return 1
> > +     done &&
>
> And then a few candidate refs that are not reachable from other refs, or
> from each other. OK.
>
> I think you could just write:
>
>   git commit-tree HEAD^{tree} -p HEAD
>
> instead of doing separate rev-parses, but it's probably not a big deal
> either way.
>
> > +test_expect_success 'verify contains results' '
> > +     git for-each-ref --contains=refs/contains-perf-base \
> > +             refs/contains-perf/ >actual &&
> > +     test_line_count = $(wc -l <contains-commits) actual &&
> > +
> > +     echo refs/contains-diverged/target >expect &&
> > +     GIT_TEST_COMMIT_GRAPH=0 \
> > +             git -c core.commitGraph=false for-each-ref \
> > +                     --format="%(refname)" \
> > +                     --contains=refs/contains-diverged/target \
> > +                     refs/contains-diverged/ >actual &&
> > +     test_cmp expect actual
> > +'
>
> This is a funny test to have in the middle of a perf script (which
> hardly anybody ever runs). If we are concerned about the correctness,
> should this be in a non-perf test script? Though I'd imagine something
> like it is already covered there.

>
> There's a lot of subtlety in what we're verifying, too. In the first
> half, we are checking that all of the commits in contains-perf contain
> the base.  And that base is the final element of the contains-commits
> list. Which made me wonder what happens in a branch history, since that
> list is linearized. But because we used --first-parent to generate it,
> it _is_ linear, and the results work out. So OK, I don't think it's
> wrong, but I am struggling to understand the meaning of the test.
>
> The second half is just checking that...the other refs which are not
> contained in "target" are not mentioned? OK, but why do it only with
> commit graphs off. Why not both off and on? Again, I'm not sure I
> understand what we're trying to focus on here.
>
> > +test_perf 'contains: git for-each-ref --contains' '
> > +     git for-each-ref --contains=refs/contains-perf-base \
> > +             refs/contains-perf/ >/dev/null
> > +'
>
> Yay, actual perf tests. Here we have a ton of matches, and they all walk
> over the same chunk of history. Should get much faster, though it's
> mostly a synthetic test.
>
> For --merged, we already have separate tests with each of for-each-ref,
> branch, and tag. Should we have the same here for --contains? And should
> we be using the input repo data, rather than our synthetic test? It is
> nice to show off the performance with the synthetic test, but ultimately
> the point of the perf suite is feeding it real workloads and looking for
> regressions.

>
> > +test_perf 'contains without generations: divergent refs' '
> > +     GIT_TEST_COMMIT_GRAPH=0 \
> > +             git -c core.commitGraph=false for-each-ref \
> > +                     --contains=refs/contains-diverged/target \
> > +                     refs/contains-diverged/ >/dev/null
> > +'
>
> OK, and this one should find that most of them are not contained, but
> the depth-first algorithm could walk all the way down to the roots. But
> we don't run it at all, since we disable commit graphs!
>
> So what are we trying to measure here? If it left commit graphs enabled,
> I think we could demonstrate that using the depth-first algorithm with
> generation numbers does not make anything _worse_. I.e., that
> for-each-ref and branch did not regress from the change.

>
> > +test_expect_success 'missing ancestors are reported by contains filters' '
> > +     test_when_finished "git update-ref -d refs/heads/missing-parent" &&
> > +     {
> > +             echo "tree $(git rev-parse HEAD^{tree})" &&
> > +             echo "parent $MISSING" &&
> > +             git cat-file commit HEAD |
> > +                     sed -n -e "/^author /p" -e "/^committer /p" &&
> > +             echo &&
> > +             echo "missing parent"
> > +     } >commit &&
> > +     broken=$(git hash-object -t commit -w commit) &&
> > +     git update-ref refs/heads/missing-parent "$broken" &&
> > +     for option in --contains --no-contains
> > +     do
> > +             test_must_fail git for-each-ref "$option=HEAD" \
> > +                     refs/heads/missing-parent >out 2>err &&
> > +             test_must_be_empty out &&
> > +             test_grep "parse commit $MISSING" err ||
> > +             return 1
> > +     done
> > +'
>
> This is a great thing to test, but probably should be pulled out into
> a separate patch along with the fix to check the return code.

>
> The commit construction looks OK, and is nicer than corrupting the
> repository by deleting a real object. Given that we are pulling the
> idents from an existing commit, it might be simpler to just use the
> whole commit as a template, like:
>
>   git cat-file commit HEAD |
>   sed "s/^parent /parent $MISSING/"
>
> but it may be a matter of taste.
>
> -Peff