Re: [PATCH] ref-filter: reuse --contains traversal results
- From
Karthik Nayak <karthik.188@gmail.com>
- Date
- Jun 8, 2026, 21:18 UTC
- Message-ID
- <CAOLa=ZS_U+u43SV9ELSEU6AT7rzEQ44BuHPAi1BAHEGQAnPoPw@mail.gmail.com>
- In-Reply-To
- <20260607-ref-filter-memoized-contains-v1-1-a1972dde9c76@gmail.com>
Tamir Duberstein <tamird@gmail.com> writes:
Show 12 quoted lines
> 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 > the tag traversal that caches positive and negative answers across > candidates. ee2bd06b0f (ref-filter: implement '--contains' option, > 2015-07-07) preserved the branch and tag implementations when ref-filter > learned --contains. 008ed7df930 (tag.c: use the correct algorithm for > the '--contains' option, 2015-10-18) noted that they should be unified. >
Nicely explained. We should've merged this long ago, so this is a worthwhile change.
Show 74 quoted lines
> Use the memoized traversal for every ref-filter contains check and
> remove the implementation selector. The cache records answers for one
> fixed target list, so document that callers must clear it before
> changing the list.
>
> The memoized depth-first walk assumes acyclic ancestry, but replacement
> refs can create cycles. Track commits while they are on the walk. If a
> cycle is found, discard partial cache entries and use
> repo_is_descendant_of() for that candidate.
>
> The branch and for-each-ref path passed repo_is_descendant_of() through
> a Boolean interface. In configurations where it returned -1 for missing
> ancestry, ref-filter treated the error as "contains". The memoized path
> instead fails when ancestry cannot be parsed, as git tag already did.
> During review of the 2018 reachability series, making parse failures
> fatal was explicitly deferred because that series was intended to
> preserve behavior. Unifying the implementations now makes all callers
> fail consistently instead of preserving that accidental Boolean
> interpretation.
>
> The added p1500 case uses up to 8,192 packed refs along one first-parent
> history. It improves from 0.68 to 0.03 seconds.
>
> On a checkout with 62,174 remote-tracking refs, 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, for a 223x speedup. Both commands produced
> output with SHA-256
> 2466f6e2b72aa16b1a2126eddb81c8a1b2764ee251204ac034c191a925aa896f.
>
> Both revisions were rebuilt 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/git/20180723204112.233274-1-jonathantanmy@google.com/
> Link: https://lore.kernel.org/git/24424e55-7fa8-d05b-bc39-e14b4d5abcb6@gmail.com/
> Signed-off-by: Tamir Duberstein <tamird@gmail.com>
> ---
> builtin/tag.c | 1 -
> commit-reach.c | 45 +++++++++++++++++++++++++++++++-----------
> commit-reach.h | 15 ++++++++++----
> ref-filter.c | 6 ++++--
> ref-filter.h | 7 +++----
> t/helper/test-reach.c | 10 ++--------
> t/perf/p1500-graph-walks.sh | 24 +++++++++++++++++++++-
> t/t6301-for-each-ref-errors.sh | 18 +++++++++++++++++
> t/t6302-for-each-ref-filter.sh | 21 ++++++++++++++++++++
> t/t6600-test-reach.sh | 6 ++----
> 10 files changed, 117 insertions(+), 36 deletions(-)
>
> diff --git a/builtin/tag.c b/builtin/tag.c
> index d51c2e3349..9f34d948d4 100644
> --- a/builtin/tag.c
> +++ b/builtin/tag.c
> @@ -71,7 +71,6 @@ static int list_tags(struct ref_filter *filter, struct ref_sorting *sorting,
>
> if (verify_ref_format(format))
> die(_("unable to parse format string"));
> - filter->with_commit_tag_algo = 1;We were selectively using the algo for `git tag`, like mentioned I guess we'll entirely remove `with_commit_tag_algo` below somewhere
Show 22 quoted lines
> filter_and_format_refs(filter, FILTER_REFS_TAGS, sorting, format); > > free(to_free); > diff --git a/commit-reach.c b/commit-reach.c > index 9b3ea46d6f..6e599a3670 100644 > --- a/commit-reach.c > +++ b/commit-reach.c > @@ -6,7 +6,6 @@ > #include "decorate.h" > #include "hex.h" > #include "prio-queue.h" > -#include "ref-filter.h" > #include "revision.h" > #include "tag.h" > #include "commit-reach.h" > @@ -708,7 +707,8 @@ static int in_commit_list(const struct commit_list *want, struct commit *c) > > /* > * Test whether the candidate is contained in the list. > - * Do not recurse to find out, though, but return -1 if inconclusive. > + * Do not recurse to find out, though, but return CONTAINS_UNKNOWN if > + * inconclusive.
Okay so the code does return CONTAINS_UNKNOWN which is an enum beginning at 0, so this makes sense.
Show 46 quoted lines
> */
> static enum contains_result contains_test(struct commit *candidate,
> const struct commit_list *want,
> @@ -743,9 +743,9 @@ static void push_to_contains_stack(struct commit *candidate, struct contains_sta
> contains_stack->contains_stack[contains_stack->nr++].parents = candidate->parents;
> }
>
> -static enum contains_result contains_tag_algo(struct commit *candidate,
> - const struct commit_list *want,
> - struct contains_cache *cache)
> +static enum contains_result contains_algo(struct commit *candidate,
> + struct commit_list *want,
> + struct contains_cache *cache)
> {
> struct contains_stack contains_stack = { 0, 0, NULL };
> enum contains_result result;
> @@ -765,6 +765,7 @@ static enum contains_result contains_tag_algo(struct commit *candidate,
> if (result != CONTAINS_UNKNOWN)
> return result;
>
> + *contains_cache_at(cache, candidate) = CONTAINS_IN_PROGRESS;
> push_to_contains_stack(candidate, &contains_stack);
> while (contains_stack.nr) {
> struct contains_stack_entry *entry = &contains_stack.contains_stack[contains_stack.nr - 1];
> @@ -776,8 +777,8 @@ static enum contains_result contains_tag_algo(struct commit *candidate,
> contains_stack.nr--;
> }
> /*
> - * If we just popped the stack, parents->item has been marked,
> - * therefore contains_test will return a meaningful yes/no.
> + * A parent may have just been popped and marked, or may still
> + * be active when replacement refs create a cycle.
> */
> else switch (contains_test(parents->item, want, cache, cutoff)) {
> case CONTAINS_YES:
> @@ -787,21 +788,41 @@ static enum contains_result contains_tag_algo(struct commit *candidate,
> case CONTAINS_NO:
> entry->parents = parents->next;
> break;
> + case CONTAINS_IN_PROGRESS:
> + /*
> + * Partial negative answers are not safe across a cycle.
> + * Discard them and use the cycle-safe reachability walk.
> + */
> + goto cycle;
>If I understand this correctly, we now use CONTAINS_IN_PROGRESS to showcase a commit for which we still don't have a result. Since any commit with UNKNOWN will start a recursive search through its parents.
So with this if we encounter a CONTAINS_IN_PROGRESS while recursion, this would indicate that we hit a cyclic graph and so go to the fallback of using repo_is_descendant_of(). So this avoids an infinite recursion in such instances. Makes sense.
Show 112 quoted lines
> case CONTAINS_UNKNOWN:
> + *contains_cache_at(cache, parents->item) =
> + CONTAINS_IN_PROGRESS;
> push_to_contains_stack(parents->item, &contains_stack);
> break;
> }
> }
> free(contains_stack.contains_stack);
> return contains_test(candidate, want, cache, cutoff);
> +
> +cycle:
> + free(contains_stack.contains_stack);
> + clear_contains_cache(cache);
> + init_contains_cache(cache);
> +
> + result = repo_is_descendant_of(the_repository, candidate, want);
> + if (result < 0)
> + exit(128);
> + *contains_cache_at(cache, candidate) =
> + result ? CONTAINS_YES : CONTAINS_NO;
> + return result ? CONTAINS_YES : CONTAINS_NO;
> }
>
> -int commit_contains(struct ref_filter *filter, struct commit *commit,
> - struct commit_list *list, struct contains_cache *cache)
> +int commit_contains(struct commit *commit, struct commit_list *list,
> + struct contains_cache *cache)
> {
> - if (filter->with_commit_tag_algo)
> - return contains_tag_algo(commit, list, cache) == CONTAINS_YES;
> - return repo_is_descendant_of(the_repository, commit, list);
> + if (!list)
> + return 1;
> + return contains_algo(commit, list, cache) == CONTAINS_YES;
> }
>
> int can_all_from_reach_with_flag(struct object_array *from,
> diff --git a/commit-reach.h b/commit-reach.h
> index 3f3a563d8a..144dc56275 100644
> --- a/commit-reach.h
> +++ b/commit-reach.h
> @@ -5,7 +5,6 @@
> #include "commit-slab.h"
>
> struct commit_list;
> -struct ref_filter;
> struct object_id;
> struct object_array;
>
> @@ -73,13 +72,21 @@ int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid);
> enum contains_result {
> CONTAINS_UNKNOWN = 0,
> CONTAINS_NO,
> - CONTAINS_YES
> + CONTAINS_YES,
> + CONTAINS_IN_PROGRESS
> };
>
> define_commit_slab(contains_cache, enum contains_result);
>
> -int commit_contains(struct ref_filter *filter, struct commit *commit,
> - struct commit_list *list, struct contains_cache *cache);
> +/*
> + * Return whether "commit" is a descendant of any commit in "list". An empty
> + * list matches.
> + *
> + * "cache" records answers for one fixed "list". Clear it before changing the
> + * list.
> + */
> +int commit_contains(struct commit *commit, struct commit_list *list,
> + struct contains_cache *cache);
>
> /*
> * Determine if every commit in 'from' can reach at least one commit
> diff --git a/ref-filter.c b/ref-filter.c
> index 1da4c0e60d..7788147959 100644
> --- a/ref-filter.c
> +++ b/ref-filter.c
> @@ -2991,11 +2991,13 @@ static struct ref_array_item *apply_ref_filter(const struct reference *ref,
> return NULL;
> /* We perform the filtering for the '--contains' option... */
> if (filter->with_commit &&
> - !commit_contains(filter, commit, filter->with_commit, &filter->internal.contains_cache))
> + !commit_contains(commit, filter->with_commit,
> + &filter->internal.contains_cache))
> return NULL;
> /* ...or for the `--no-contains' option */
> if (filter->no_commit &&
> - commit_contains(filter, commit, filter->no_commit, &filter->internal.no_contains_cache))
> + commit_contains(commit, filter->no_commit,
> + &filter->internal.no_contains_cache))
> return NULL;
> }
>
> diff --git a/ref-filter.h b/ref-filter.h
> index 120221b47f..9e14afca9c 100644
> --- a/ref-filter.h
> +++ b/ref-filter.h
> @@ -73,10 +73,9 @@ struct ref_filter {
> struct commit_list *reachable_from;
> struct commit_list *unreachable_from;
>
> - unsigned int with_commit_tag_algo : 1,
> - match_as_path : 1,
> - ignore_case : 1,
> - detached : 1;
> + unsigned int match_as_path : 1,
> + ignore_case : 1,
> + detached : 1;
> unsigned int kind,
> lines;
> int abbrev,Nit: With the changes above. I do wish it was split into two commits. 1. Fix cyclic recursions in the algo. 2. Use the algo for all filter types.
Show 31 quoted lines
> diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c
> index 5d86a96c17..82235f713e 100644
> --- a/t/helper/test-reach.c
> +++ b/t/helper/test-reach.c
> @@ -6,7 +6,6 @@
> #include "gettext.h"
> #include "hex.h"
> #include "object-name.h"
> -#include "ref-filter.h"
> #include "setup.h"
> #include "string-list.h"
> #include "tag.h"
> @@ -138,16 +137,11 @@ int cmd__reach(int ac, const char **av)
>
> printf("%s(X,_,_,0,0):%d\n", av[1], can_all_from_reach_with_flag(&X_obj, 2, 4, 0, 0));
> } else if (!strcmp(av[1], "commit_contains")) {
> - struct ref_filter filter = REF_FILTER_INIT;
> struct contains_cache cache;
> init_contains_cache(&cache);
>
> - if (ac > 2 && !strcmp(av[2], "--tag"))
> - filter.with_commit_tag_algo = 1;
> - else
> - filter.with_commit_tag_algo = 0;
> -
> - printf("%s(_,A,X,_):%d\n", av[1], commit_contains(&filter, A, X, &cache));
> + printf("%s(_,A,X,_):%d\n", av[1],
> + commit_contains(A, X, &cache));
> clear_contains_cache(&cache);
> } else if (!strcmp(av[1], "get_reachable_subset")) {
> const int reachable_flag = 1;Makes sense.
Show 37 quoted lines
> diff --git a/t/perf/p1500-graph-walks.sh b/t/perf/p1500-graph-walks.sh
> index 5b23ce5db9..ac68fdbacd 100755
> --- a/t/perf/p1500-graph-walks.sh
> +++ b/t/perf/p1500-graph-walks.sh
> @@ -5,6 +5,8 @@ test_description='Commit walk performance tests'
>
> test_perf_large_repo
>
> +contains_ref_limit=8192
> +
> test_expect_success 'setup' '
> git for-each-ref --format="%(refname)" "refs/heads/*" "refs/tags/*" >allrefs &&
> sort -r allrefs | head -n 50 >refs &&
> @@ -32,10 +34,25 @@ test_expect_success 'setup' '
> echo "X:$line" >>test-tool-tags || return 1
> done &&
>
> + git rev-list --first-parent --max-count=$contains_ref_limit HEAD >contains-commits &&
> + contains_ref_count=$(wc -l <contains-commits) &&
> + test "$contains_ref_count" -gt 0 &&
> + contains_base=$(tail -n 1 contains-commits) &&
> + export contains_base &&
> + 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 $(git rev-parse HEAD^{tree})) &&
> git update-ref refs/heads/disjoint-base $commit &&
>
> - git commit-graph write --reachable
> + git commit-graph write --reachable &&
> +
> + git for-each-ref --contains="$contains_base" \
> + refs/contains-perf/ >actual &&
> + test_line_count = $contains_ref_count actualShouldn't this be a separate test and not a part of the setup?
Show 12 quoted lines
> ' > > test_perf 'ahead-behind counts: git for-each-ref' ' > @@ -62,6 +79,11 @@ 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="$contains_base" \ > + refs/contains-perf/ >/dev/null > +' > +
Ah! we also have this, so perhaps moving the `test_line_count` here and dropping it above would be better.
Show 96 quoted lines
> 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..169cc70c23 100755
> --- a/t/t6301-for-each-ref-errors.sh
> +++ b/t/t6301-for-each-ref-errors.sh
> @@ -52,6 +52,24 @@ 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" &&
> + test_must_fail git for-each-ref --contains=HEAD \
> + refs/heads/missing-parent >out 2>err &&
> + test_must_be_empty out &&
> + test_grep "unable to parse commit $MISSING" err
> +'
> +
> test_expect_success 'ahead-behind requires an argument' '
> test_must_fail git for-each-ref \
> --format="%(ahead-behind)" 2>err &&
> diff --git a/t/t6302-for-each-ref-filter.sh b/t/t6302-for-each-ref-filter.sh
> index 7f060d97bf..423505d1fb 100755
> --- a/t/t6302-for-each-ref-filter.sh
> +++ b/t/t6302-for-each-ref-filter.sh
> @@ -177,6 +177,27 @@ test_expect_success 'filtering with --contains and --no-contains' '
> test_cmp expect actual
> '
>
> +test_expect_success 'contains handles cyclic replacement histories' '
> + one=$(git rev-parse one) &&
> + three=$(git rev-parse three) &&
> + test_when_finished "
> + git replace -d $one
> + git replace -d $three
> + git tag -d cycle-a cycle-b
> + " &&
> + git tag cycle-a "$one" &&
> + git tag cycle-b "$three" &&
> + git replace --graft "$one" "$three" two &&
> + git replace --graft "$three" "$one" &&
> + cat >expect <<-\EOF &&
> + refs/tags/cycle-a
> + refs/tags/cycle-b
> + EOF
> + git for-each-ref --format="%(refname)" --contains=two \
> + "refs/tags/cycle-*" >actual &&
> + test_cmp expect actual
> +'
> +
> test_expect_success '%(color) must fail' '
> test_must_fail git for-each-ref --format="%(color)%(refname)"
> '
> diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
> index b5b314e570..1ecc2571c2 100755
> --- a/t/t6600-test-reach.sh
> +++ b/t/t6600-test-reach.sh
> @@ -286,8 +286,7 @@ test_expect_success 'commit_contains:hit' '
> X:commit-9-3
> EOF
> echo "commit_contains(_,A,X,_):1" >expect &&
> - test_all_modes commit_contains &&
> - test_all_modes commit_contains --tag
> + test_all_modes commit_contains
> '
>
> test_expect_success 'commit_contains:miss' '
> @@ -303,8 +302,7 @@ test_expect_success 'commit_contains:miss' '
> X:commit-9-3
> EOF
> echo "commit_contains(_,A,X,_):0" >expect &&
> - test_all_modes commit_contains &&
> - test_all_modes commit_contains --tag
> + test_all_modes commit_contains
> '
>
> test_expect_success 'rev-list: basic topo-order' '
>
> ---
> base-commit: 9ac3f193c05c2237e2b14ebaa1149e9fc8a1abe0
> change-id: 20260607-ref-filter-memoized-contains-7cb6b3bccad1
>
> Best regards,
> --
> Tamir Duberstein <tamird@gmail.com>Overall the patch looks great. The perf improvements are also very welcome. Some small nits from me.
Thanks