{"thread":{"id":"65768","subject":"[PATCH] ref-filter: reuse --contains traversal results","startedAt":"2026-06-08T03:33:36Z","lastAt":"2026-06-08T23:56:42Z","messageCount":7,"participants":["Tamir Duberstein","Karthik Nayak","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"544858","messageId":"20260607-ref-filter-memoized-contains-v1-1-a1972dde9c76@gmail.com","threadId":"65768","inReplyTo":null,"subject":"[PATCH] ref-filter: reuse --contains traversal results","fromName":"Tamir Duberstein","fromEmail":"tamird@gmail.com","sentAt":"2026-06-08T03:33:29Z","receivedAt":"2026-06-08T03:33:36Z","isPatch":true,"body":"git branch and git for-each-ref call repo_is_descendant_of() for each\ncandidate selected by --contains or --no-contains. Each call starts a\nnew graph walk, so refs with shared history repeatedly traverse the same\ncommits.\n\nffc4b8012d (tag: speed up --contains calculation, 2011-06-11) introduced\nthe tag traversal that caches positive and negative answers across\ncandidates. ee2bd06b0f (ref-filter: implement '--contains' option,\n2015-07-07) preserved the branch and tag implementations when ref-filter\nlearned --contains. 008ed7df930 (tag.c: use the correct algorithm for\nthe '--contains' option, 2015-10-18) noted that they should be unified.\n\nUse the memoized traversal for every ref-filter contains check and\nremove the implementation selector. The cache records answers for one\nfixed target list, so document that callers must clear it before\nchanging the list.\n\nThe memoized depth-first walk assumes acyclic ancestry, but replacement\nrefs can create cycles. Track commits while they are on the walk. If a\ncycle is found, discard partial cache entries and use\nrepo_is_descendant_of() for that candidate.\n\nThe branch and for-each-ref path passed repo_is_descendant_of() through\na Boolean interface. In configurations where it returned -1 for missing\nancestry, ref-filter treated the error as \"contains\". The memoized path\ninstead fails when ancestry cannot be parsed, as git tag already did.\nDuring review of the 2018 reachability series, making parse failures\nfatal was explicitly deferred because that series was intended to\npreserve behavior. Unifying the implementations now makes all callers\nfail consistently instead of preserving that accidental Boolean\ninterpretation.\n\nThe added p1500 case uses up to 8,192 packed refs along one first-parent\nhistory. It improves from 0.68 to 0.03 seconds.\n\nOn a checkout with 62,174 remote-tracking refs, I ran:\n\n    hyperfine --warmup 0 --runs 3 \\\n        --command-name parent \\\n        '\"$parent\" branch -r --contains c78ae85f3ce7e >/dev/null' \\\n        --command-name this-commit \\\n        '\"$this\" branch -r --contains c78ae85f3ce7e >/dev/null'\n\nThe results were:\n\n             parent       this commit\n  elapsed    104.365 s     467.7 ms\n  user        93.702 s     220.2 ms\n  system       0.723 s     182.7 ms\n\nThe wall-time standard deviations were 11.356 seconds and 133.8\nmilliseconds, respectively, for a 223x speedup. Both commands produced\noutput with SHA-256\n2466f6e2b72aa16b1a2126eddb81c8a1b2764ee251204ac034c191a925aa896f.\n\nBoth revisions were rebuilt with the default -O2 flags using Apple clang\n21.0.0 on macOS 26.5. The machine was a MacBook Pro (Mac16,6) with a\n16-core Apple M4 Max (12 performance and four efficiency cores) and 128\nGB RAM.\n\nLink: https://lore.kernel.org/git/1445163904-24611-1-git-send-email-Karthik.188@gmail.com/\nLink: https://lore.kernel.org/git/20180723204112.233274-1-jonathantanmy@google.com/\nLink: https://lore.kernel.org/git/24424e55-7fa8-d05b-bc39-e14b4d5abcb6@gmail.com/\nSigned-off-by: Tamir Duberstein <tamird@gmail.com>\n---\n builtin/tag.c                  |  1 -\n commit-reach.c                 | 45 +++++++++++++++++++++++++++++++-----------\n commit-reach.h                 | 15 ++++++++++----\n ref-filter.c                   |  6 ++++--\n ref-filter.h                   |  7 +++----\n t/helper/test-reach.c          | 10 ++--------\n t/perf/p1500-graph-walks.sh    | 24 +++++++++++++++++++++-\n t/t6301-for-each-ref-errors.sh | 18 +++++++++++++++++\n t/t6302-for-each-ref-filter.sh | 21 ++++++++++++++++++++\n t/t6600-test-reach.sh          |  6 ++----\n 10 files changed, 117 insertions(+), 36 deletions(-)\n\ndiff --git a/builtin/tag.c b/builtin/tag.c\nindex d51c2e3349..9f34d948d4 100644\n--- a/builtin/tag.c\n+++ b/builtin/tag.c\n@@ -71,7 +71,6 @@ static int list_tags(struct ref_filter *filter, struct ref_sorting *sorting,\n \n \tif (verify_ref_format(format))\n \t\tdie(_(\"unable to parse format string\"));\n-\tfilter->with_commit_tag_algo = 1;\n \tfilter_and_format_refs(filter, FILTER_REFS_TAGS, sorting, format);\n \n \tfree(to_free);\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 9b3ea46d6f..6e599a3670 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -6,7 +6,6 @@\n #include \"decorate.h\"\n #include \"hex.h\"\n #include \"prio-queue.h\"\n-#include \"ref-filter.h\"\n #include \"revision.h\"\n #include \"tag.h\"\n #include \"commit-reach.h\"\n@@ -708,7 +707,8 @@ static int in_commit_list(const struct commit_list *want, struct commit *c)\n \n /*\n  * Test whether the candidate is contained in the list.\n- * Do not recurse to find out, though, but return -1 if inconclusive.\n+ * Do not recurse to find out, though, but return CONTAINS_UNKNOWN if\n+ * inconclusive.\n  */\n static enum contains_result contains_test(struct commit *candidate,\n \t\t\t\t\t  const struct commit_list *want,\n@@ -743,9 +743,9 @@ static void push_to_contains_stack(struct commit *candidate, struct contains_sta\n \tcontains_stack->contains_stack[contains_stack->nr++].parents = candidate->parents;\n }\n \n-static enum contains_result contains_tag_algo(struct commit *candidate,\n-\t\t\t\t\t      const struct commit_list *want,\n-\t\t\t\t\t      struct contains_cache *cache)\n+static enum contains_result contains_algo(struct commit *candidate,\n+\t\t\t\t\t  struct commit_list *want,\n+\t\t\t\t\t  struct contains_cache *cache)\n {\n \tstruct contains_stack contains_stack = { 0, 0, NULL };\n \tenum contains_result result;\n@@ -765,6 +765,7 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n \tif (result != CONTAINS_UNKNOWN)\n \t\treturn result;\n \n+\t*contains_cache_at(cache, candidate) = CONTAINS_IN_PROGRESS;\n \tpush_to_contains_stack(candidate, &contains_stack);\n \twhile (contains_stack.nr) {\n \t\tstruct contains_stack_entry *entry = &contains_stack.contains_stack[contains_stack.nr - 1];\n@@ -776,8 +777,8 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n \t\t\tcontains_stack.nr--;\n \t\t}\n \t\t/*\n-\t\t * If we just popped the stack, parents->item has been marked,\n-\t\t * therefore contains_test will return a meaningful yes/no.\n+\t\t * A parent may have just been popped and marked, or may still\n+\t\t * be active when replacement refs create a cycle.\n \t\t */\n \t\telse switch (contains_test(parents->item, want, cache, cutoff)) {\n \t\tcase CONTAINS_YES:\n@@ -787,21 +788,41 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n \t\tcase CONTAINS_NO:\n \t\t\tentry->parents = parents->next;\n \t\t\tbreak;\n+\t\tcase CONTAINS_IN_PROGRESS:\n+\t\t\t/*\n+\t\t\t * Partial negative answers are not safe across a cycle.\n+\t\t\t * Discard them and use the cycle-safe reachability walk.\n+\t\t\t */\n+\t\t\tgoto cycle;\n \t\tcase CONTAINS_UNKNOWN:\n+\t\t\t*contains_cache_at(cache, parents->item) =\n+\t\t\t\tCONTAINS_IN_PROGRESS;\n \t\t\tpush_to_contains_stack(parents->item, &contains_stack);\n \t\t\tbreak;\n \t\t}\n \t}\n \tfree(contains_stack.contains_stack);\n \treturn contains_test(candidate, want, cache, cutoff);\n+\n+cycle:\n+\tfree(contains_stack.contains_stack);\n+\tclear_contains_cache(cache);\n+\tinit_contains_cache(cache);\n+\n+\tresult = repo_is_descendant_of(the_repository, candidate, want);\n+\tif (result < 0)\n+\t\texit(128);\n+\t*contains_cache_at(cache, candidate) =\n+\t\tresult ? CONTAINS_YES : CONTAINS_NO;\n+\treturn result ? CONTAINS_YES : CONTAINS_NO;\n }\n \n-int commit_contains(struct ref_filter *filter, struct commit *commit,\n-\t\t    struct commit_list *list, struct contains_cache *cache)\n+int commit_contains(struct commit *commit, struct commit_list *list,\n+\t\t    struct contains_cache *cache)\n {\n-\tif (filter->with_commit_tag_algo)\n-\t\treturn contains_tag_algo(commit, list, cache) == CONTAINS_YES;\n-\treturn repo_is_descendant_of(the_repository, commit, list);\n+\tif (!list)\n+\t\treturn 1;\n+\treturn contains_algo(commit, list, cache) == CONTAINS_YES;\n }\n \n int can_all_from_reach_with_flag(struct object_array *from,\ndiff --git a/commit-reach.h b/commit-reach.h\nindex 3f3a563d8a..144dc56275 100644\n--- a/commit-reach.h\n+++ b/commit-reach.h\n@@ -5,7 +5,6 @@\n #include \"commit-slab.h\"\n \n struct commit_list;\n-struct ref_filter;\n struct object_id;\n struct object_array;\n \n@@ -73,13 +72,21 @@ int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid);\n enum contains_result {\n \tCONTAINS_UNKNOWN = 0,\n \tCONTAINS_NO,\n-\tCONTAINS_YES\n+\tCONTAINS_YES,\n+\tCONTAINS_IN_PROGRESS\n };\n \n define_commit_slab(contains_cache, enum contains_result);\n \n-int commit_contains(struct ref_filter *filter, struct commit *commit,\n-\t\t    struct commit_list *list, struct contains_cache *cache);\n+/*\n+ * Return whether \"commit\" is a descendant of any commit in \"list\". An empty\n+ * list matches.\n+ *\n+ * \"cache\" records answers for one fixed \"list\". Clear it before changing the\n+ * list.\n+ */\n+int commit_contains(struct commit *commit, struct commit_list *list,\n+\t\t    struct contains_cache *cache);\n \n /*\n  * Determine if every commit in 'from' can reach at least one commit\ndiff --git a/ref-filter.c b/ref-filter.c\nindex 1da4c0e60d..7788147959 100644\n--- a/ref-filter.c\n+++ b/ref-filter.c\n@@ -2991,11 +2991,13 @@ static struct ref_array_item *apply_ref_filter(const struct reference *ref,\n \t\t\treturn NULL;\n \t\t/* We perform the filtering for the '--contains' option... */\n \t\tif (filter->with_commit &&\n-\t\t    !commit_contains(filter, commit, filter->with_commit, &filter->internal.contains_cache))\n+\t\t    !commit_contains(commit, filter->with_commit,\n+\t\t\t\t     &filter->internal.contains_cache))\n \t\t\treturn NULL;\n \t\t/* ...or for the `--no-contains' option */\n \t\tif (filter->no_commit &&\n-\t\t    commit_contains(filter, commit, filter->no_commit, &filter->internal.no_contains_cache))\n+\t\t    commit_contains(commit, filter->no_commit,\n+\t\t\t\t    &filter->internal.no_contains_cache))\n \t\t\treturn NULL;\n \t}\n \ndiff --git a/ref-filter.h b/ref-filter.h\nindex 120221b47f..9e14afca9c 100644\n--- a/ref-filter.h\n+++ b/ref-filter.h\n@@ -73,10 +73,9 @@ struct ref_filter {\n \tstruct commit_list *reachable_from;\n \tstruct commit_list *unreachable_from;\n \n-\tunsigned int with_commit_tag_algo : 1,\n-\t\tmatch_as_path : 1,\n-\t\tignore_case : 1,\n-\t\tdetached : 1;\n+\tunsigned int match_as_path : 1,\n+\t\t     ignore_case : 1,\n+\t\t     detached : 1;\n \tunsigned int kind,\n \t\tlines;\n \tint abbrev,\ndiff --git a/t/helper/test-reach.c b/t/helper/test-reach.c\nindex 5d86a96c17..82235f713e 100644\n--- a/t/helper/test-reach.c\n+++ b/t/helper/test-reach.c\n@@ -6,7 +6,6 @@\n #include \"gettext.h\"\n #include \"hex.h\"\n #include \"object-name.h\"\n-#include \"ref-filter.h\"\n #include \"setup.h\"\n #include \"string-list.h\"\n #include \"tag.h\"\n@@ -138,16 +137,11 @@ int cmd__reach(int ac, const char **av)\n \n \t\tprintf(\"%s(X,_,_,0,0):%d\\n\", av[1], can_all_from_reach_with_flag(&X_obj, 2, 4, 0, 0));\n \t} else if (!strcmp(av[1], \"commit_contains\")) {\n-\t\tstruct ref_filter filter = REF_FILTER_INIT;\n \t\tstruct contains_cache cache;\n \t\tinit_contains_cache(&cache);\n \n-\t\tif (ac > 2 && !strcmp(av[2], \"--tag\"))\n-\t\t\tfilter.with_commit_tag_algo = 1;\n-\t\telse\n-\t\t\tfilter.with_commit_tag_algo = 0;\n-\n-\t\tprintf(\"%s(_,A,X,_):%d\\n\", av[1], commit_contains(&filter, A, X, &cache));\n+\t\tprintf(\"%s(_,A,X,_):%d\\n\", av[1],\n+\t\t       commit_contains(A, X, &cache));\n \t\tclear_contains_cache(&cache);\n \t} else if (!strcmp(av[1], \"get_reachable_subset\")) {\n \t\tconst int reachable_flag = 1;\ndiff --git a/t/perf/p1500-graph-walks.sh b/t/perf/p1500-graph-walks.sh\nindex 5b23ce5db9..ac68fdbacd 100755\n--- a/t/perf/p1500-graph-walks.sh\n+++ b/t/perf/p1500-graph-walks.sh\n@@ -5,6 +5,8 @@ test_description='Commit walk performance tests'\n \n test_perf_large_repo\n \n+contains_ref_limit=8192\n+\n test_expect_success 'setup' '\n \tgit for-each-ref --format=\"%(refname)\" \"refs/heads/*\" \"refs/tags/*\" >allrefs &&\n \tsort -r allrefs | head -n 50 >refs &&\n@@ -32,10 +34,25 @@ test_expect_success 'setup' '\n \t\techo \"X:$line\" >>test-tool-tags || return 1\n \tdone &&\n \n+\tgit rev-list --first-parent --max-count=$contains_ref_limit HEAD >contains-commits &&\n+\tcontains_ref_count=$(wc -l <contains-commits) &&\n+\ttest \"$contains_ref_count\" -gt 0 &&\n+\tcontains_base=$(tail -n 1 contains-commits) &&\n+\texport contains_base &&\n+\tawk \"{\n+\t\tprintf \\\"update refs/contains-perf/%04d %s\\\\n\\\", NR, \\$1\n+\t}\" contains-commits |\n+\t\tgit update-ref --stdin &&\n+\tgit pack-refs --include \"refs/contains-perf/*\" &&\n+\n \tcommit=$(git commit-tree $(git rev-parse HEAD^{tree})) &&\n \tgit update-ref refs/heads/disjoint-base $commit &&\n \n-\tgit commit-graph write --reachable\n+\tgit commit-graph write --reachable &&\n+\n+\tgit for-each-ref --contains=\"$contains_base\" \\\n+\t\trefs/contains-perf/ >actual &&\n+\ttest_line_count = $contains_ref_count actual\n '\n \n test_perf 'ahead-behind counts: git for-each-ref' '\n@@ -62,6 +79,11 @@ test_perf 'contains: git tag --merged' '\n \txargs git tag --merged=HEAD <tags\n '\n \n+test_perf 'contains: git for-each-ref --contains' '\n+\tgit for-each-ref --contains=\"$contains_base\" \\\n+\t\trefs/contains-perf/ >/dev/null\n+'\n+\n test_perf 'is-base check: test-tool reach (refs)' '\n \ttest-tool reach get_branch_base_for_tip <test-tool-refs\n '\ndiff --git a/t/t6301-for-each-ref-errors.sh b/t/t6301-for-each-ref-errors.sh\nindex e06feb06e9..169cc70c23 100755\n--- a/t/t6301-for-each-ref-errors.sh\n+++ b/t/t6301-for-each-ref-errors.sh\n@@ -52,6 +52,24 @@ test_expect_success 'Missing objects are reported correctly' '\n \ttest_must_be_empty brief-err\n '\n \n+test_expect_success 'missing ancestors are reported by contains filters' '\n+\ttest_when_finished \"git update-ref -d refs/heads/missing-parent\" &&\n+\t{\n+\t\techo \"tree $(git rev-parse HEAD^{tree})\" &&\n+\t\techo \"parent $MISSING\" &&\n+\t\tgit cat-file commit HEAD |\n+\t\t\tsed -n -e \"/^author /p\" -e \"/^committer /p\" &&\n+\t\techo &&\n+\t\techo \"missing parent\"\n+\t} >commit &&\n+\tbroken=$(git hash-object -t commit -w commit) &&\n+\tgit update-ref refs/heads/missing-parent \"$broken\" &&\n+\ttest_must_fail git for-each-ref --contains=HEAD \\\n+\t\trefs/heads/missing-parent >out 2>err &&\n+\ttest_must_be_empty out &&\n+\ttest_grep \"unable to parse commit $MISSING\" err\n+'\n+\n test_expect_success 'ahead-behind requires an argument' '\n \ttest_must_fail git for-each-ref \\\n \t\t--format=\"%(ahead-behind)\" 2>err &&\ndiff --git a/t/t6302-for-each-ref-filter.sh b/t/t6302-for-each-ref-filter.sh\nindex 7f060d97bf..423505d1fb 100755\n--- a/t/t6302-for-each-ref-filter.sh\n+++ b/t/t6302-for-each-ref-filter.sh\n@@ -177,6 +177,27 @@ test_expect_success 'filtering with --contains and --no-contains' '\n \ttest_cmp expect actual\n '\n \n+test_expect_success 'contains handles cyclic replacement histories' '\n+\tone=$(git rev-parse one) &&\n+\tthree=$(git rev-parse three) &&\n+\ttest_when_finished \"\n+\t\tgit replace -d $one\n+\t\tgit replace -d $three\n+\t\tgit tag -d cycle-a cycle-b\n+\t\" &&\n+\tgit tag cycle-a \"$one\" &&\n+\tgit tag cycle-b \"$three\" &&\n+\tgit replace --graft \"$one\" \"$three\" two &&\n+\tgit replace --graft \"$three\" \"$one\" &&\n+\tcat >expect <<-\\EOF &&\n+\trefs/tags/cycle-a\n+\trefs/tags/cycle-b\n+\tEOF\n+\tgit for-each-ref --format=\"%(refname)\" --contains=two \\\n+\t\t\"refs/tags/cycle-*\" >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_expect_success '%(color) must fail' '\n \ttest_must_fail git for-each-ref --format=\"%(color)%(refname)\"\n '\ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nindex b5b314e570..1ecc2571c2 100755\n--- a/t/t6600-test-reach.sh\n+++ b/t/t6600-test-reach.sh\n@@ -286,8 +286,7 @@ test_expect_success 'commit_contains:hit' '\n \tX:commit-9-3\n \tEOF\n \techo \"commit_contains(_,A,X,_):1\" >expect &&\n-\ttest_all_modes commit_contains &&\n-\ttest_all_modes commit_contains --tag\n+\ttest_all_modes commit_contains\n '\n \n test_expect_success 'commit_contains:miss' '\n@@ -303,8 +302,7 @@ test_expect_success 'commit_contains:miss' '\n \tX:commit-9-3\n \tEOF\n \techo \"commit_contains(_,A,X,_):0\" >expect &&\n-\ttest_all_modes commit_contains &&\n-\ttest_all_modes commit_contains --tag\n+\ttest_all_modes commit_contains\n '\n \n test_expect_success 'rev-list: basic topo-order' '\n\n---\nbase-commit: 9ac3f193c05c2237e2b14ebaa1149e9fc8a1abe0\nchange-id: 20260607-ref-filter-memoized-contains-7cb6b3bccad1\n\nBest regards,\n--  \nTamir Duberstein <tamird@gmail.com>\n\n"},{"id":"544966","messageId":"CAOLa=ZS_U+u43SV9ELSEU6AT7rzEQ44BuHPAi1BAHEGQAnPoPw@mail.gmail.com","threadId":"65768","inReplyTo":"20260607-ref-filter-memoized-contains-v1-1-a1972dde9c76@gmail.com","subject":"Re: [PATCH] ref-filter: reuse --contains traversal results","fromName":"Karthik Nayak","fromEmail":"karthik.188@gmail.com","sentAt":"2026-06-08T21:18:39Z","receivedAt":"2026-06-08T21:18:42Z","isPatch":true,"body":"Tamir Duberstein <tamird@gmail.com> writes:\n\n> git branch and git for-each-ref call repo_is_descendant_of() for each\n> candidate selected by --contains or --no-contains. Each call starts a\n> new graph walk, so refs with shared history repeatedly traverse the same\n> commits.\n>\n> ffc4b8012d (tag: speed up --contains calculation, 2011-06-11) introduced\n> the tag traversal that caches positive and negative answers across\n> candidates. ee2bd06b0f (ref-filter: implement '--contains' option,\n> 2015-07-07) preserved the branch and tag implementations when ref-filter\n> learned --contains. 008ed7df930 (tag.c: use the correct algorithm for\n> the '--contains' option, 2015-10-18) noted that they should be unified.\n>\n\nNicely explained. We should've merged this long ago, so this is a\nworthwhile change.\n\n> Use the memoized traversal for every ref-filter contains check and\n> remove the implementation selector. The cache records answers for one\n> fixed target list, so document that callers must clear it before\n> changing the list.\n>\n> The memoized depth-first walk assumes acyclic ancestry, but replacement\n> refs can create cycles. Track commits while they are on the walk. If a\n> cycle is found, discard partial cache entries and use\n> repo_is_descendant_of() for that candidate.\n>\n> The branch and for-each-ref path passed repo_is_descendant_of() through\n> a Boolean interface. In configurations where it returned -1 for missing\n> ancestry, ref-filter treated the error as \"contains\". The memoized path\n> instead fails when ancestry cannot be parsed, as git tag already did.\n> During review of the 2018 reachability series, making parse failures\n> fatal was explicitly deferred because that series was intended to\n> preserve behavior. Unifying the implementations now makes all callers\n> fail consistently instead of preserving that accidental Boolean\n> interpretation.\n>\n> The added p1500 case uses up to 8,192 packed refs along one first-parent\n> history. It improves from 0.68 to 0.03 seconds.\n>\n> On a checkout with 62,174 remote-tracking refs, I ran:\n>\n>     hyperfine --warmup 0 --runs 3 \\\n>         --command-name parent \\\n>         '\"$parent\" branch -r --contains c78ae85f3ce7e >/dev/null' \\\n>         --command-name this-commit \\\n>         '\"$this\" branch -r --contains c78ae85f3ce7e >/dev/null'\n>\n> The results were:\n>\n>              parent       this commit\n>   elapsed    104.365 s     467.7 ms\n>   user        93.702 s     220.2 ms\n>   system       0.723 s     182.7 ms\n>\n> The wall-time standard deviations were 11.356 seconds and 133.8\n> milliseconds, respectively, for a 223x speedup. Both commands produced\n> output with SHA-256\n> 2466f6e2b72aa16b1a2126eddb81c8a1b2764ee251204ac034c191a925aa896f.\n>\n> Both revisions were rebuilt with the default -O2 flags using Apple clang\n> 21.0.0 on macOS 26.5. The machine was a MacBook Pro (Mac16,6) with a\n> 16-core Apple M4 Max (12 performance and four efficiency cores) and 128\n> GB RAM.\n>\n> Link: https://lore.kernel.org/git/1445163904-24611-1-git-send-email-Karthik.188@gmail.com/\n> Link: https://lore.kernel.org/git/20180723204112.233274-1-jonathantanmy@google.com/\n> Link: https://lore.kernel.org/git/24424e55-7fa8-d05b-bc39-e14b4d5abcb6@gmail.com/\n> Signed-off-by: Tamir Duberstein <tamird@gmail.com>\n> ---\n>  builtin/tag.c                  |  1 -\n>  commit-reach.c                 | 45 +++++++++++++++++++++++++++++++-----------\n>  commit-reach.h                 | 15 ++++++++++----\n>  ref-filter.c                   |  6 ++++--\n>  ref-filter.h                   |  7 +++----\n>  t/helper/test-reach.c          | 10 ++--------\n>  t/perf/p1500-graph-walks.sh    | 24 +++++++++++++++++++++-\n>  t/t6301-for-each-ref-errors.sh | 18 +++++++++++++++++\n>  t/t6302-for-each-ref-filter.sh | 21 ++++++++++++++++++++\n>  t/t6600-test-reach.sh          |  6 ++----\n>  10 files changed, 117 insertions(+), 36 deletions(-)\n>\n> diff --git a/builtin/tag.c b/builtin/tag.c\n> index d51c2e3349..9f34d948d4 100644\n> --- a/builtin/tag.c\n> +++ b/builtin/tag.c\n> @@ -71,7 +71,6 @@ static int list_tags(struct ref_filter *filter, struct ref_sorting *sorting,\n>\n>  \tif (verify_ref_format(format))\n>  \t\tdie(_(\"unable to parse format string\"));\n> -\tfilter->with_commit_tag_algo = 1;\n\nWe were selectively using the algo for `git tag`, like mentioned I guess\nwe'll entirely remove `with_commit_tag_algo` below somewhere\n\n>  \tfilter_and_format_refs(filter, FILTER_REFS_TAGS, sorting, format);\n>\n>  \tfree(to_free);\n> diff --git a/commit-reach.c b/commit-reach.c\n> index 9b3ea46d6f..6e599a3670 100644\n> --- a/commit-reach.c\n> +++ b/commit-reach.c\n> @@ -6,7 +6,6 @@\n>  #include \"decorate.h\"\n>  #include \"hex.h\"\n>  #include \"prio-queue.h\"\n> -#include \"ref-filter.h\"\n>  #include \"revision.h\"\n>  #include \"tag.h\"\n>  #include \"commit-reach.h\"\n> @@ -708,7 +707,8 @@ static int in_commit_list(const struct commit_list *want, struct commit *c)\n>\n>  /*\n>   * Test whether the candidate is contained in the list.\n> - * Do not recurse to find out, though, but return -1 if inconclusive.\n> + * Do not recurse to find out, though, but return CONTAINS_UNKNOWN if\n> + * inconclusive.\n\nOkay so the code does return CONTAINS_UNKNOWN which is an enum beginning\nat 0, so this makes sense.\n\n>   */\n>  static enum contains_result contains_test(struct commit *candidate,\n>  \t\t\t\t\t  const struct commit_list *want,\n> @@ -743,9 +743,9 @@ static void push_to_contains_stack(struct commit *candidate, struct contains_sta\n>  \tcontains_stack->contains_stack[contains_stack->nr++].parents = candidate->parents;\n>  }\n>\n> -static enum contains_result contains_tag_algo(struct commit *candidate,\n> -\t\t\t\t\t      const struct commit_list *want,\n> -\t\t\t\t\t      struct contains_cache *cache)\n> +static enum contains_result contains_algo(struct commit *candidate,\n> +\t\t\t\t\t  struct commit_list *want,\n> +\t\t\t\t\t  struct contains_cache *cache)\n>  {\n>  \tstruct contains_stack contains_stack = { 0, 0, NULL };\n>  \tenum contains_result result;\n> @@ -765,6 +765,7 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n>  \tif (result != CONTAINS_UNKNOWN)\n>  \t\treturn result;\n>\n> +\t*contains_cache_at(cache, candidate) = CONTAINS_IN_PROGRESS;\n>  \tpush_to_contains_stack(candidate, &contains_stack);\n>  \twhile (contains_stack.nr) {\n>  \t\tstruct contains_stack_entry *entry = &contains_stack.contains_stack[contains_stack.nr - 1];\n> @@ -776,8 +777,8 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n>  \t\t\tcontains_stack.nr--;\n>  \t\t}\n>  \t\t/*\n> -\t\t * If we just popped the stack, parents->item has been marked,\n> -\t\t * therefore contains_test will return a meaningful yes/no.\n> +\t\t * A parent may have just been popped and marked, or may still\n> +\t\t * be active when replacement refs create a cycle.\n>  \t\t */\n>  \t\telse switch (contains_test(parents->item, want, cache, cutoff)) {\n>  \t\tcase CONTAINS_YES:\n> @@ -787,21 +788,41 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n>  \t\tcase CONTAINS_NO:\n>  \t\t\tentry->parents = parents->next;\n>  \t\t\tbreak;\n> +\t\tcase CONTAINS_IN_PROGRESS:\n> +\t\t\t/*\n> +\t\t\t * Partial negative answers are not safe across a cycle.\n> +\t\t\t * Discard them and use the cycle-safe reachability walk.\n> +\t\t\t */\n> +\t\t\tgoto cycle;\n>\n\nIf I understand this correctly, we now use CONTAINS_IN_PROGRESS to\nshowcase a commit for which we still don't have a result. Since any\ncommit with UNKNOWN will start a recursive search through its parents.\n\nSo with this if we encounter a CONTAINS_IN_PROGRESS while recursion,\nthis would indicate that we hit a cyclic graph and so go to the fallback\nof using repo_is_descendant_of(). So this avoids an infinite recursion\nin such instances. Makes sense.\n\n>  \t\tcase CONTAINS_UNKNOWN:\n> +\t\t\t*contains_cache_at(cache, parents->item) =\n> +\t\t\t\tCONTAINS_IN_PROGRESS;\n>  \t\t\tpush_to_contains_stack(parents->item, &contains_stack);\n>  \t\t\tbreak;\n>  \t\t}\n>  \t}\n>  \tfree(contains_stack.contains_stack);\n>  \treturn contains_test(candidate, want, cache, cutoff);\n> +\n> +cycle:\n> +\tfree(contains_stack.contains_stack);\n> +\tclear_contains_cache(cache);\n> +\tinit_contains_cache(cache);\n> +\n> +\tresult = repo_is_descendant_of(the_repository, candidate, want);\n> +\tif (result < 0)\n> +\t\texit(128);\n> +\t*contains_cache_at(cache, candidate) =\n> +\t\tresult ? CONTAINS_YES : CONTAINS_NO;\n> +\treturn result ? CONTAINS_YES : CONTAINS_NO;\n>  }\n>\n> -int commit_contains(struct ref_filter *filter, struct commit *commit,\n> -\t\t    struct commit_list *list, struct contains_cache *cache)\n> +int commit_contains(struct commit *commit, struct commit_list *list,\n> +\t\t    struct contains_cache *cache)\n>  {\n> -\tif (filter->with_commit_tag_algo)\n> -\t\treturn contains_tag_algo(commit, list, cache) == CONTAINS_YES;\n> -\treturn repo_is_descendant_of(the_repository, commit, list);\n> +\tif (!list)\n> +\t\treturn 1;\n> +\treturn contains_algo(commit, list, cache) == CONTAINS_YES;\n>  }\n>\n>  int can_all_from_reach_with_flag(struct object_array *from,\n> diff --git a/commit-reach.h b/commit-reach.h\n> index 3f3a563d8a..144dc56275 100644\n> --- a/commit-reach.h\n> +++ b/commit-reach.h\n> @@ -5,7 +5,6 @@\n>  #include \"commit-slab.h\"\n>\n>  struct commit_list;\n> -struct ref_filter;\n>  struct object_id;\n>  struct object_array;\n>\n> @@ -73,13 +72,21 @@ int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid);\n>  enum contains_result {\n>  \tCONTAINS_UNKNOWN = 0,\n>  \tCONTAINS_NO,\n> -\tCONTAINS_YES\n> +\tCONTAINS_YES,\n> +\tCONTAINS_IN_PROGRESS\n>  };\n>\n>  define_commit_slab(contains_cache, enum contains_result);\n>\n> -int commit_contains(struct ref_filter *filter, struct commit *commit,\n> -\t\t    struct commit_list *list, struct contains_cache *cache);\n> +/*\n> + * Return whether \"commit\" is a descendant of any commit in \"list\". An empty\n> + * list matches.\n> + *\n> + * \"cache\" records answers for one fixed \"list\". Clear it before changing the\n> + * list.\n> + */\n> +int commit_contains(struct commit *commit, struct commit_list *list,\n> +\t\t    struct contains_cache *cache);\n>\n>  /*\n>   * Determine if every commit in 'from' can reach at least one commit\n> diff --git a/ref-filter.c b/ref-filter.c\n> index 1da4c0e60d..7788147959 100644\n> --- a/ref-filter.c\n> +++ b/ref-filter.c\n> @@ -2991,11 +2991,13 @@ static struct ref_array_item *apply_ref_filter(const struct reference *ref,\n>  \t\t\treturn NULL;\n>  \t\t/* We perform the filtering for the '--contains' option... */\n>  \t\tif (filter->with_commit &&\n> -\t\t    !commit_contains(filter, commit, filter->with_commit, &filter->internal.contains_cache))\n> +\t\t    !commit_contains(commit, filter->with_commit,\n> +\t\t\t\t     &filter->internal.contains_cache))\n>  \t\t\treturn NULL;\n>  \t\t/* ...or for the `--no-contains' option */\n>  \t\tif (filter->no_commit &&\n> -\t\t    commit_contains(filter, commit, filter->no_commit, &filter->internal.no_contains_cache))\n> +\t\t    commit_contains(commit, filter->no_commit,\n> +\t\t\t\t    &filter->internal.no_contains_cache))\n>  \t\t\treturn NULL;\n>  \t}\n>\n> diff --git a/ref-filter.h b/ref-filter.h\n> index 120221b47f..9e14afca9c 100644\n> --- a/ref-filter.h\n> +++ b/ref-filter.h\n> @@ -73,10 +73,9 @@ struct ref_filter {\n>  \tstruct commit_list *reachable_from;\n>  \tstruct commit_list *unreachable_from;\n>\n> -\tunsigned int with_commit_tag_algo : 1,\n> -\t\tmatch_as_path : 1,\n> -\t\tignore_case : 1,\n> -\t\tdetached : 1;\n> +\tunsigned int match_as_path : 1,\n> +\t\t     ignore_case : 1,\n> +\t\t     detached : 1;\n>  \tunsigned int kind,\n>  \t\tlines;\n>  \tint abbrev,\n\nNit: With the changes above. I do wish it was split into two commits.\n1. Fix cyclic recursions in the algo.\n2. Use the algo for all filter types.\n\n> diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c\n> index 5d86a96c17..82235f713e 100644\n> --- a/t/helper/test-reach.c\n> +++ b/t/helper/test-reach.c\n> @@ -6,7 +6,6 @@\n>  #include \"gettext.h\"\n>  #include \"hex.h\"\n>  #include \"object-name.h\"\n> -#include \"ref-filter.h\"\n>  #include \"setup.h\"\n>  #include \"string-list.h\"\n>  #include \"tag.h\"\n> @@ -138,16 +137,11 @@ int cmd__reach(int ac, const char **av)\n>\n>  \t\tprintf(\"%s(X,_,_,0,0):%d\\n\", av[1], can_all_from_reach_with_flag(&X_obj, 2, 4, 0, 0));\n>  \t} else if (!strcmp(av[1], \"commit_contains\")) {\n> -\t\tstruct ref_filter filter = REF_FILTER_INIT;\n>  \t\tstruct contains_cache cache;\n>  \t\tinit_contains_cache(&cache);\n>\n> -\t\tif (ac > 2 && !strcmp(av[2], \"--tag\"))\n> -\t\t\tfilter.with_commit_tag_algo = 1;\n> -\t\telse\n> -\t\t\tfilter.with_commit_tag_algo = 0;\n> -\n> -\t\tprintf(\"%s(_,A,X,_):%d\\n\", av[1], commit_contains(&filter, A, X, &cache));\n> +\t\tprintf(\"%s(_,A,X,_):%d\\n\", av[1],\n> +\t\t       commit_contains(A, X, &cache));\n>  \t\tclear_contains_cache(&cache);\n>  \t} else if (!strcmp(av[1], \"get_reachable_subset\")) {\n>  \t\tconst int reachable_flag = 1;\n\nMakes sense.\n\n> diff --git a/t/perf/p1500-graph-walks.sh b/t/perf/p1500-graph-walks.sh\n> index 5b23ce5db9..ac68fdbacd 100755\n> --- a/t/perf/p1500-graph-walks.sh\n> +++ b/t/perf/p1500-graph-walks.sh\n> @@ -5,6 +5,8 @@ test_description='Commit walk performance tests'\n>\n>  test_perf_large_repo\n>\n> +contains_ref_limit=8192\n> +\n>  test_expect_success 'setup' '\n>  \tgit for-each-ref --format=\"%(refname)\" \"refs/heads/*\" \"refs/tags/*\" >allrefs &&\n>  \tsort -r allrefs | head -n 50 >refs &&\n> @@ -32,10 +34,25 @@ test_expect_success 'setup' '\n>  \t\techo \"X:$line\" >>test-tool-tags || return 1\n>  \tdone &&\n>\n> +\tgit rev-list --first-parent --max-count=$contains_ref_limit HEAD >contains-commits &&\n> +\tcontains_ref_count=$(wc -l <contains-commits) &&\n> +\ttest \"$contains_ref_count\" -gt 0 &&\n> +\tcontains_base=$(tail -n 1 contains-commits) &&\n> +\texport contains_base &&\n> +\tawk \"{\n> +\t\tprintf \\\"update refs/contains-perf/%04d %s\\\\n\\\", NR, \\$1\n> +\t}\" contains-commits |\n> +\t\tgit update-ref --stdin &&\n> +\tgit pack-refs --include \"refs/contains-perf/*\" &&\n> +\n>  \tcommit=$(git commit-tree $(git rev-parse HEAD^{tree})) &&\n>  \tgit update-ref refs/heads/disjoint-base $commit &&\n>\n> -\tgit commit-graph write --reachable\n> +\tgit commit-graph write --reachable &&\n> +\n> +\tgit for-each-ref --contains=\"$contains_base\" \\\n> +\t\trefs/contains-perf/ >actual &&\n> +\ttest_line_count = $contains_ref_count actual\n\nShouldn't this be a separate test and not a part of the setup?\n\n>  '\n>\n>  test_perf 'ahead-behind counts: git for-each-ref' '\n> @@ -62,6 +79,11 @@ test_perf 'contains: git tag --merged' '\n>  \txargs git tag --merged=HEAD <tags\n>  '\n>\n> +test_perf 'contains: git for-each-ref --contains' '\n> +\tgit for-each-ref --contains=\"$contains_base\" \\\n> +\t\trefs/contains-perf/ >/dev/null\n> +'\n> +\n\nAh! we also have this, so perhaps moving the `test_line_count` here and\ndropping it above would be better.\n\n>  test_perf 'is-base check: test-tool reach (refs)' '\n>  \ttest-tool reach get_branch_base_for_tip <test-tool-refs\n>  '\n> diff --git a/t/t6301-for-each-ref-errors.sh b/t/t6301-for-each-ref-errors.sh\n> index e06feb06e9..169cc70c23 100755\n> --- a/t/t6301-for-each-ref-errors.sh\n> +++ b/t/t6301-for-each-ref-errors.sh\n> @@ -52,6 +52,24 @@ test_expect_success 'Missing objects are reported correctly' '\n>  \ttest_must_be_empty brief-err\n>  '\n>\n> +test_expect_success 'missing ancestors are reported by contains filters' '\n> +\ttest_when_finished \"git update-ref -d refs/heads/missing-parent\" &&\n> +\t{\n> +\t\techo \"tree $(git rev-parse HEAD^{tree})\" &&\n> +\t\techo \"parent $MISSING\" &&\n> +\t\tgit cat-file commit HEAD |\n> +\t\t\tsed -n -e \"/^author /p\" -e \"/^committer /p\" &&\n> +\t\techo &&\n> +\t\techo \"missing parent\"\n> +\t} > commit &&\n> +\tbroken=$(git hash-object -t commit -w commit) &&\n> +\tgit update-ref refs/heads/missing-parent \"$broken\" &&\n> +\ttest_must_fail git for-each-ref --contains=HEAD \\\n> +\t\trefs/heads/missing-parent >out 2>err &&\n> +\ttest_must_be_empty out &&\n> +\ttest_grep \"unable to parse commit $MISSING\" err\n> +'\n> +\n>  test_expect_success 'ahead-behind requires an argument' '\n>  \ttest_must_fail git for-each-ref \\\n>  \t\t--format=\"%(ahead-behind)\" 2>err &&\n> diff --git a/t/t6302-for-each-ref-filter.sh b/t/t6302-for-each-ref-filter.sh\n> index 7f060d97bf..423505d1fb 100755\n> --- a/t/t6302-for-each-ref-filter.sh\n> +++ b/t/t6302-for-each-ref-filter.sh\n> @@ -177,6 +177,27 @@ test_expect_success 'filtering with --contains and --no-contains' '\n>  \ttest_cmp expect actual\n>  '\n>\n> +test_expect_success 'contains handles cyclic replacement histories' '\n> +\tone=$(git rev-parse one) &&\n> +\tthree=$(git rev-parse three) &&\n> +\ttest_when_finished \"\n> +\t\tgit replace -d $one\n> +\t\tgit replace -d $three\n> +\t\tgit tag -d cycle-a cycle-b\n> +\t\" &&\n> +\tgit tag cycle-a \"$one\" &&\n> +\tgit tag cycle-b \"$three\" &&\n> +\tgit replace --graft \"$one\" \"$three\" two &&\n> +\tgit replace --graft \"$three\" \"$one\" &&\n> +\tcat >expect <<-\\EOF &&\n> +\trefs/tags/cycle-a\n> +\trefs/tags/cycle-b\n> +\tEOF\n> +\tgit for-each-ref --format=\"%(refname)\" --contains=two \\\n> +\t\t\"refs/tags/cycle-*\" >actual &&\n> +\ttest_cmp expect actual\n> +'\n> +\n>  test_expect_success '%(color) must fail' '\n>  \ttest_must_fail git for-each-ref --format=\"%(color)%(refname)\"\n>  '\n> diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\n> index b5b314e570..1ecc2571c2 100755\n> --- a/t/t6600-test-reach.sh\n> +++ b/t/t6600-test-reach.sh\n> @@ -286,8 +286,7 @@ test_expect_success 'commit_contains:hit' '\n>  \tX:commit-9-3\n>  \tEOF\n>  \techo \"commit_contains(_,A,X,_):1\" >expect &&\n> -\ttest_all_modes commit_contains &&\n> -\ttest_all_modes commit_contains --tag\n> +\ttest_all_modes commit_contains\n>  '\n>\n>  test_expect_success 'commit_contains:miss' '\n> @@ -303,8 +302,7 @@ test_expect_success 'commit_contains:miss' '\n>  \tX:commit-9-3\n>  \tEOF\n>  \techo \"commit_contains(_,A,X,_):0\" >expect &&\n> -\ttest_all_modes commit_contains &&\n> -\ttest_all_modes commit_contains --tag\n> +\ttest_all_modes commit_contains\n>  '\n>\n>  test_expect_success 'rev-list: basic topo-order' '\n>\n> ---\n> base-commit: 9ac3f193c05c2237e2b14ebaa1149e9fc8a1abe0\n> change-id: 20260607-ref-filter-memoized-contains-7cb6b3bccad1\n>\n> Best regards,\n> --\n> Tamir Duberstein <tamird@gmail.com>\n\nOverall the patch looks great. The perf improvements are also very\nwelcome. Some small nits from me.\n\nThanks\n"},{"id":"544971","messageId":"CAJ-ks9me7GjLwvQqJK21jPyYvUJWoV-HAMhPGPsLDDNdNZVzOg@mail.gmail.com","threadId":"65768","inReplyTo":"CAOLa=ZS_U+u43SV9ELSEU6AT7rzEQ44BuHPAi1BAHEGQAnPoPw@mail.gmail.com","subject":"Re: [PATCH] ref-filter: reuse --contains traversal results","fromName":"Tamir Duberstein","fromEmail":"tamird@gmail.com","sentAt":"2026-06-08T22:30:58Z","receivedAt":"2026-06-08T22:31:37Z","isPatch":true,"body":"On Mon, Jun 8, 2026 at 2:18 PM Karthik Nayak <karthik.188@gmail.com> wrote:\n>\n> Tamir Duberstein <tamird@gmail.com> writes:\n>\n> > git branch and git for-each-ref call repo_is_descendant_of() for each\n> > candidate selected by --contains or --no-contains. Each call starts a\n> > new graph walk, so refs with shared history repeatedly traverse the same\n> > commits.\n> >\n> > ffc4b8012d (tag: speed up --contains calculation, 2011-06-11) introduced\n> > the tag traversal that caches positive and negative answers across\n> > candidates. ee2bd06b0f (ref-filter: implement '--contains' option,\n> > 2015-07-07) preserved the branch and tag implementations when ref-filter\n> > learned --contains. 008ed7df930 (tag.c: use the correct algorithm for\n> > the '--contains' option, 2015-10-18) noted that they should be unified.\n> >\n>\n> Nicely explained. We should've merged this long ago, so this is a\n> worthwhile change.\n>\n> > Use the memoized traversal for every ref-filter contains check and\n> > remove the implementation selector. The cache records answers for one\n> > fixed target list, so document that callers must clear it before\n> > changing the list.\n> >\n> > The memoized depth-first walk assumes acyclic ancestry, but replacement\n> > refs can create cycles. Track commits while they are on the walk. If a\n> > cycle is found, discard partial cache entries and use\n> > repo_is_descendant_of() for that candidate.\n> >\n> > The branch and for-each-ref path passed repo_is_descendant_of() through\n> > a Boolean interface. In configurations where it returned -1 for missing\n> > ancestry, ref-filter treated the error as \"contains\". The memoized path\n> > instead fails when ancestry cannot be parsed, as git tag already did.\n> > During review of the 2018 reachability series, making parse failures\n> > fatal was explicitly deferred because that series was intended to\n> > preserve behavior. Unifying the implementations now makes all callers\n> > fail consistently instead of preserving that accidental Boolean\n> > interpretation.\n> >\n> > The added p1500 case uses up to 8,192 packed refs along one first-parent\n> > history. It improves from 0.68 to 0.03 seconds.\n> >\n> > On a checkout with 62,174 remote-tracking refs, I ran:\n> >\n> >     hyperfine --warmup 0 --runs 3 \\\n> >         --command-name parent \\\n> >         '\"$parent\" branch -r --contains c78ae85f3ce7e >/dev/null' \\\n> >         --command-name this-commit \\\n> >         '\"$this\" branch -r --contains c78ae85f3ce7e >/dev/null'\n> >\n> > The results were:\n> >\n> >              parent       this commit\n> >   elapsed    104.365 s     467.7 ms\n> >   user        93.702 s     220.2 ms\n> >   system       0.723 s     182.7 ms\n> >\n> > The wall-time standard deviations were 11.356 seconds and 133.8\n> > milliseconds, respectively, for a 223x speedup. Both commands produced\n> > output with SHA-256\n> > 2466f6e2b72aa16b1a2126eddb81c8a1b2764ee251204ac034c191a925aa896f.\n> >\n> > Both revisions were rebuilt with the default -O2 flags using Apple clang\n> > 21.0.0 on macOS 26.5. The machine was a MacBook Pro (Mac16,6) with a\n> > 16-core Apple M4 Max (12 performance and four efficiency cores) and 128\n> > GB RAM.\n> >\n> > Link: https://lore.kernel.org/git/1445163904-24611-1-git-send-email-Karthik.188@gmail.com/\n> > Link: https://lore.kernel.org/git/20180723204112.233274-1-jonathantanmy@google.com/\n> > Link: https://lore.kernel.org/git/24424e55-7fa8-d05b-bc39-e14b4d5abcb6@gmail.com/\n> > Signed-off-by: Tamir Duberstein <tamird@gmail.com>\n> > ---\n> >  builtin/tag.c                  |  1 -\n> >  commit-reach.c                 | 45 +++++++++++++++++++++++++++++++-----------\n> >  commit-reach.h                 | 15 ++++++++++----\n> >  ref-filter.c                   |  6 ++++--\n> >  ref-filter.h                   |  7 +++----\n> >  t/helper/test-reach.c          | 10 ++--------\n> >  t/perf/p1500-graph-walks.sh    | 24 +++++++++++++++++++++-\n> >  t/t6301-for-each-ref-errors.sh | 18 +++++++++++++++++\n> >  t/t6302-for-each-ref-filter.sh | 21 ++++++++++++++++++++\n> >  t/t6600-test-reach.sh          |  6 ++----\n> >  10 files changed, 117 insertions(+), 36 deletions(-)\n> >\n> > diff --git a/builtin/tag.c b/builtin/tag.c\n> > index d51c2e3349..9f34d948d4 100644\n> > --- a/builtin/tag.c\n> > +++ b/builtin/tag.c\n> > @@ -71,7 +71,6 @@ static int list_tags(struct ref_filter *filter, struct ref_sorting *sorting,\n> >\n> >       if (verify_ref_format(format))\n> >               die(_(\"unable to parse format string\"));\n> > -     filter->with_commit_tag_algo = 1;\n>\n> We were selectively using the algo for `git tag`, like mentioned I guess\n> we'll entirely remove `with_commit_tag_algo` below somewhere\n>\n> >       filter_and_format_refs(filter, FILTER_REFS_TAGS, sorting, format);\n> >\n> >       free(to_free);\n> > diff --git a/commit-reach.c b/commit-reach.c\n> > index 9b3ea46d6f..6e599a3670 100644\n> > --- a/commit-reach.c\n> > +++ b/commit-reach.c\n> > @@ -6,7 +6,6 @@\n> >  #include \"decorate.h\"\n> >  #include \"hex.h\"\n> >  #include \"prio-queue.h\"\n> > -#include \"ref-filter.h\"\n> >  #include \"revision.h\"\n> >  #include \"tag.h\"\n> >  #include \"commit-reach.h\"\n> > @@ -708,7 +707,8 @@ static int in_commit_list(const struct commit_list *want, struct commit *c)\n> >\n> >  /*\n> >   * Test whether the candidate is contained in the list.\n> > - * Do not recurse to find out, though, but return -1 if inconclusive.\n> > + * Do not recurse to find out, though, but return CONTAINS_UNKNOWN if\n> > + * inconclusive.\n>\n> Okay so the code does return CONTAINS_UNKNOWN which is an enum beginning\n> at 0, so this makes sense.\n>\n> >   */\n> >  static enum contains_result contains_test(struct commit *candidate,\n> >                                         const struct commit_list *want,\n> > @@ -743,9 +743,9 @@ static void push_to_contains_stack(struct commit *candidate, struct contains_sta\n> >       contains_stack->contains_stack[contains_stack->nr++].parents = candidate->parents;\n> >  }\n> >\n> > -static enum contains_result contains_tag_algo(struct commit *candidate,\n> > -                                           const struct commit_list *want,\n> > -                                           struct contains_cache *cache)\n> > +static enum contains_result contains_algo(struct commit *candidate,\n> > +                                       struct commit_list *want,\n> > +                                       struct contains_cache *cache)\n> >  {\n> >       struct contains_stack contains_stack = { 0, 0, NULL };\n> >       enum contains_result result;\n> > @@ -765,6 +765,7 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n> >       if (result != CONTAINS_UNKNOWN)\n> >               return result;\n> >\n> > +     *contains_cache_at(cache, candidate) = CONTAINS_IN_PROGRESS;\n> >       push_to_contains_stack(candidate, &contains_stack);\n> >       while (contains_stack.nr) {\n> >               struct contains_stack_entry *entry = &contains_stack.contains_stack[contains_stack.nr - 1];\n> > @@ -776,8 +777,8 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n> >                       contains_stack.nr--;\n> >               }\n> >               /*\n> > -              * If we just popped the stack, parents->item has been marked,\n> > -              * therefore contains_test will return a meaningful yes/no.\n> > +              * A parent may have just been popped and marked, or may still\n> > +              * be active when replacement refs create a cycle.\n> >                */\n> >               else switch (contains_test(parents->item, want, cache, cutoff)) {\n> >               case CONTAINS_YES:\n> > @@ -787,21 +788,41 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n> >               case CONTAINS_NO:\n> >                       entry->parents = parents->next;\n> >                       break;\n> > +             case CONTAINS_IN_PROGRESS:\n> > +                     /*\n> > +                      * Partial negative answers are not safe across a cycle.\n> > +                      * Discard them and use the cycle-safe reachability walk.\n> > +                      */\n> > +                     goto cycle;\n> >\n>\n> If I understand this correctly, we now use CONTAINS_IN_PROGRESS to\n> showcase a commit for which we still don't have a result. Since any\n> commit with UNKNOWN will start a recursive search through its parents.\n>\n> So with this if we encounter a CONTAINS_IN_PROGRESS while recursion,\n> this would indicate that we hit a cyclic graph and so go to the fallback\n> of using repo_is_descendant_of(). So this avoids an infinite recursion\n> in such instances. Makes sense.\n>\n> >               case CONTAINS_UNKNOWN:\n> > +                     *contains_cache_at(cache, parents->item) =\n> > +                             CONTAINS_IN_PROGRESS;\n> >                       push_to_contains_stack(parents->item, &contains_stack);\n> >                       break;\n> >               }\n> >       }\n> >       free(contains_stack.contains_stack);\n> >       return contains_test(candidate, want, cache, cutoff);\n> > +\n> > +cycle:\n> > +     free(contains_stack.contains_stack);\n> > +     clear_contains_cache(cache);\n> > +     init_contains_cache(cache);\n> > +\n> > +     result = repo_is_descendant_of(the_repository, candidate, want);\n> > +     if (result < 0)\n> > +             exit(128);\n> > +     *contains_cache_at(cache, candidate) =\n> > +             result ? CONTAINS_YES : CONTAINS_NO;\n> > +     return result ? CONTAINS_YES : CONTAINS_NO;\n> >  }\n> >\n> > -int commit_contains(struct ref_filter *filter, struct commit *commit,\n> > -                 struct commit_list *list, struct contains_cache *cache)\n> > +int commit_contains(struct commit *commit, struct commit_list *list,\n> > +                 struct contains_cache *cache)\n> >  {\n> > -     if (filter->with_commit_tag_algo)\n> > -             return contains_tag_algo(commit, list, cache) == CONTAINS_YES;\n> > -     return repo_is_descendant_of(the_repository, commit, list);\n> > +     if (!list)\n> > +             return 1;\n> > +     return contains_algo(commit, list, cache) == CONTAINS_YES;\n> >  }\n> >\n> >  int can_all_from_reach_with_flag(struct object_array *from,\n> > diff --git a/commit-reach.h b/commit-reach.h\n> > index 3f3a563d8a..144dc56275 100644\n> > --- a/commit-reach.h\n> > +++ b/commit-reach.h\n> > @@ -5,7 +5,6 @@\n> >  #include \"commit-slab.h\"\n> >\n> >  struct commit_list;\n> > -struct ref_filter;\n> >  struct object_id;\n> >  struct object_array;\n> >\n> > @@ -73,13 +72,21 @@ int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid);\n> >  enum contains_result {\n> >       CONTAINS_UNKNOWN = 0,\n> >       CONTAINS_NO,\n> > -     CONTAINS_YES\n> > +     CONTAINS_YES,\n> > +     CONTAINS_IN_PROGRESS\n> >  };\n> >\n> >  define_commit_slab(contains_cache, enum contains_result);\n> >\n> > -int commit_contains(struct ref_filter *filter, struct commit *commit,\n> > -                 struct commit_list *list, struct contains_cache *cache);\n> > +/*\n> > + * Return whether \"commit\" is a descendant of any commit in \"list\". An empty\n> > + * list matches.\n> > + *\n> > + * \"cache\" records answers for one fixed \"list\". Clear it before changing the\n> > + * list.\n> > + */\n> > +int commit_contains(struct commit *commit, struct commit_list *list,\n> > +                 struct contains_cache *cache);\n> >\n> >  /*\n> >   * Determine if every commit in 'from' can reach at least one commit\n> > diff --git a/ref-filter.c b/ref-filter.c\n> > index 1da4c0e60d..7788147959 100644\n> > --- a/ref-filter.c\n> > +++ b/ref-filter.c\n> > @@ -2991,11 +2991,13 @@ static struct ref_array_item *apply_ref_filter(const struct reference *ref,\n> >                       return NULL;\n> >               /* We perform the filtering for the '--contains' option... */\n> >               if (filter->with_commit &&\n> > -                 !commit_contains(filter, commit, filter->with_commit, &filter->internal.contains_cache))\n> > +                 !commit_contains(commit, filter->with_commit,\n> > +                                  &filter->internal.contains_cache))\n> >                       return NULL;\n> >               /* ...or for the `--no-contains' option */\n> >               if (filter->no_commit &&\n> > -                 commit_contains(filter, commit, filter->no_commit, &filter->internal.no_contains_cache))\n> > +                 commit_contains(commit, filter->no_commit,\n> > +                                 &filter->internal.no_contains_cache))\n> >                       return NULL;\n> >       }\n> >\n> > diff --git a/ref-filter.h b/ref-filter.h\n> > index 120221b47f..9e14afca9c 100644\n> > --- a/ref-filter.h\n> > +++ b/ref-filter.h\n> > @@ -73,10 +73,9 @@ struct ref_filter {\n> >       struct commit_list *reachable_from;\n> >       struct commit_list *unreachable_from;\n> >\n> > -     unsigned int with_commit_tag_algo : 1,\n> > -             match_as_path : 1,\n> > -             ignore_case : 1,\n> > -             detached : 1;\n> > +     unsigned int match_as_path : 1,\n> > +                  ignore_case : 1,\n> > +                  detached : 1;\n> >       unsigned int kind,\n> >               lines;\n> >       int abbrev,\n>\n> Nit: With the changes above. I do wish it was split into two commits.\n> 1. Fix cyclic recursions in the algo.\n> 2. Use the algo for all filter types.\n\nMakes sense. I split v2 accordingly. The first patch now fixes the\nexisting git tag --contains traversal and tests that path directly.\nThe second patch then uses the traversal for the other ref-filter\ncallers.\n\n>\n> > diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c\n> > index 5d86a96c17..82235f713e 100644\n> > --- a/t/helper/test-reach.c\n> > +++ b/t/helper/test-reach.c\n> > @@ -6,7 +6,6 @@\n> >  #include \"gettext.h\"\n> >  #include \"hex.h\"\n> >  #include \"object-name.h\"\n> > -#include \"ref-filter.h\"\n> >  #include \"setup.h\"\n> >  #include \"string-list.h\"\n> >  #include \"tag.h\"\n> > @@ -138,16 +137,11 @@ int cmd__reach(int ac, const char **av)\n> >\n> >               printf(\"%s(X,_,_,0,0):%d\\n\", av[1], can_all_from_reach_with_flag(&X_obj, 2, 4, 0, 0));\n> >       } else if (!strcmp(av[1], \"commit_contains\")) {\n> > -             struct ref_filter filter = REF_FILTER_INIT;\n> >               struct contains_cache cache;\n> >               init_contains_cache(&cache);\n> >\n> > -             if (ac > 2 && !strcmp(av[2], \"--tag\"))\n> > -                     filter.with_commit_tag_algo = 1;\n> > -             else\n> > -                     filter.with_commit_tag_algo = 0;\n> > -\n> > -             printf(\"%s(_,A,X,_):%d\\n\", av[1], commit_contains(&filter, A, X, &cache));\n> > +             printf(\"%s(_,A,X,_):%d\\n\", av[1],\n> > +                    commit_contains(A, X, &cache));\n> >               clear_contains_cache(&cache);\n> >       } else if (!strcmp(av[1], \"get_reachable_subset\")) {\n> >               const int reachable_flag = 1;\n>\n> Makes sense.\n>\n> > diff --git a/t/perf/p1500-graph-walks.sh b/t/perf/p1500-graph-walks.sh\n> > index 5b23ce5db9..ac68fdbacd 100755\n> > --- a/t/perf/p1500-graph-walks.sh\n> > +++ b/t/perf/p1500-graph-walks.sh\n> > @@ -5,6 +5,8 @@ test_description='Commit walk performance tests'\n> >\n> >  test_perf_large_repo\n> >\n> > +contains_ref_limit=8192\n> > +\n> >  test_expect_success 'setup' '\n> >       git for-each-ref --format=\"%(refname)\" \"refs/heads/*\" \"refs/tags/*\" >allrefs &&\n> >       sort -r allrefs | head -n 50 >refs &&\n> > @@ -32,10 +34,25 @@ test_expect_success 'setup' '\n> >               echo \"X:$line\" >>test-tool-tags || return 1\n> >       done &&\n> >\n> > +     git rev-list --first-parent --max-count=$contains_ref_limit HEAD >contains-commits &&\n> > +     contains_ref_count=$(wc -l <contains-commits) &&\n> > +     test \"$contains_ref_count\" -gt 0 &&\n> > +     contains_base=$(tail -n 1 contains-commits) &&\n> > +     export contains_base &&\n> > +     awk \"{\n> > +             printf \\\"update refs/contains-perf/%04d %s\\\\n\\\", NR, \\$1\n> > +     }\" contains-commits |\n> > +             git update-ref --stdin &&\n> > +     git pack-refs --include \"refs/contains-perf/*\" &&\n> > +\n> >       commit=$(git commit-tree $(git rev-parse HEAD^{tree})) &&\n> >       git update-ref refs/heads/disjoint-base $commit &&\n> >\n> > -     git commit-graph write --reachable\n> > +     git commit-graph write --reachable &&\n> > +\n> > +     git for-each-ref --contains=\"$contains_base\" \\\n> > +             refs/contains-perf/ >actual &&\n> > +     test_line_count = $contains_ref_count actual\n>\n> Shouldn't this be a separate test and not a part of the setup?\n>\n> >  '\n> >\n> >  test_perf 'ahead-behind counts: git for-each-ref' '\n> > @@ -62,6 +79,11 @@ test_perf 'contains: git tag --merged' '\n> >       xargs git tag --merged=HEAD <tags\n> >  '\n> >\n> > +test_perf 'contains: git for-each-ref --contains' '\n> > +     git for-each-ref --contains=\"$contains_base\" \\\n> > +             refs/contains-perf/ >/dev/null\n> > +'\n> > +\n>\n> Ah! we also have this, so perhaps moving the `test_line_count` here and\n> dropping it above would be better.\n\nMakes sense! Done in v2.\n\n>\n> >  test_perf 'is-base check: test-tool reach (refs)' '\n> >       test-tool reach get_branch_base_for_tip <test-tool-refs\n> >  '\n> > diff --git a/t/t6301-for-each-ref-errors.sh b/t/t6301-for-each-ref-errors.sh\n> > index e06feb06e9..169cc70c23 100755\n> > --- a/t/t6301-for-each-ref-errors.sh\n> > +++ b/t/t6301-for-each-ref-errors.sh\n> > @@ -52,6 +52,24 @@ test_expect_success 'Missing objects are reported correctly' '\n> >       test_must_be_empty brief-err\n> >  '\n> >\n> > +test_expect_success 'missing ancestors are reported by contains filters' '\n> > +     test_when_finished \"git update-ref -d refs/heads/missing-parent\" &&\n> > +     {\n> > +             echo \"tree $(git rev-parse HEAD^{tree})\" &&\n> > +             echo \"parent $MISSING\" &&\n> > +             git cat-file commit HEAD |\n> > +                     sed -n -e \"/^author /p\" -e \"/^committer /p\" &&\n> > +             echo &&\n> > +             echo \"missing parent\"\n> > +     } > commit &&\n> > +     broken=$(git hash-object -t commit -w commit) &&\n> > +     git update-ref refs/heads/missing-parent \"$broken\" &&\n> > +     test_must_fail git for-each-ref --contains=HEAD \\\n> > +             refs/heads/missing-parent >out 2>err &&\n> > +     test_must_be_empty out &&\n> > +     test_grep \"unable to parse commit $MISSING\" err\n> > +'\n> > +\n> >  test_expect_success 'ahead-behind requires an argument' '\n> >       test_must_fail git for-each-ref \\\n> >               --format=\"%(ahead-behind)\" 2>err &&\n> > diff --git a/t/t6302-for-each-ref-filter.sh b/t/t6302-for-each-ref-filter.sh\n> > index 7f060d97bf..423505d1fb 100755\n> > --- a/t/t6302-for-each-ref-filter.sh\n> > +++ b/t/t6302-for-each-ref-filter.sh\n> > @@ -177,6 +177,27 @@ test_expect_success 'filtering with --contains and --no-contains' '\n> >       test_cmp expect actual\n> >  '\n> >\n> > +test_expect_success 'contains handles cyclic replacement histories' '\n> > +     one=$(git rev-parse one) &&\n> > +     three=$(git rev-parse three) &&\n> > +     test_when_finished \"\n> > +             git replace -d $one\n> > +             git replace -d $three\n> > +             git tag -d cycle-a cycle-b\n> > +     \" &&\n> > +     git tag cycle-a \"$one\" &&\n> > +     git tag cycle-b \"$three\" &&\n> > +     git replace --graft \"$one\" \"$three\" two &&\n> > +     git replace --graft \"$three\" \"$one\" &&\n> > +     cat >expect <<-\\EOF &&\n> > +     refs/tags/cycle-a\n> > +     refs/tags/cycle-b\n> > +     EOF\n> > +     git for-each-ref --format=\"%(refname)\" --contains=two \\\n> > +             \"refs/tags/cycle-*\" >actual &&\n> > +     test_cmp expect actual\n> > +'\n> > +\n> >  test_expect_success '%(color) must fail' '\n> >       test_must_fail git for-each-ref --format=\"%(color)%(refname)\"\n> >  '\n> > diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\n> > index b5b314e570..1ecc2571c2 100755\n> > --- a/t/t6600-test-reach.sh\n> > +++ b/t/t6600-test-reach.sh\n> > @@ -286,8 +286,7 @@ test_expect_success 'commit_contains:hit' '\n> >       X:commit-9-3\n> >       EOF\n> >       echo \"commit_contains(_,A,X,_):1\" >expect &&\n> > -     test_all_modes commit_contains &&\n> > -     test_all_modes commit_contains --tag\n> > +     test_all_modes commit_contains\n> >  '\n> >\n> >  test_expect_success 'commit_contains:miss' '\n> > @@ -303,8 +302,7 @@ test_expect_success 'commit_contains:miss' '\n> >       X:commit-9-3\n> >       EOF\n> >       echo \"commit_contains(_,A,X,_):0\" >expect &&\n> > -     test_all_modes commit_contains &&\n> > -     test_all_modes commit_contains --tag\n> > +     test_all_modes commit_contains\n> >  '\n> >\n> >  test_expect_success 'rev-list: basic topo-order' '\n> >\n> > ---\n> > base-commit: 9ac3f193c05c2237e2b14ebaa1149e9fc8a1abe0\n> > change-id: 20260607-ref-filter-memoized-contains-7cb6b3bccad1\n> >\n> > Best regards,\n> > --\n> > Tamir Duberstein <tamird@gmail.com>\n>\n> Overall the patch looks great. The perf improvements are also very\n> welcome. Some small nits from me.\n\nThanks a lot for the review!\n"},{"id":"544972","messageId":"20260608223430.GA340696@coredump.intra.peff.net","threadId":"65768","inReplyTo":"20260607-ref-filter-memoized-contains-v1-1-a1972dde9c76@gmail.com","subject":"Re: [PATCH] ref-filter: reuse --contains traversal results","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-06-08T22:34:30Z","receivedAt":"2026-06-08T22:34:38Z","isPatch":true,"body":"On Sun, Jun 07, 2026 at 08:33:29PM -0700, Tamir Duberstein wrote:\n\n> git branch and git for-each-ref call repo_is_descendant_of() for each\n> candidate selected by --contains or --no-contains. Each call starts a\n> new graph walk, so refs with shared history repeatedly traverse the same\n> commits.\n> \n> ffc4b8012d (tag: speed up --contains calculation, 2011-06-11) introduced\n> the tag traversal that caches positive and negative answers across\n> candidates. ee2bd06b0f (ref-filter: implement '--contains' option,\n> 2015-07-07) preserved the branch and tag implementations when ref-filter\n> learned --contains. 008ed7df930 (tag.c: use the correct algorithm for\n> the '--contains' option, 2015-10-18) noted that they should be unified.\n> \n> Use the memoized traversal for every ref-filter contains check and\n> remove the implementation selector. The cache records answers for one\n> fixed target list, so document that callers must clear it before\n> changing the list.\n\nThe subject line obfuscated the intent here (at least for me). I think a\nmore clear subject would just be: \"ref-filter: always use\ncontains_tag_algo\" or something.\n\nBut more importantly, I think the analysis above is missing a key point\nabout why we didn't make the tag algo the default in the first place: it\nis depth first, and thus slower when the merge base can be found quickly\nby the breadth-first traversal. For tags, you tend to have to look at\nall of history anyway (because you have at least one old tag that\nrequires walking back that far), but that is often not true for\nbranches.\n\nWe are able to get the best of both worlds if we can cut off the\ndepth-first traversal early using generation numbers.\n\nSo I think a better rule here is to tweak the selection in\ncommit_contains() to select the depth-first algorithm when we have\ngeneration numbers enabled. There's a patch in an old thread, which was\nrevived a week or two ago by Kristofer (cc'd):\n\n  https://lore.kernel.org/git/20260527070510.3510836-1-krka@spotify.com/\n\n> The memoized depth-first walk assumes acyclic ancestry, but replacement\n> refs can create cycles. Track commits while they are on the walk. If a\n> cycle is found, discard partial cache entries and use\n> repo_is_descendant_of() for that candidate.\n\nI can believe that the depth-first code doesn't handle cycles well. But\nif that's the case, then it's already a problem for \"git tag\n--contains\". And we should fix it as a separate patch from enabling that\nalgorithm in more cases.\n\nI'm not quite sure how ancestry should be defined in a cycle. How does\nthe algorithm behave now when it sees a cycle? If it loops infinitely,\nwe definitely would want to fix that. If not, then to some degree I\ndon't care too much what answer is provided, since the input is somewhat\nnonsense in the first place. And if it is expensive to track, it might\nnot be worth inflicting that penalty on the sane cases. But it looks\nlike your solution is just setting an extra flag value in the slab,\nwhich should be pretty cheap.\n\n> The branch and for-each-ref path passed repo_is_descendant_of() through\n> a Boolean interface. In configurations where it returned -1 for missing\n> ancestry, ref-filter treated the error as \"contains\". The memoized path\n> instead fails when ancestry cannot be parsed, as git tag already did.\n> During review of the 2018 reachability series, making parse failures\n> fatal was explicitly deferred because that series was intended to\n> preserve behavior. Unifying the implementations now makes all callers\n> fail consistently instead of preserving that accidental Boolean\n> interpretation.\n\nI think that's a good outcome.\n\n> The added p1500 case uses up to 8,192 packed refs along one first-parent\n> history. It improves from 0.68 to 0.03 seconds.\n> \n> On a checkout with 62,174 remote-tracking refs, I ran:\n> \n>     hyperfine --warmup 0 --runs 3 \\\n>         --command-name parent \\\n>         '\"$parent\" branch -r --contains c78ae85f3ce7e >/dev/null' \\\n>         --command-name this-commit \\\n>         '\"$this\" branch -r --contains c78ae85f3ce7e >/dev/null'\n> \n> The results were:\n> \n>              parent       this commit\n>   elapsed    104.365 s     467.7 ms\n>   user        93.702 s     220.2 ms\n>   system       0.723 s     182.7 ms\n\nI didn't time it, but the probable regression case is something like\nthis: a very deep history with a small number of branches diverging only\na few commits away. Without a commit-graph file (or one without\ngeneration numbers), that probably makes \"git branch --contains\" slower.\n\n-Peff\n"},{"id":"544980","messageId":"CAJ-ks9ng3Obv8jydYiBD4kxmTSZCJX8xNb0YihNeSW8_8WL5Ew@mail.gmail.com","threadId":"65768","inReplyTo":"20260608223430.GA340696@coredump.intra.peff.net","subject":"Re: [PATCH] ref-filter: reuse --contains traversal results","fromName":"Tamir Duberstein","fromEmail":"tamird@gmail.com","sentAt":"2026-06-08T23:35:57Z","receivedAt":"2026-06-08T23:36:36Z","isPatch":true,"body":"On Mon, Jun 8, 2026 at 3:34 PM Jeff King <peff@peff.net> wrote:\n>\n> On Sun, Jun 07, 2026 at 08:33:29PM -0700, Tamir Duberstein wrote:\n>\n> > git branch and git for-each-ref call repo_is_descendant_of() for each\n> > candidate selected by --contains or --no-contains. Each call starts a\n> > new graph walk, so refs with shared history repeatedly traverse the same\n> > commits.\n> >\n> > ffc4b8012d (tag: speed up --contains calculation, 2011-06-11) introduced\n> > the tag traversal that caches positive and negative answers across\n> > candidates. ee2bd06b0f (ref-filter: implement '--contains' option,\n> > 2015-07-07) preserved the branch and tag implementations when ref-filter\n> > learned --contains. 008ed7df930 (tag.c: use the correct algorithm for\n> > the '--contains' option, 2015-10-18) noted that they should be unified.\n> >\n> > Use the memoized traversal for every ref-filter contains check and\n> > remove the implementation selector. The cache records answers for one\n> > fixed target list, so document that callers must clear it before\n> > changing the list.\n>\n> The subject line obfuscated the intent here (at least for me). I think a\n> more clear subject would just be: \"ref-filter: always use\n> contains_tag_algo\" or something.\n\nAck, changed to \"ref-filter: memoize --contains with generations\" in v2 draft.\n\n>\n> But more importantly, I think the analysis above is missing a key point\n> about why we didn't make the tag algo the default in the first place: it\n> is depth first, and thus slower when the merge base can be found quickly\n> by the breadth-first traversal. For tags, you tend to have to look at\n> all of history anyway (because you have at least one old tag that\n> requires walking back that far), but that is often not true for\n> branches.\n>\n> We are able to get the best of both worlds if we can cut off the\n> depth-first traversal early using generation numbers.\n>\n> So I think a better rule here is to tweak the selection in\n> commit_contains() to select the depth-first algorithm when we have\n> generation numbers enabled. There's a patch in an old thread, which was\n> revived a week or two ago by Kristofer (cc'd):\n>\n>   https://lore.kernel.org/git/20260527070510.3510836-1-krka@spotify.com/\n\nVery good catch, thank you. I reproduced the regression with a\n100,000-commit history and generation numbers disabled. The parent\ntook 13.0 ms, the unconditional depth-first version took 238.4 ms, and\nthe generation-aware version took 9.1 ms.\n\nI didn't find a patch in that thread, so I will reroll using the\nmemoized walk for tags or when generation numbers are enabled, while\nretaining the breadth-first walk otherwise. If someone else would\nprefer to send that patch, that is fine by me as well.\n\n>\n> > The memoized depth-first walk assumes acyclic ancestry, but replacement\n> > refs can create cycles. Track commits while they are on the walk. If a\n> > cycle is found, discard partial cache entries and use\n> > repo_is_descendant_of() for that candidate.\n>\n> I can believe that the depth-first code doesn't handle cycles well. But\n> if that's the case, then it's already a problem for \"git tag\n> --contains\". And we should fix it as a separate patch from enabling that\n> algorithm in more cases.\n\nAgreed, and Karthik flagged the same. The cycle handling is now a\nseparate first patch.\n\n>\n> I'm not quite sure how ancestry should be defined in a cycle. How does\n> the algorithm behave now when it sees a cycle? If it loops infinitely,\n> we definitely would want to fix that. If not, then to some degree I\n> don't care too much what answer is provided, since the input is somewhat\n> nonsense in the first place. And if it is expensive to track, it might\n> not be worth inflicting that penalty on the sane cases. But it looks\n> like your solution is just setting an extra flag value in the slab,\n> which should be pretty cheap.\n>\n> > The branch and for-each-ref path passed repo_is_descendant_of() through\n> > a Boolean interface. In configurations where it returned -1 for missing\n> > ancestry, ref-filter treated the error as \"contains\". The memoized path\n> > instead fails when ancestry cannot be parsed, as git tag already did.\n> > During review of the 2018 reachability series, making parse failures\n> > fatal was explicitly deferred because that series was intended to\n> > preserve behavior. Unifying the implementations now makes all callers\n> > fail consistently instead of preserving that accidental Boolean\n> > interpretation.\n>\n> I think that's a good outcome.\n>\n> > The added p1500 case uses up to 8,192 packed refs along one first-parent\n> > history. It improves from 0.68 to 0.03 seconds.\n> >\n> > On a checkout with 62,174 remote-tracking refs, I ran:\n> >\n> >     hyperfine --warmup 0 --runs 3 \\\n> >         --command-name parent \\\n> >         '\"$parent\" branch -r --contains c78ae85f3ce7e >/dev/null' \\\n> >         --command-name this-commit \\\n> >         '\"$this\" branch -r --contains c78ae85f3ce7e >/dev/null'\n> >\n> > The results were:\n> >\n> >              parent       this commit\n> >   elapsed    104.365 s     467.7 ms\n> >   user        93.702 s     220.2 ms\n> >   system       0.723 s     182.7 ms\n>\n> I didn't time it, but the probable regression case is something like\n> this: a very deep history with a small number of branches diverging only\n> a few commits away. Without a commit-graph file (or one without\n> generation numbers), that probably makes \"git branch --contains\" slower.\n>\n> -Peff\n"},{"id":"544984","messageId":"20260608235214.GC358144@coredump.intra.peff.net","threadId":"65768","inReplyTo":"CAJ-ks9ng3Obv8jydYiBD4kxmTSZCJX8xNb0YihNeSW8_8WL5Ew@mail.gmail.com","subject":"Re: [PATCH] ref-filter: reuse --contains traversal results","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-06-08T23:52:14Z","receivedAt":"2026-06-08T23:52:16Z","isPatch":true,"body":"On Mon, Jun 08, 2026 at 07:35:57PM -0400, Tamir Duberstein wrote:\n\n> > So I think a better rule here is to tweak the selection in\n> > commit_contains() to select the depth-first algorithm when we have\n> > generation numbers enabled. There's a patch in an old thread, which was\n> > revived a week or two ago by Kristofer (cc'd):\n> >\n> >   https://lore.kernel.org/git/20260527070510.3510836-1-krka@spotify.com/\n> \n> Very good catch, thank you. I reproduced the regression with a\n> 100,000-commit history and generation numbers disabled. The parent\n> took 13.0 ms, the unconditional depth-first version took 238.4 ms, and\n> the generation-aware version took 9.1 ms.\n> \n> I didn't find a patch in that thread, so I will reroll using the\n> memoized walk for tags or when generation numbers are enabled, while\n> retaining the breadth-first walk otherwise. If someone else would\n> prefer to send that patch, that is fine by me as well.\n\nIt's just this:\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 9b3ea46d6f..cdea0030b8 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -799,7 +799,8 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n int commit_contains(struct ref_filter *filter, struct commit *commit,\n \t\t    struct commit_list *list, struct contains_cache *cache)\n {\n-\tif (filter->with_commit_tag_algo)\n+\tif (filter->with_commit_tag_algo ||\n+\t    generation_numbers_enabled(the_repository))\n \t\treturn contains_tag_algo(commit, list, cache) == CONTAINS_YES;\n \treturn repo_is_descendant_of(the_repository, commit, list);\n }\n\nfrom:\n\n  https://lore.kernel.org/git/20230324191009.GA536967@coredump.intra.peff.net/\n\nBut I won't be surprised if you recreated the identical patch yourself. ;)\n\n-Peff\n"},{"id":"544987","messageId":"CAJ-ks9m1BKPswrc+f3JDf5x-APfgZ2ycggxi-tJgr12GONb0jg@mail.gmail.com","threadId":"65768","inReplyTo":"20260608235214.GC358144@coredump.intra.peff.net","subject":"Re: [PATCH] ref-filter: reuse --contains traversal results","fromName":"Tamir Duberstein","fromEmail":"tamird@gmail.com","sentAt":"2026-06-08T23:56:03Z","receivedAt":"2026-06-08T23:56:42Z","isPatch":true,"body":"On Mon, Jun 8, 2026 at 4:52 PM Jeff King <peff@peff.net> wrote:\n>\n> On Mon, Jun 08, 2026 at 07:35:57PM -0400, Tamir Duberstein wrote:\n>\n> > > So I think a better rule here is to tweak the selection in\n> > > commit_contains() to select the depth-first algorithm when we have\n> > > generation numbers enabled. There's a patch in an old thread, which was\n> > > revived a week or two ago by Kristofer (cc'd):\n> > >\n> > >   https://lore.kernel.org/git/20260527070510.3510836-1-krka@spotify.com/\n> >\n> > Very good catch, thank you. I reproduced the regression with a\n> > 100,000-commit history and generation numbers disabled. The parent\n> > took 13.0 ms, the unconditional depth-first version took 238.4 ms, and\n> > the generation-aware version took 9.1 ms.\n> >\n> > I didn't find a patch in that thread, so I will reroll using the\n> > memoized walk for tags or when generation numbers are enabled, while\n> > retaining the breadth-first walk otherwise. If someone else would\n> > prefer to send that patch, that is fine by me as well.\n>\n> It's just this:\n>\n> diff --git a/commit-reach.c b/commit-reach.c\n> index 9b3ea46d6f..cdea0030b8 100644\n> --- a/commit-reach.c\n> +++ b/commit-reach.c\n> @@ -799,7 +799,8 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n>  int commit_contains(struct ref_filter *filter, struct commit *commit,\n>                     struct commit_list *list, struct contains_cache *cache)\n>  {\n> -       if (filter->with_commit_tag_algo)\n> +       if (filter->with_commit_tag_algo ||\n> +           generation_numbers_enabled(the_repository))\n>                 return contains_tag_algo(commit, list, cache) == CONTAINS_YES;\n>         return repo_is_descendant_of(the_repository, commit, list);\n>  }\n>\n> from:\n>\n>   https://lore.kernel.org/git/20230324191009.GA536967@coredump.intra.peff.net/\n>\n> But I won't be surprised if you recreated the identical patch yourself. ;)\n\nYep, that's what happened!\n\n>\n> -Peff\n\nThanks again for all the reviews, v2 of all the patches coming shortly.\n"}]}