[PATCH v3 2/3] ref-filter: memoize --contains with generations
- From
Tamir Duberstein <tamird@gmail.com>
- Date
- Jun 12, 2026, 03:00 UTC
- Message-ID
- <20260611-ref-filter-memoized-contains-v3-2-b26af3dba285@gmail.com>
- In-Reply-To
- <20260611-ref-filter-memoized-contains-v3-0-b26af3dba285@gmail.com>
git branch and git for-each-ref run a separate reachability walk for each ref considered by --contains and --no-contains. Refs with shared history therefore traverse the same commits repeatedly.
git tag instead uses a depth-first walk that caches results across refs. That walk can perform poorly without generation numbers: a negative check may walk to the root instead of stopping at a nearby divergence. Generation numbers let it stop below the oldest target.
Use the memoized walk for all ref-filter callers when generation numbers are available. Keep git tag on its existing path without generations. Caching still helps when many tags share deep history: ffc4b8012d (tag: speed up --contains calculation, 2011-06-11) reduced git tag --contains HEAD~200 in linux-2.6 from 15.417 to 5.329 seconds.
The new shared-history perf test improves from 0.72 to 0.03 seconds. In a repository with 62,174 remote-tracking refs, running:
git branch -r --contains c78ae85f3ce7e
improves from 104.365 seconds to 468 milliseconds.
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 Link: https://lore.kernel.org/r/CAOLa=ZSezQOj56-TezVaAcisUyczxhJmu4VghyFBHcBB_mKJ2A@mail.gmail.com Suggested-by: Jeff King <peff@peff.net> Signed-off-by: Tamir Duberstein <tamird@gmail.com> --- commit-reach.c | 3 ++- t/perf/p1500-graph-walks.sh | 28 +++++++++++++++++++++++++++- 2 files changed, 29 insertions(+), 2 deletions(-)
diff --git a/commit-reach.c b/commit-reach.c index 1d34d66fe8..572d2d47ff 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -820,7 +820,8 @@ 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) + 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); } diff --git a/t/perf/p1500-graph-walks.sh b/t/perf/p1500-graph-walks.sh index 5b23ce5db9..d167b4f7e1 100755 --- a/t/perf/p1500-graph-walks.sh +++ b/t/perf/p1500-graph-walks.sh @@ -32,7 +32,16 @@ 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/*" && + + commit=$(git commit-tree HEAD^{tree}) && git update-ref refs/heads/disjoint-base $commit && git commit-graph write --reachable @@ -62,6 +71,23 @@ test_perf 'contains: git tag --merged' ' xargs git tag --merged=HEAD <tags ' +test_perf 'contains: git for-each-ref' ' + git for-each-ref --contains=refs/contains-perf-base --stdin <refs +' + +test_perf 'contains: git branch' ' + xargs git branch --contains=refs/contains-perf-base <branches +' + +test_perf 'contains: git tag' ' + xargs git tag --contains=refs/contains-perf-base <tags +' + +test_perf 'contains: synthetic shared history' ' + git for-each-ref --contains=refs/contains-perf-base \ + refs/contains-perf/ >/dev/null +' + test_perf 'is-base check: test-tool reach (refs)' ' test-tool reach get_branch_base_for_tip <test-tool-refs '
-- 2.54.0.548.gbe7bb2469c