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

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

From
Tamir Duberstein <tamird@gmail.com>
Date
Jun 9, 2026, 02:36 UTC
Message-ID
<20260608-ref-filter-memoized-contains-v2-2-e72720344a7c@gmail.com>
In-Reply-To
<20260608-ref-filter-memoized-contains-v2-0-e72720344a7c@gmail.com>

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 a depth-first walk for git tag that caches positive and negative answers across candidates. ee2bd06b0f (ref-filter: implement '--contains' option, 2015-07-07) preserved both implementations when ref-filter learned --contains.

The memoized walk is not always faster. Without generation numbers, a negative check can walk to the root even when the breadth-first merge-base walk finds a nearby divergence. With generation numbers, the depth-first walk can stop below the oldest target while still reusing answers across candidates.

Keep the existing memoized selection for git tag. Select it for other ref-filter callers when generation numbers are enabled, and retain the breadth-first walk otherwise.

When generation numbers are unavailable, repo_is_descendant_of() can return -1 if ancestry cannot be read. The ref-filter Boolean interface treated that error as a match. Check it and exit instead. The memoized path already dies on the same parse failure, so both selected paths now fail rather than return a result.

Add p1500 cases for up to 8,192 packed refs along one first-parent history and for sibling refs near the tip with generation numbers forced off.

On a checkout with 62,174 remote-tracking refs and generation numbers enabled, 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

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.

Both revisions were built with the default -O2 flags using Apple clang 21.0.0 on macOS 26.5. The machine was a MacBook Pro (Mac16,6) with a 16-core Apple M4 Max (12 performance and four efficiency cores) and 128 GB RAM.

Link: https://lore.kernel.org/git/1445163904-24611-1-git-send-email-Karthik.188@gmail.com/
Link: https://lore.kernel.org/r/20230324191009.GA536967@coredump.intra.peff.net
Link: https://lore.kernel.org/git/20260527070510.3510836-1-krka@spotify.com/
Link: https://lore.kernel.org/r/20260608223430.GA340696@coredump.intra.peff.net
Suggested-by: Jeff King <peff@peff.net>
Signed-off-by: Tamir Duberstein <tamird@gmail.com>
---
 commit-reach.c                 | 13 +++++++++--
 commit-reach.h                 |  7 ++++++
 t/perf/p1500-graph-walks.sh    | 49 +++++++++++++++++++++++++++++++++++++++++-
 t/t6301-for-each-ref-errors.sh | 22 +++++++++++++++++++
 4 files changed, 88 insertions(+), 3 deletions(-)
diff --git a/commit-reach.c b/commit-reach.c
index 65b618959b..83a48004ef 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -821,9 +821,18 @@ static enum contains_result contains_tag_algo(struct commit *candidate,
 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;
 }
 
 int can_all_from_reach_with_flag(struct object_array *from,
diff --git a/commit-reach.h b/commit-reach.h
index f908d305b1..da6796a354 100644
--- a/commit-reach.h
+++ b/commit-reach.h
@@ -79,6 +79,13 @@ enum contains_result {
 
 define_commit_slab(contains_cache, enum contains_result);
 
+/*
+ * Return whether "commit" is a descendant of any commit in "list". An empty
+ * list matches.
+ *
+ * The memoized traversal records answers in "cache" for one fixed "list".
+ * Clear it before changing the list.
+ */
 int commit_contains(struct ref_filter *filter, struct commit *commit,
 		    struct commit_list *list, struct contains_cache *cache);
 
diff --git a/t/perf/p1500-graph-walks.sh b/t/perf/p1500-graph-walks.sh
index 5b23ce5db9..99b54e274b 100755
--- a/t/perf/p1500-graph-walks.sh
+++ b/t/perf/p1500-graph-walks.sh
@@ -32,12 +32,47 @@ test_expect_success 'setup' '
 		echo "X:$line" >>test-tool-tags || return 1
 	done &&
 
-	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/*" &&
+
+	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 &&
+
+	commit=$(git commit-tree "$tree") &&
 	git update-ref refs/heads/disjoint-base $commit &&
 
 	git commit-graph write --reachable
 '
 
+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
+'
+
 test_perf 'ahead-behind counts: git for-each-ref' '
 	git for-each-ref --format="%(ahead-behind:HEAD)" --stdin <refs
 '
@@ -62,6 +97,18 @@ test_perf 'contains: git tag --merged' '
 	xargs git tag --merged=HEAD <tags
 '
 
+test_perf 'contains: git for-each-ref --contains' '
+	git for-each-ref --contains=refs/contains-perf-base \
+		refs/contains-perf/ >/dev/null
+'
+
+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
+'
+
 test_perf 'is-base check: test-tool reach (refs)' '
 	test-tool reach get_branch_base_for_tip <test-tool-refs
 '
diff --git a/t/t6301-for-each-ref-errors.sh b/t/t6301-for-each-ref-errors.sh
index e06feb06e9..72b27c8be3 100755
--- a/t/t6301-for-each-ref-errors.sh
+++ b/t/t6301-for-each-ref-errors.sh
@@ -52,6 +52,28 @@ test_expect_success 'Missing objects are reported correctly' '
 	test_must_be_empty brief-err
 '
 
+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
+'
+
 test_expect_success 'ahead-behind requires an argument' '
 	test_must_fail git for-each-ref \
 		--format="%(ahead-behind)" 2>err &&

-- 
2.54.0.501.g0fb508de08
Previous: Tamir DubersteinNext: Karthik Nayak
Message 5 of 25 in “Reuse --contains traversal results”
  1. 0/2 Reuse --contains traversal resultsTamir Duberstein, Jun 9, 2026
  2. 1/2 commit-reach: handle cycles in contains walkTamir Duberstein, Jun 9, 2026
  3. Jeff KingJun 11, 2026
  4. Tamir DubersteinJun 12, 2026
  5. 2/2 ref-filter: memoize --contains with generationsTamir Duberstein, Jun 9, 2026
  6. Karthik NayakJun 10, 2026
  7. Tamir DubersteinJun 10, 2026
  8. Karthik NayakJun 11, 2026
  9. Tamir DubersteinJun 11, 2026
  10. Jeff KingJun 11, 2026
  11. Tamir DubersteinJun 12, 2026
  12. 0/3 Reuse --contains traversal resultsTamir Duberstein, Jun 12, 2026
  13. 1/3 commit-reach: handle cycles in contains walkTamir Duberstein, Jun 12, 2026
  14. Kristofer KarlssonJun 12, 2026
  15. Tamir DubersteinJun 12, 2026
  16. 2/3 ref-filter: memoize --contains with generationsTamir Duberstein, Jun 12, 2026
  17. 3/3 commit-reach: die on contains walk errorsTamir Duberstein, Jun 12, 2026
  18. 0/3 Reuse --contains traversal resultsTamir Duberstein, Jun 12, 2026
  19. 1/3 commit-reach: reject cycles in contains walkTamir Duberstein, Jun 12, 2026
  20. Jeff KingJul 16, 2026
  21. 2/3 ref-filter: memoize --contains with generationsTamir Duberstein, Jun 12, 2026
  22. 3/3 commit-reach: die on contains walk errorsTamir Duberstein, Jun 12, 2026
  23. Jeff KingJul 16, 2026
  24. Junio C HamanoJun 29, 2026
  25. Jeff KingJul 16, 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.