Re: [PATCH v2 2/2] ref-filter: memoize --contains with generations
- From
Jeff King <peff@peff.net>
- Date
- Jun 11, 2026, 08:22 UTC
- Message-ID
- <20260611082244.GH2191159@coredump.intra.peff.net>
- In-Reply-To
- <20260608-ref-filter-memoized-contains-v2-2-e72720344a7c@gmail.com>
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.
Show 17 quoted lines
> 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.
Show 9 quoted lines
> - 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.
Show 11 quoted lines
> + 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 HEADinstead of doing separate rev-parses, but it's probably not a big deal either way.
Show 13 quoted lines
> +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.
Show 6 quoted lines
> +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.
Show 21 quoted lines
> +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