From: Tamir Duberstein Date: Fri, 12 Jun 2026 02:40:23 GMT Subject: Re: [PATCH v2 2/2] ref-filter: memoize --contains with generations Message-ID: In-Reply-To: <20260611082244.GH2191159@coredump.intra.peff.net> On Thu, Jun 11, 2026 at 1:22 AM Jeff King wrote: > > 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. Yeah, AI slop. Removed. > > > 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. I dropped the empty-list change. The error check is now a separate patch and uses die(). > > > 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 tried the suggested argument swap, but tips_reachable_from_bases() only reports whether a tip is reachable from any base. It cannot report which candidate refs contain a target, which is what --contains needs. I did not find an existing batched reachability helper that returns those per-candidate answers. > > 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 > + > > + 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. I deleted that block rather than moving it. It only rechecked ordinary --contains semantics already covered by t3201, t6302, and t7004; with GIT_TEST_COMMIT_GRAPH=1, those tests exercise the newly selected memoized path for branch and for-each-ref. The series adds functional tests for the behavior that is actually new: t7004 covers cyclic replacement histories, and t6301 covers unreadable ancestry. The p1500 additions now measure performance only. > > 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. I added p1500 cases for all three frontends using refs from the input repository, while retaining the synthetic shared-history case. > > > +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. The divergent-ref test did not exercise the changed path, so I removed it. > > > +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. Done in v3. > > 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