{"thread":{"id":"65609","subject":"[PATCH] commit-reach: early exit paint_down_to_common for single merge-base","startedAt":"2026-05-08T15:07:20Z","lastAt":"2026-05-12T05:16:17Z","messageCount":11,"participants":["Kristofer Karlsson via GitGitGadget","Junio C Hamano","Patrick Steinhardt","Kristofer Karlsson"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"542927","messageId":"pull.2109.git.1778252837132.gitgitgadget@gmail.com","threadId":"65609","inReplyTo":null,"subject":"[PATCH] commit-reach: early exit paint_down_to_common for single merge-base","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-05-08T15:07:17Z","receivedAt":"2026-05-08T15:07:20Z","isPatch":true,"body":"From: Kristofer Karlsson \n\nWhen find_all is false and generation numbers are available, the\npriority queue pops in non-increasing generation order. The first\ndoubly-painted commit is a valid best merge-base; no later commit\ncan dominate it. Skip the expensive STALE drain in this case.\n\nThe early exit is guarded by three conditions: find_all must be\nfalse, the commit-graph must provide generation numbers, and the\nmerge-base commit itself must have a finite generation (not\nGENERATION_NUMBER_INFINITY from being outside the commit-graph).\n\nAdd find_all parameter to repo_get_merge_bases_many_dirty() and\nthread it through to paint_down_to_common(). git merge-base\n(without --all) passes show_all=0, triggering the early exit.\n\nOn a 2.2M-commit merge-heavy monorepo with commit-graph:\n\n HEAD vs ~500: 5,229ms -> 24ms\n HEAD vs ~1000: 4,214ms -> 39ms\n HEAD vs ~5000: 3,799ms -> 46ms\n HEAD vs ~10000: 3,827ms -> 61ms\n\nSigned-off-by: Kristofer Karlsson \n---\n [RFC] commit-reach: skip STALE drain when only one merge-base needed\n \n Context for what this is all about.\n \n I am working with a very large git monorepo and have been investigating\n performance issue. After some digging I ended up looking more deeply\n into git merge-base. I saw it had an --all parameter but the default is\n to only return a single merge-base. Looking through the code and adding\n debug timing, I realized that although the total time to compute the\n merge-base was high, a very small amount of time was spent finding the\n initial merge-base value that was later returned.\n \n The optimization is actually quite dramatic in a large repo - runtime\n went down from 5000ms to 50ms, so it's roughly a 100x optimization. This\n comes from an exploding frontier of STALE commits to drain.\n \n Thus, my idea is simply to return early from the function once we know\n what will be returned. This only works if we find a candidate that we\n know will not be pruned later - but fortunately if we have a commit\n graph with generations we will visit commits in order such that it will\n actually not be pruned.\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2109%2Fspkrka%2Fmerge-base-early-exit-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2109/spkrka/merge-base-early-exit-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/2109\n\n builtin/merge-base.c | 3 +-\n commit-reach.c | 26 ++++++---\n commit-reach.h | 5 +-\n t/t6010-merge-base.sh | 119 ++++++++++++++++++++++++++++++++++++++++++\n t/t6600-test-reach.sh | 40 ++++++++++++++\n 5 files changed, 183 insertions(+), 10 deletions(-)\n\ndiff --git a/builtin/merge-base.c b/builtin/merge-base.c\nindex c7ee97fa6a..6b9d42f596 100644\n--- a/builtin/merge-base.c\n+++ b/builtin/merge-base.c\n@@ -14,7 +14,8 @@ static int show_merge_base(struct commit **rev, size_t rev_nr, int show_all)\n \tstruct commit_list *result = NULL, *r;\n \n \tif (repo_get_merge_bases_many_dirty(the_repository, rev[0],\n-\t\t\t\t\t rev_nr - 1, rev + 1, &result) < 0) {\n+\t\t\t\t\t rev_nr - 1, rev + 1,\n+\t\t\t\t\t show_all, &result) < 0) {\n \t\tcommit_list_free(result);\n \t\treturn -1;\n \t}\ndiff --git a/commit-reach.c b/commit-reach.c\nindex d3a9b3ed6f..c9d2d594de 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -55,14 +55,16 @@ static int paint_down_to_common(struct repository *r,\n \t\t\t\tstruct commit **twos,\n \t\t\t\ttimestamp_t min_generation,\n \t\t\t\tint ignore_missing_commits,\n+\t\t\t\tint find_all,\n \t\t\t\tstruct commit_list **result)\n {\n \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n \tint i;\n+\tint has_gens = min_generation || corrected_commit_dates_enabled(r);\n \ttimestamp_t last_gen = GENERATION_NUMBER_INFINITY;\n \tstruct commit_list **tail = result;\n \n-\tif (!min_generation && !corrected_commit_dates_enabled(r))\n+\tif (!has_gens)\n \t\tqueue.compare = compare_commits_by_commit_date;\n \n \tone->object.flags |= PARENT1;\n@@ -97,6 +99,11 @@ static int paint_down_to_common(struct repository *r,\n \t\t\tif (!(commit->object.flags & RESULT)) {\n \t\t\t\tcommit->object.flags |= RESULT;\n \t\t\t\ttail = commit_list_append(commit, tail);\n+\t\t\t\t/* Generation-ordered queue: no later\n+\t\t\t\t * commit can dominate this one. */\n+\t\t\t\tif (!find_all && has_gens &&\n+\t\t\t\t generation < GENERATION_NUMBER_INFINITY)\n+\t\t\t\t\tbreak;\n \t\t\t}\n \t\t\t/* Mark parents of a found merge stale */\n \t\t\tflags |= STALE;\n@@ -136,6 +143,7 @@ static int paint_down_to_common(struct repository *r,\n static int merge_bases_many(struct repository *r,\n \t\t\t struct commit *one, int n,\n \t\t\t struct commit **twos,\n+\t\t\t int find_all,\n \t\t\t struct commit_list **result)\n {\n \tstruct commit_list *list = NULL, **tail = result;\n@@ -165,7 +173,7 @@ static int merge_bases_many(struct repository *r,\n \t\t\t\t oid_to_hex(&twos[i]->object.oid));\n \t}\n \n-\tif (paint_down_to_common(r, one, n, twos, 0, 0, &list)) {\n+\tif (paint_down_to_common(r, one, n, twos, 0, 0, find_all, &list)) {\n \t\tcommit_list_free(list);\n \t\treturn -1;\n \t}\n@@ -246,7 +254,7 @@ static int remove_redundant_no_gen(struct repository *r,\n \t\t\t\tmin_generation = curr_generation;\n \t\t}\n \t\tif (paint_down_to_common(r, array[i], filled,\n-\t\t\t\t\t work, min_generation, 0, &common)) {\n+\t\t\t\t\t work, min_generation, 0, 1, &common)) {\n \t\t\tclear_commit_marks(array[i], all_flags);\n \t\t\tclear_commit_marks_many(filled, work, all_flags);\n \t\t\tcommit_list_free(common);\n@@ -425,6 +433,7 @@ static int get_merge_bases_many_0(struct repository *r,\n \t\t\t\t size_t n,\n \t\t\t\t struct commit **twos,\n \t\t\t\t int cleanup,\n+\t\t\t\t int find_all,\n \t\t\t\t struct commit_list **result)\n {\n \tstruct commit_list *list, **tail = result;\n@@ -432,7 +441,7 @@ static int get_merge_bases_many_0(struct repository *r,\n \tsize_t cnt, i;\n \tint ret;\n \n-\tif (merge_bases_many(r, one, n, twos, result) < 0)\n+\tif (merge_bases_many(r, one, n, twos, find_all, result) < 0)\n \t\treturn -1;\n \tfor (i = 0; i < n; i++) {\n \t\tif (one == twos[i])\n@@ -475,16 +484,17 @@ int repo_get_merge_bases_many(struct repository *r,\n \t\t\t struct commit **twos,\n \t\t\t struct commit_list **result)\n {\n-\treturn get_merge_bases_many_0(r, one, n, twos, 1, result);\n+\treturn get_merge_bases_many_0(r, one, n, twos, 1, 1, result);\n }\n \n int repo_get_merge_bases_many_dirty(struct repository *r,\n \t\t\t\t struct commit *one,\n \t\t\t\t size_t n,\n \t\t\t\t struct commit **twos,\n+\t\t\t\t int find_all,\n \t\t\t\t struct commit_list **result)\n {\n-\treturn get_merge_bases_many_0(r, one, n, twos, 0, result);\n+\treturn get_merge_bases_many_0(r, one, n, twos, 0, find_all, result);\n }\n \n int repo_get_merge_bases(struct repository *r,\n@@ -492,7 +502,7 @@ int repo_get_merge_bases(struct repository *r,\n \t\t\t struct commit *two,\n \t\t\t struct commit_list **result)\n {\n-\treturn get_merge_bases_many_0(r, one, 1, &two, 1, result);\n+\treturn get_merge_bases_many_0(r, one, 1, &two, 1, 1, result);\n }\n \n /*\n@@ -555,7 +565,7 @@ int repo_in_merge_bases_many(struct repository *r, struct commit *commit,\n \n \tif (paint_down_to_common(r, commit,\n \t\t\t\t nr_reference, reference,\n-\t\t\t\t generation, ignore_missing_commits, &bases))\n+\t\t\t\t generation, ignore_missing_commits, 1, &bases))\n \t\tret = -1;\n \telse if (commit->object.flags & PARENT2)\n \t\tret = 1;\ndiff --git a/commit-reach.h b/commit-reach.h\nindex 6012402dfc..908b9539c5 100644\n--- a/commit-reach.h\n+++ b/commit-reach.h\n@@ -17,10 +17,13 @@ int repo_get_merge_bases_many(struct repository *r,\n \t\t\t struct commit *one, size_t n,\n \t\t\t struct commit **twos,\n \t\t\t struct commit_list **result);\n-/* To be used only when object flags after this call no longer matter */\n+/* To be used only when object flags after this call no longer matter.\n+ * When find_all is false and generation numbers are available, returns\n+ * after finding the first merge-base, skipping the STALE drain. */\n int repo_get_merge_bases_many_dirty(struct repository *r,\n \t\t\t\t struct commit *one, size_t n,\n \t\t\t\t struct commit **twos,\n+\t\t\t\t int find_all,\n \t\t\t\t struct commit_list **result);\n \n int get_octopus_merge_bases(struct commit_list *in, struct commit_list **result);\ndiff --git a/t/t6010-merge-base.sh b/t/t6010-merge-base.sh\nindex 44c726ea39..f6c85d4f53 100755\n--- a/t/t6010-merge-base.sh\n+++ b/t/t6010-merge-base.sh\n@@ -305,4 +305,123 @@ test_expect_success 'merge-base --octopus --all for complex tree' '\n \ttest_cmp expected actual\n '\n \n+# The following tests verify that \"git merge-base\" (without --all)\n+# returns the same result with and without a commit-graph.\n+# This exercises the early-exit optimisation in paint_down_to_common\n+# that skips the STALE drain when generation numbers are available.\n+\n+test_expect_success 'setup for commit-graph tests' '\n+\tgit init graph-repo &&\n+\t(\n+\t\tcd graph-repo &&\n+\n+\t\t# Build a forked DAG:\n+\t\t#\n+\t\t# L1---L2 (left)\n+\t\t# /\n+\t\t# S\n+\t\t# \\\n+\t\t# R1---R2 (right)\n+\t\t#\n+\t\ttest_commit GS &&\n+\t\tgit checkout -b left &&\n+\t\ttest_commit L1 &&\n+\t\ttest_commit L2 &&\n+\t\tgit checkout GS &&\n+\t\tgit checkout -b right &&\n+\t\ttest_commit GR1 &&\n+\t\ttest_commit GR2\n+\t)\n+'\n+\n+test_expect_success 'merge-base without commit-graph' '\n+\t(\n+\t\tcd graph-repo &&\n+\t\trm -f .git/objects/info/commit-graph &&\n+\t\tgit merge-base left right >actual &&\n+\t\tgit rev-parse GS >expected &&\n+\t\ttest_cmp expected actual\n+\t)\n+'\n+\n+test_expect_success 'merge-base with commit-graph' '\n+\t(\n+\t\tcd graph-repo &&\n+\t\tgit commit-graph write --reachable &&\n+\t\tgit merge-base left right >actual &&\n+\t\tgit rev-parse GS >expected &&\n+\t\ttest_cmp expected actual\n+\t)\n+'\n+\n+test_expect_success 'merge-base --all with commit-graph' '\n+\t(\n+\t\tcd graph-repo &&\n+\t\tgit merge-base --all left right >actual &&\n+\t\tgit rev-parse GS >expected &&\n+\t\ttest_cmp expected actual\n+\t)\n+'\n+\n+test_expect_success 'merge-base agrees with --all for single result' '\n+\t(\n+\t\tcd graph-repo &&\n+\t\tgit commit-graph write --reachable &&\n+\t\tgit merge-base left right >actual.single &&\n+\t\tgit merge-base --all left right >actual.all &&\n+\t\ttest_cmp actual.all actual.single\n+\t)\n+'\n+\n+test_expect_success 'setup for deep chain commit-graph test' '\n+\tgit init deep-repo &&\n+\t(\n+\t\tcd deep-repo &&\n+\n+\t\t# Build a deep forked DAG:\n+\t\t#\n+\t\t# L1--L2--...--L20 (left)\n+\t\t# /\n+\t\t# S\n+\t\t# \\\n+\t\t# R1--R2--...--R20 (right)\n+\t\t#\n+\t\ttest_commit DS &&\n+\t\tgit checkout -b left &&\n+\t\tfor i in $(test_seq 1 20)\n+\t\tdo\n+\t\t\ttest_commit DL$i || return 1\n+\t\tdone &&\n+\t\tgit checkout DS &&\n+\t\tgit checkout -b right &&\n+\t\tfor i in $(test_seq 1 20)\n+\t\tdo\n+\t\t\ttest_commit DR$i || return 1\n+\t\tdone\n+\t)\n+'\n+\n+test_expect_success 'deep chain: merge-base matches with and without commit-graph' '\n+\t(\n+\t\tcd deep-repo &&\n+\t\trm -f .git/objects/info/commit-graph &&\n+\t\tgit merge-base left right >actual.no-graph &&\n+\t\tgit rev-parse DS >expected &&\n+\t\ttest_cmp expected actual.no-graph &&\n+\t\tgit commit-graph write --reachable &&\n+\t\tgit merge-base left right >actual.graph &&\n+\t\ttest_cmp expected actual.graph\n+\t)\n+'\n+\n+test_expect_success 'deep chain: --all and non---all agree with commit-graph' '\n+\t(\n+\t\tcd deep-repo &&\n+\t\tgit commit-graph write --reachable &&\n+\t\tgit merge-base left right >actual.single &&\n+\t\tgit merge-base --all left right >actual.all &&\n+\t\ttest_cmp actual.all actual.single\n+\t)\n+'\n+\n test_done\ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nindex dc0421ed2f..51c23b7683 100755\n--- a/t/t6600-test-reach.sh\n+++ b/t/t6600-test-reach.sh\n@@ -882,4 +882,44 @@ test_expect_success 'rev-list --maximal-only matches merge-base --independent' '\n \ttest_cmp expect.sorted actual.sorted\n '\n \n+# The following tests verify the early-exit optimisation in\n+# paint_down_to_common when merge-base is invoked without --all.\n+# Each test checks all four commit-graph configurations.\n+\n+merge_base_all_modes () {\n+\ttest_when_finished rm -rf .git/objects/info/commit-graph &&\n+\tgit merge-base \"$@\" >actual &&\n+\ttest_cmp expect actual &&\n+\tcp commit-graph-full .git/objects/info/commit-graph &&\n+\tgit merge-base \"$@\" >actual &&\n+\ttest_cmp expect actual &&\n+\tcp commit-graph-half .git/objects/info/commit-graph &&\n+\tgit merge-base \"$@\" >actual &&\n+\ttest_cmp expect actual &&\n+\tcp commit-graph-no-gdat .git/objects/info/commit-graph &&\n+\tgit merge-base \"$@\" >actual &&\n+\ttest_cmp expect actual\n+}\n+\n+test_expect_success 'merge-base without --all (unique base)' '\n+\tgit rev-parse commit-5-3 >expect &&\n+\tmerge_base_all_modes commit-5-7 commit-8-3\n+'\n+\n+test_expect_success 'merge-base without --all is one of --all results' '\n+\ttest_when_finished rm -rf .git/objects/info/commit-graph &&\n+\n+\tcp commit-graph-full .git/objects/info/commit-graph &&\n+\tgit merge-base --all commit-5-7 commit-4-8 commit-6-6 commit-8-3 >all &&\n+\tgit merge-base commit-5-7 commit-4-8 commit-6-6 commit-8-3 >single &&\n+\ttest_line_count = 1 single &&\n+\tgrep -F -f single all &&\n+\n+\tcp commit-graph-half .git/objects/info/commit-graph &&\n+\tgit merge-base --all commit-5-7 commit-4-8 commit-6-6 commit-8-3 >all &&\n+\tgit merge-base commit-5-7 commit-4-8 commit-6-6 commit-8-3 >single &&\n+\ttest_line_count = 1 single &&\n+\tgrep -F -f single all\n+'\n+\n test_done\n\nbase-commit: 94f057755b7941b321fd11fec1b2e3ca5313a4e0\n-- \ngitgitgadget\n"},{"id":"542998","messageId":"xmqqh5oevgth.fsf@gitster.g","threadId":"65609","inReplyTo":"pull.2109.git.1778252837132.gitgitgadget@gmail.com","subject":"Re: [PATCH] commit-reach: early exit paint_down_to_common for single merge-base","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-05-11T02:08:26Z","receivedAt":"2026-05-11T02:08:28Z","isPatch":true,"body":"\"Kristofer Karlsson via GitGitGadget\" \nwrites:\n\n> diff --git a/commit-reach.c b/commit-reach.c\n> index d3a9b3ed6f..c9d2d594de 100644\n> --- a/commit-reach.c\n> +++ b/commit-reach.c\n> @@ -55,14 +55,16 @@ static int paint_down_to_common(struct repository *r,\n> \t\t\t\tstruct commit **twos,\n> \t\t\t\ttimestamp_t min_generation,\n> \t\t\t\tint ignore_missing_commits,\n> +\t\t\t\tint find_all,\n> \t\t\t\tstruct commit_list **result)\n> {\n> \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n> \tint i;\n> +\tint has_gens = min_generation || corrected_commit_dates_enabled(r);\n\nGiving a name that identifies what the commonly-used logical\nexpression means is a very good idea, but don't some caller pass\nmin_generation==infinity (i.e., not zero) when there is no\ngeneration available? E.g., remove_redundant_no_gen() passes\nthe result of calling commit_graph_generation(), and without commit\ngraph, we would get infinity here, right?\n\nGiven that the second user of this variable is guarded by !find_all,\nthe variable being true even when we shouldn't be using generation\nnumbers may not matter for the purpose of the early break, but then\nit means that the patch squanders the perfect opportunity to clarify\nwhat the variable means, which is not very lovely.\n\n> \ttimestamp_t last_gen = GENERATION_NUMBER_INFINITY;\n> \tstruct commit_list **tail = result;\n> \n> -\tif (!min_generation && !corrected_commit_dates_enabled(r))\n> +\tif (!has_gens)\n> \t\tqueue.compare = compare_commits_by_commit_date;\n> \n> \tone->object.flags |= PARENT1;\n> @@ -97,6 +99,11 @@ static int paint_down_to_common(struct repository *r,\n> \t\t\tif (!(commit->object.flags & RESULT)) {\n> \t\t\t\tcommit->object.flags |= RESULT;\n> \t\t\t\ttail = commit_list_append(commit, tail);\n> +\t\t\t\t/* Generation-ordered queue: no later\n> +\t\t\t\t * commit can dominate this one. */\n> +\t\t\t\tif (!find_all && has_gens &&\n> +\t\t\t\t generation < GENERATION_NUMBER_INFINITY)\n> +\t\t\t\t\tbreak;\n\nThree comments\n\n * See Documentation/CodingGuidelines for our preferred style for\n multi-line comments.\n\n * I do not think we often use \"dominate\" to describe relationship\n between commits, and I am not sure what you want the word to mean\n in this context. Can you clarify?\n\n * The code is getting way too deeply indented. Perhaps using a\n helper function and\n\n\n if (!(commit->object.flags & RESULT)) {\n if (mark_result(r, &tail, commit,\n\t\t\t\t\t\tfind_all, min_generation))\n break;\n }\n\n move the logic to mark the newly discovered commit as one of the\n possible result, and to tell the loop to terminate, to it, along\n with the comment on the meaning of its return value, may make the\n code easier to follow?\n\n> +/* To be used only when object flags after this call no longer matter.\n> + * When find_all is false and generation numbers are available, returns\n> + * after finding the first merge-base, skipping the STALE drain. */\n\nDitto on the style.\n"},{"id":"543014","messageId":"pull.2109.v2.git.1778480348118.gitgitgadget@gmail.com","threadId":"65609","inReplyTo":"pull.2109.git.1778252837132.gitgitgadget@gmail.com","subject":"[PATCH v2] commit-reach: early exit paint_down_to_common for single merge-base","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-05-11T06:19:08Z","receivedAt":"2026-05-11T06:19:11Z","isPatch":true,"body":"From: Kristofer Karlsson \n\nCommits not in the commit-graph get GENERATION_NUMBER_INFINITY and\nsort to the top of the priority queue. After those, commits with\nfinite generation numbers are popped in non-increasing order.\nWhen find_all is false the first doubly-painted commit with a\nfinite generation is therefore a best merge-base: no commit still\nin the queue can be a descendant of it. Skip the expensive STALE\ndrain in this case.\n\nAdd find_all parameter to repo_get_merge_bases_many_dirty() and\nthread it through to paint_down_to_common(). git merge-base\n(without --all) passes show_all=0, triggering the early exit.\n\nOn a 2.2M-commit merge-heavy monorepo with commit-graph:\n\n HEAD vs ~500: 5,229ms -> 24ms\n HEAD vs ~1000: 4,214ms -> 39ms\n HEAD vs ~5000: 3,799ms -> 46ms\n HEAD vs ~10000: 3,827ms -> 61ms\n\nSigned-off-by: Kristofer Karlsson \n---\n [RFC] commit-reach: skip STALE drain when only one merge-base needed\n \n Context for what this is all about.\n \n I am working with a very large git monorepo and have been investigating\n performance issues. After some digging I ended up looking more deeply\n into git merge-base. I saw it had an --all parameter but the default is\n to only return a single merge-base. Looking through the code and adding\n debug timing, I realized that although the total time to compute the\n merge-base was high, a very small amount of time was spent finding the\n initial merge-base value that was later returned.\n \n The optimization is actually quite dramatic in a large repo - runtime\n went down from 5000ms to 50ms, so it's roughly a 100x optimization. This\n comes from an exploding frontier of STALE commits to drain.\n \n Thus, my idea is simply to return early from the function once we know\n what will be returned. This only works if we find a candidate that we\n know will not be pruned later - but fortunately if we have a commit\n graph with generations we will visit commits in order such that it will\n actually not be pruned.\n \n CC: Derrick Stolee stolee@gmail.com\n \n Changes since v1 (thanks Junio for the review):\n \n * Dropped the has_gens variable entirely. If a commit has a finite\n generation then it is in the commit-graph, and so are all its\n ancestors — no additional check is needed to know the queue ordering\n is sound. Without a commit-graph every commit gets INFINITY and the\n guard never fires. This also avoids the misleading interaction with\n callers that pass non-zero min_generation without having generation\n data.\n \n * Simplified the early exit guard from three conditions to two:\n !find_all && generation < GENERATION_NUMBER_INFINITY.\n \n * Fixed multi-line comment style per CodingGuidelines.\n \n * Replaced \"dominate\" with concrete reasoning about queue ordering.\n \n * Did not extract a helper function: after the simplifications above\n the inner block is four lines and reads naturally inline. The right\n boundary for a helper is not obvious (it could absorb just the result\n marking, or also the RESULT flag check, or also the PARENT1|PARENT2\n test) and each level requires more local state passed by pointer.\n Happy to extract one if preferred.\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2109%2Fspkrka%2Fmerge-base-early-exit-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2109/spkrka/merge-base-early-exit-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/2109\n\nRange-diff vs v1:\n\n 1: 54cdf9bfd9 ! 1: f7b5c267f3 commit-reach: early exit paint_down_to_common for single merge-base\n @@ Metadata\n ## Commit message ##\n commit-reach: early exit paint_down_to_common for single merge-base\n \n - When find_all is false and generation numbers are available, the\n - priority queue pops in non-increasing generation order. The first\n - doubly-painted commit is a valid best merge-base; no later commit\n - can dominate it. Skip the expensive STALE drain in this case.\n -\n - The early exit is guarded by three conditions: find_all must be\n - false, the commit-graph must provide generation numbers, and the\n - merge-base commit itself must have a finite generation (not\n - GENERATION_NUMBER_INFINITY from being outside the commit-graph).\n + Commits not in the commit-graph get GENERATION_NUMBER_INFINITY and\n + sort to the top of the priority queue. After those, commits with\n + finite generation numbers are popped in non-increasing order.\n + When find_all is false the first doubly-painted commit with a\n + finite generation is therefore a best merge-base: no commit still\n + in the queue can be a descendant of it. Skip the expensive STALE\n + drain in this case.\n \n Add find_all parameter to repo_get_merge_bases_many_dirty() and\n thread it through to paint_down_to_common(). git merge-base\n @@ commit-reach.c: static int paint_down_to_common(struct repository *r,\n \t\t\t\tstruct commit_list **result)\n {\n \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n - \tint i;\n -+\tint has_gens = min_generation || corrected_commit_dates_enabled(r);\n - \ttimestamp_t last_gen = GENERATION_NUMBER_INFINITY;\n - \tstruct commit_list **tail = result;\n - \n --\tif (!min_generation && !corrected_commit_dates_enabled(r))\n -+\tif (!has_gens)\n - \t\tqueue.compare = compare_commits_by_commit_date;\n - \n - \tone->object.flags |= PARENT1;\n @@ commit-reach.c: static int paint_down_to_common(struct repository *r,\n \t\t\tif (!(commit->object.flags & RESULT)) {\n \t\t\t\tcommit->object.flags |= RESULT;\n \t\t\t\ttail = commit_list_append(commit, tail);\n -+\t\t\t\t/* Generation-ordered queue: no later\n -+\t\t\t\t * commit can dominate this one. */\n -+\t\t\t\tif (!find_all && has_gens &&\n ++\t\t\t\t/*\n ++\t\t\t\t * The queue is generation-ordered; no\n ++\t\t\t\t * remaining common ancestor can be a\n ++\t\t\t\t * descendant of this one.\n ++\t\t\t\t */\n ++\t\t\t\tif (!find_all &&\n +\t\t\t\t generation < GENERATION_NUMBER_INFINITY)\n +\t\t\t\t\tbreak;\n \t\t\t}\n @@ commit-reach.h: int repo_get_merge_bases_many(struct repository *r,\n \t\t\t struct commit **twos,\n \t\t\t struct commit_list **result);\n -/* To be used only when object flags after this call no longer matter */\n -+/* To be used only when object flags after this call no longer matter.\n ++/*\n ++ * To be used only when object flags after this call no longer matter.\n + * When find_all is false and generation numbers are available, returns\n -+ * after finding the first merge-base, skipping the STALE drain. */\n ++ * after finding the first merge-base, skipping the STALE drain.\n ++ */\n int repo_get_merge_bases_many_dirty(struct repository *r,\n \t\t\t\t struct commit *one, size_t n,\n \t\t\t\t struct commit **twos,\n\n\n builtin/merge-base.c | 3 +-\n commit-reach.c | 26 ++++++---\n commit-reach.h | 7 ++-\n t/t6010-merge-base.sh | 119 ++++++++++++++++++++++++++++++++++++++++++\n t/t6600-test-reach.sh | 40 ++++++++++++++\n 5 files changed, 186 insertions(+), 9 deletions(-)\n\ndiff --git a/builtin/merge-base.c b/builtin/merge-base.c\nindex c7ee97fa6a..6b9d42f596 100644\n--- a/builtin/merge-base.c\n+++ b/builtin/merge-base.c\n@@ -14,7 +14,8 @@ static int show_merge_base(struct commit **rev, size_t rev_nr, int show_all)\n \tstruct commit_list *result = NULL, *r;\n \n \tif (repo_get_merge_bases_many_dirty(the_repository, rev[0],\n-\t\t\t\t\t rev_nr - 1, rev + 1, &result) < 0) {\n+\t\t\t\t\t rev_nr - 1, rev + 1,\n+\t\t\t\t\t show_all, &result) < 0) {\n \t\tcommit_list_free(result);\n \t\treturn -1;\n \t}\ndiff --git a/commit-reach.c b/commit-reach.c\nindex d3a9b3ed6f..b4ca00bb7e 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -55,6 +55,7 @@ static int paint_down_to_common(struct repository *r,\n \t\t\t\tstruct commit **twos,\n \t\t\t\ttimestamp_t min_generation,\n \t\t\t\tint ignore_missing_commits,\n+\t\t\t\tint find_all,\n \t\t\t\tstruct commit_list **result)\n {\n \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n@@ -97,6 +98,14 @@ static int paint_down_to_common(struct repository *r,\n \t\t\tif (!(commit->object.flags & RESULT)) {\n \t\t\t\tcommit->object.flags |= RESULT;\n \t\t\t\ttail = commit_list_append(commit, tail);\n+\t\t\t\t/*\n+\t\t\t\t * The queue is generation-ordered; no\n+\t\t\t\t * remaining common ancestor can be a\n+\t\t\t\t * descendant of this one.\n+\t\t\t\t */\n+\t\t\t\tif (!find_all &&\n+\t\t\t\t generation < GENERATION_NUMBER_INFINITY)\n+\t\t\t\t\tbreak;\n \t\t\t}\n \t\t\t/* Mark parents of a found merge stale */\n \t\t\tflags |= STALE;\n@@ -136,6 +145,7 @@ static int paint_down_to_common(struct repository *r,\n static int merge_bases_many(struct repository *r,\n \t\t\t struct commit *one, int n,\n \t\t\t struct commit **twos,\n+\t\t\t int find_all,\n \t\t\t struct commit_list **result)\n {\n \tstruct commit_list *list = NULL, **tail = result;\n@@ -165,7 +175,7 @@ static int merge_bases_many(struct repository *r,\n \t\t\t\t oid_to_hex(&twos[i]->object.oid));\n \t}\n \n-\tif (paint_down_to_common(r, one, n, twos, 0, 0, &list)) {\n+\tif (paint_down_to_common(r, one, n, twos, 0, 0, find_all, &list)) {\n \t\tcommit_list_free(list);\n \t\treturn -1;\n \t}\n@@ -246,7 +256,7 @@ static int remove_redundant_no_gen(struct repository *r,\n \t\t\t\tmin_generation = curr_generation;\n \t\t}\n \t\tif (paint_down_to_common(r, array[i], filled,\n-\t\t\t\t\t work, min_generation, 0, &common)) {\n+\t\t\t\t\t work, min_generation, 0, 1, &common)) {\n \t\t\tclear_commit_marks(array[i], all_flags);\n \t\t\tclear_commit_marks_many(filled, work, all_flags);\n \t\t\tcommit_list_free(common);\n@@ -425,6 +435,7 @@ static int get_merge_bases_many_0(struct repository *r,\n \t\t\t\t size_t n,\n \t\t\t\t struct commit **twos,\n \t\t\t\t int cleanup,\n+\t\t\t\t int find_all,\n \t\t\t\t struct commit_list **result)\n {\n \tstruct commit_list *list, **tail = result;\n@@ -432,7 +443,7 @@ static int get_merge_bases_many_0(struct repository *r,\n \tsize_t cnt, i;\n \tint ret;\n \n-\tif (merge_bases_many(r, one, n, twos, result) < 0)\n+\tif (merge_bases_many(r, one, n, twos, find_all, result) < 0)\n \t\treturn -1;\n \tfor (i = 0; i < n; i++) {\n \t\tif (one == twos[i])\n@@ -475,16 +486,17 @@ int repo_get_merge_bases_many(struct repository *r,\n \t\t\t struct commit **twos,\n \t\t\t struct commit_list **result)\n {\n-\treturn get_merge_bases_many_0(r, one, n, twos, 1, result);\n+\treturn get_merge_bases_many_0(r, one, n, twos, 1, 1, result);\n }\n \n int repo_get_merge_bases_many_dirty(struct repository *r,\n \t\t\t\t struct commit *one,\n \t\t\t\t size_t n,\n \t\t\t\t struct commit **twos,\n+\t\t\t\t int find_all,\n \t\t\t\t struct commit_list **result)\n {\n-\treturn get_merge_bases_many_0(r, one, n, twos, 0, result);\n+\treturn get_merge_bases_many_0(r, one, n, twos, 0, find_all, result);\n }\n \n int repo_get_merge_bases(struct repository *r,\n@@ -492,7 +504,7 @@ int repo_get_merge_bases(struct repository *r,\n \t\t\t struct commit *two,\n \t\t\t struct commit_list **result)\n {\n-\treturn get_merge_bases_many_0(r, one, 1, &two, 1, result);\n+\treturn get_merge_bases_many_0(r, one, 1, &two, 1, 1, result);\n }\n \n /*\n@@ -555,7 +567,7 @@ int repo_in_merge_bases_many(struct repository *r, struct commit *commit,\n \n \tif (paint_down_to_common(r, commit,\n \t\t\t\t nr_reference, reference,\n-\t\t\t\t generation, ignore_missing_commits, &bases))\n+\t\t\t\t generation, ignore_missing_commits, 1, &bases))\n \t\tret = -1;\n \telse if (commit->object.flags & PARENT2)\n \t\tret = 1;\ndiff --git a/commit-reach.h b/commit-reach.h\nindex 6012402dfc..c3b570a5cc 100644\n--- a/commit-reach.h\n+++ b/commit-reach.h\n@@ -17,10 +17,15 @@ int repo_get_merge_bases_many(struct repository *r,\n \t\t\t struct commit *one, size_t n,\n \t\t\t struct commit **twos,\n \t\t\t struct commit_list **result);\n-/* To be used only when object flags after this call no longer matter */\n+/*\n+ * To be used only when object flags after this call no longer matter.\n+ * When find_all is false and generation numbers are available, returns\n+ * after finding the first merge-base, skipping the STALE drain.\n+ */\n int repo_get_merge_bases_many_dirty(struct repository *r,\n \t\t\t\t struct commit *one, size_t n,\n \t\t\t\t struct commit **twos,\n+\t\t\t\t int find_all,\n \t\t\t\t struct commit_list **result);\n \n int get_octopus_merge_bases(struct commit_list *in, struct commit_list **result);\ndiff --git a/t/t6010-merge-base.sh b/t/t6010-merge-base.sh\nindex 44c726ea39..f6c85d4f53 100755\n--- a/t/t6010-merge-base.sh\n+++ b/t/t6010-merge-base.sh\n@@ -305,4 +305,123 @@ test_expect_success 'merge-base --octopus --all for complex tree' '\n \ttest_cmp expected actual\n '\n \n+# The following tests verify that \"git merge-base\" (without --all)\n+# returns the same result with and without a commit-graph.\n+# This exercises the early-exit optimisation in paint_down_to_common\n+# that skips the STALE drain when generation numbers are available.\n+\n+test_expect_success 'setup for commit-graph tests' '\n+\tgit init graph-repo &&\n+\t(\n+\t\tcd graph-repo &&\n+\n+\t\t# Build a forked DAG:\n+\t\t#\n+\t\t# L1---L2 (left)\n+\t\t# /\n+\t\t# S\n+\t\t# \\\n+\t\t# R1---R2 (right)\n+\t\t#\n+\t\ttest_commit GS &&\n+\t\tgit checkout -b left &&\n+\t\ttest_commit L1 &&\n+\t\ttest_commit L2 &&\n+\t\tgit checkout GS &&\n+\t\tgit checkout -b right &&\n+\t\ttest_commit GR1 &&\n+\t\ttest_commit GR2\n+\t)\n+'\n+\n+test_expect_success 'merge-base without commit-graph' '\n+\t(\n+\t\tcd graph-repo &&\n+\t\trm -f .git/objects/info/commit-graph &&\n+\t\tgit merge-base left right >actual &&\n+\t\tgit rev-parse GS >expected &&\n+\t\ttest_cmp expected actual\n+\t)\n+'\n+\n+test_expect_success 'merge-base with commit-graph' '\n+\t(\n+\t\tcd graph-repo &&\n+\t\tgit commit-graph write --reachable &&\n+\t\tgit merge-base left right >actual &&\n+\t\tgit rev-parse GS >expected &&\n+\t\ttest_cmp expected actual\n+\t)\n+'\n+\n+test_expect_success 'merge-base --all with commit-graph' '\n+\t(\n+\t\tcd graph-repo &&\n+\t\tgit merge-base --all left right >actual &&\n+\t\tgit rev-parse GS >expected &&\n+\t\ttest_cmp expected actual\n+\t)\n+'\n+\n+test_expect_success 'merge-base agrees with --all for single result' '\n+\t(\n+\t\tcd graph-repo &&\n+\t\tgit commit-graph write --reachable &&\n+\t\tgit merge-base left right >actual.single &&\n+\t\tgit merge-base --all left right >actual.all &&\n+\t\ttest_cmp actual.all actual.single\n+\t)\n+'\n+\n+test_expect_success 'setup for deep chain commit-graph test' '\n+\tgit init deep-repo &&\n+\t(\n+\t\tcd deep-repo &&\n+\n+\t\t# Build a deep forked DAG:\n+\t\t#\n+\t\t# L1--L2--...--L20 (left)\n+\t\t# /\n+\t\t# S\n+\t\t# \\\n+\t\t# R1--R2--...--R20 (right)\n+\t\t#\n+\t\ttest_commit DS &&\n+\t\tgit checkout -b left &&\n+\t\tfor i in $(test_seq 1 20)\n+\t\tdo\n+\t\t\ttest_commit DL$i || return 1\n+\t\tdone &&\n+\t\tgit checkout DS &&\n+\t\tgit checkout -b right &&\n+\t\tfor i in $(test_seq 1 20)\n+\t\tdo\n+\t\t\ttest_commit DR$i || return 1\n+\t\tdone\n+\t)\n+'\n+\n+test_expect_success 'deep chain: merge-base matches with and without commit-graph' '\n+\t(\n+\t\tcd deep-repo &&\n+\t\trm -f .git/objects/info/commit-graph &&\n+\t\tgit merge-base left right >actual.no-graph &&\n+\t\tgit rev-parse DS >expected &&\n+\t\ttest_cmp expected actual.no-graph &&\n+\t\tgit commit-graph write --reachable &&\n+\t\tgit merge-base left right >actual.graph &&\n+\t\ttest_cmp expected actual.graph\n+\t)\n+'\n+\n+test_expect_success 'deep chain: --all and non---all agree with commit-graph' '\n+\t(\n+\t\tcd deep-repo &&\n+\t\tgit commit-graph write --reachable &&\n+\t\tgit merge-base left right >actual.single &&\n+\t\tgit merge-base --all left right >actual.all &&\n+\t\ttest_cmp actual.all actual.single\n+\t)\n+'\n+\n test_done\ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nindex dc0421ed2f..51c23b7683 100755\n--- a/t/t6600-test-reach.sh\n+++ b/t/t6600-test-reach.sh\n@@ -882,4 +882,44 @@ test_expect_success 'rev-list --maximal-only matches merge-base --independent' '\n \ttest_cmp expect.sorted actual.sorted\n '\n \n+# The following tests verify the early-exit optimisation in\n+# paint_down_to_common when merge-base is invoked without --all.\n+# Each test checks all four commit-graph configurations.\n+\n+merge_base_all_modes () {\n+\ttest_when_finished rm -rf .git/objects/info/commit-graph &&\n+\tgit merge-base \"$@\" >actual &&\n+\ttest_cmp expect actual &&\n+\tcp commit-graph-full .git/objects/info/commit-graph &&\n+\tgit merge-base \"$@\" >actual &&\n+\ttest_cmp expect actual &&\n+\tcp commit-graph-half .git/objects/info/commit-graph &&\n+\tgit merge-base \"$@\" >actual &&\n+\ttest_cmp expect actual &&\n+\tcp commit-graph-no-gdat .git/objects/info/commit-graph &&\n+\tgit merge-base \"$@\" >actual &&\n+\ttest_cmp expect actual\n+}\n+\n+test_expect_success 'merge-base without --all (unique base)' '\n+\tgit rev-parse commit-5-3 >expect &&\n+\tmerge_base_all_modes commit-5-7 commit-8-3\n+'\n+\n+test_expect_success 'merge-base without --all is one of --all results' '\n+\ttest_when_finished rm -rf .git/objects/info/commit-graph &&\n+\n+\tcp commit-graph-full .git/objects/info/commit-graph &&\n+\tgit merge-base --all commit-5-7 commit-4-8 commit-6-6 commit-8-3 >all &&\n+\tgit merge-base commit-5-7 commit-4-8 commit-6-6 commit-8-3 >single &&\n+\ttest_line_count = 1 single &&\n+\tgrep -F -f single all &&\n+\n+\tcp commit-graph-half .git/objects/info/commit-graph &&\n+\tgit merge-base --all commit-5-7 commit-4-8 commit-6-6 commit-8-3 >all &&\n+\tgit merge-base commit-5-7 commit-4-8 commit-6-6 commit-8-3 >single &&\n+\ttest_line_count = 1 single &&\n+\tgrep -F -f single all\n+'\n+\n test_done\n\nbase-commit: 94f057755b7941b321fd11fec1b2e3ca5313a4e0\n-- \ngitgitgadget\n"},{"id":"543024","messageId":"agGDu4Nc5sBjpf_B@pks.im","threadId":"65609","inReplyTo":"pull.2109.v2.git.1778480348118.gitgitgadget@gmail.com","subject":"Re: [PATCH v2] commit-reach: early exit paint_down_to_common for single merge-base","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-05-11T07:22:35Z","receivedAt":"2026-05-11T07:22:40Z","isPatch":true,"body":"On Mon, May 11, 2026 at 06:19:08AM +0000, Kristofer Karlsson via GitGitGadget wrote:\n> diff --git a/commit-reach.c b/commit-reach.c\n> index d3a9b3ed6f..b4ca00bb7e 100644\n> --- a/commit-reach.c\n> +++ b/commit-reach.c\n> @@ -165,7 +175,7 @@ static int merge_bases_many(struct repository *r,\n> \t\t\t\t oid_to_hex(&twos[i]->object.oid));\n> \t}\n> \n> -\tif (paint_down_to_common(r, one, n, twos, 0, 0, &list)) {\n> +\tif (paint_down_to_common(r, one, n, twos, 0, 0, find_all, &list)) {\n> \t\tcommit_list_free(list);\n> \t\treturn -1;\n> \t}\n\nCallsites like this are quite hard to read now with these boolean flags.\nWould it be preferable to instead use flags?\n\n enum paint_down_to_common_flags {\n PAINT_DOWN_TO_COMMON_IGNORE_MISSING_COMMITS = (1 << 0),\n PAINT_DOWN_TO_COMMON_FIND_ALL = (1 << 1),\n };\n\nIt's more verbose of course, but that's kind of the point.\n\nOnly weirdness is that we don't only accept these flags in\n`paint_down_to_common()`, but also in other functions that pass those\nflags down.\n\nPatrick\n"},{"id":"543044","messageId":"pull.2109.v3.git.1778498532730.gitgitgadget@gmail.com","threadId":"65609","inReplyTo":"pull.2109.v2.git.1778480348118.gitgitgadget@gmail.com","subject":"[PATCH v3] commit-reach: early exit paint_down_to_common for single merge-base","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-05-11T11:22:12Z","receivedAt":"2026-05-11T11:22:17Z","isPatch":true,"body":"From: Kristofer Karlsson \n\nCommits not in the commit-graph get GENERATION_NUMBER_INFINITY and\nsort to the top of the priority queue. After those, commits with\nfinite generation numbers are popped in non-increasing order.\nWhen MERGE_BASE_FIND_ALL is not set the first doubly-painted commit\nwith a finite generation is therefore a best merge-base: no commit\nstill in the queue can be a descendant of it. Skip the expensive\nSTALE drain in this case.\n\nIntroduce enum merge_base_flags with MERGE_BASE_FIND_ALL and\nMERGE_BASE_IGNORE_MISSING_COMMITS, replacing the two boolean\nparameters in paint_down_to_common(). Thread the flags through\nmerge_bases_many(), get_merge_bases_many_0(), and the public\nrepo_get_merge_bases_many_dirty() API. git merge-base (without\n--all) passes 0, triggering the early exit.\n\nOn a 2.2M-commit merge-heavy monorepo with commit-graph:\n\n HEAD vs ~500: 5,229ms -> 24ms\n HEAD vs ~1000: 4,214ms -> 39ms\n HEAD vs ~5000: 3,799ms -> 46ms\n HEAD vs ~10000: 3,827ms -> 61ms\n\nSigned-off-by: Kristofer Karlsson \n---\n [RFC] commit-reach: skip STALE drain when only one merge-base needed\n \n Context for what this is all about.\n \n I am working with a very large git monorepo and have been investigating\n performance issues. After some digging I ended up looking more deeply\n into git merge-base. I saw it had an --all parameter but the default is\n to only return a single merge-base. Looking through the code and adding\n debug timing, I realized that although the total time to compute the\n merge-base was high, a very small amount of time was spent finding the\n initial merge-base value that was later returned.\n \n The optimization is actually quite dramatic in a large repo - runtime\n went down from 5000ms to 50ms, so it's roughly a 100x optimization. This\n comes from an exploding frontier of STALE commits to drain.\n \n Thus, my idea is simply to return early from the function once we know\n what will be returned. This only works if we find a candidate that we\n know will not be pruned later - but fortunately if we have a commit\n graph with generations we will visit commits in order such that it will\n actually not be pruned.\n \n CC: Derrick Stolee stolee@gmail.com\n \n Changes since v1 (thanks Junio for the review):\n \n * Dropped the has_gens variable entirely. If a commit has a finite\n generation then it is in the commit-graph, and so are all its\n ancestors — no additional check is needed to know the queue ordering\n is sound. Without a commit-graph every commit gets INFINITY and the\n guard never fires. This also avoids the misleading interaction with\n callers that pass non-zero min_generation without having generation\n data.\n \n * Simplified the early exit guard from three conditions to two:\n !find_all && generation < GENERATION_NUMBER_INFINITY.\n \n * Fixed multi-line comment style per CodingGuidelines.\n \n * Replaced \"dominate\" with concrete reasoning about queue ordering.\n \n * Did not extract a helper function: after the simplifications above\n the inner block is four lines and reads naturally inline. The right\n boundary for a helper is not obvious (it could absorb just the result\n marking, or also the RESULT flag check, or also the PARENT1|PARENT2\n test) and each level requires more local state passed by pointer.\n Happy to extract one if preferred.\n \n Changes since v2 (thanks Patrick for the suggestion):\n \n * Replaced the boolean find_all and ignore_missing_commits parameters\n in paint_down_to_common() with a single enum merge_base_flags\n mb_flags, reducing the function from 8 to 7 parameters. The enum is\n defined in commit-reach.h with MERGE_BASE_FIND_ALL and\n MERGE_BASE_IGNORE_MISSING_COMMITS.\n \n * Named the enum merge_base_flags rather than\n paint_down_to_common_flags since the flags express caller intent and\n are threaded through multiple layers including the public\n repo_get_merge_bases_many_dirty() API.\n \n * Used mb_flags as the parameter name to avoid shadowing the existing\n local int flags (commit object flags) inside paint_down_to_common().\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2109%2Fspkrka%2Fmerge-base-early-exit-v3\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2109/spkrka/merge-base-early-exit-v3\nPull-Request: https://github.com/gitgitgadget/git/pull/2109\n\nRange-diff vs v2:\n\n 1: f7b5c267f3 ! 1: e4dada892f commit-reach: early exit paint_down_to_common for single merge-base\n @@ Commit message\n Commits not in the commit-graph get GENERATION_NUMBER_INFINITY and\n sort to the top of the priority queue. After those, commits with\n finite generation numbers are popped in non-increasing order.\n - When find_all is false the first doubly-painted commit with a\n - finite generation is therefore a best merge-base: no commit still\n - in the queue can be a descendant of it. Skip the expensive STALE\n - drain in this case.\n + When MERGE_BASE_FIND_ALL is not set the first doubly-painted commit\n + with a finite generation is therefore a best merge-base: no commit\n + still in the queue can be a descendant of it. Skip the expensive\n + STALE drain in this case.\n \n - Add find_all parameter to repo_get_merge_bases_many_dirty() and\n - thread it through to paint_down_to_common(). git merge-base\n - (without --all) passes show_all=0, triggering the early exit.\n + Introduce enum merge_base_flags with MERGE_BASE_FIND_ALL and\n + MERGE_BASE_IGNORE_MISSING_COMMITS, replacing the two boolean\n + parameters in paint_down_to_common(). Thread the flags through\n + merge_bases_many(), get_merge_bases_many_0(), and the public\n + repo_get_merge_bases_many_dirty() API. git merge-base (without\n + --all) passes 0, triggering the early exit.\n \n On a 2.2M-commit merge-heavy monorepo with commit-graph:\n \n @@ Commit message\n Signed-off-by: Kristofer Karlsson \n \n ## builtin/merge-base.c ##\n -@@ builtin/merge-base.c: static int show_merge_base(struct commit **rev, size_t rev_nr, int show_all)\n +@@\n + \n + static int show_merge_base(struct commit **rev, size_t rev_nr, int show_all)\n + {\n ++\tenum merge_base_flags flags = show_all ? MERGE_BASE_FIND_ALL : 0;\n \tstruct commit_list *result = NULL, *r;\n \n \tif (repo_get_merge_bases_many_dirty(the_repository, rev[0],\n -\t\t\t\t\t rev_nr - 1, rev + 1, &result) < 0) {\n +\t\t\t\t\t rev_nr - 1, rev + 1,\n -+\t\t\t\t\t show_all, &result) < 0) {\n ++\t\t\t\t\t flags, &result) < 0) {\n \t\tcommit_list_free(result);\n \t\treturn -1;\n \t}\n \n ## commit-reach.c ##\n @@ commit-reach.c: static int paint_down_to_common(struct repository *r,\n + \t\t\t\tstruct commit *one, int n,\n \t\t\t\tstruct commit **twos,\n \t\t\t\ttimestamp_t min_generation,\n - \t\t\t\tint ignore_missing_commits,\n -+\t\t\t\tint find_all,\n +-\t\t\t\tint ignore_missing_commits,\n ++\t\t\t\tenum merge_base_flags mb_flags,\n \t\t\t\tstruct commit_list **result)\n {\n \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n @@ commit-reach.c: static int paint_down_to_common(struct repository *r,\n +\t\t\t\t * remaining common ancestor can be a\n +\t\t\t\t * descendant of this one.\n +\t\t\t\t */\n -+\t\t\t\tif (!find_all &&\n ++\t\t\t\tif (!(mb_flags & MERGE_BASE_FIND_ALL) &&\n +\t\t\t\t generation < GENERATION_NUMBER_INFINITY)\n +\t\t\t\t\tbreak;\n \t\t\t}\n \t\t\t/* Mark parents of a found merge stale */\n \t\t\tflags |= STALE;\n +@@ commit-reach.c: static int paint_down_to_common(struct repository *r,\n + \t\t\t\t * corrupt commits would already have been\n + \t\t\t\t * dispatched with a `die()`.\n + \t\t\t\t */\n +-\t\t\t\tif (ignore_missing_commits)\n ++\t\t\t\tif (mb_flags & MERGE_BASE_IGNORE_MISSING_COMMITS)\n + \t\t\t\t\treturn 0;\n + \t\t\t\treturn error(_(\"could not parse commit %s\"),\n + \t\t\t\t\t oid_to_hex(&p->object.oid));\n @@ commit-reach.c: static int paint_down_to_common(struct repository *r,\n static int merge_bases_many(struct repository *r,\n \t\t\t struct commit *one, int n,\n \t\t\t struct commit **twos,\n -+\t\t\t int find_all,\n ++\t\t\t enum merge_base_flags mb_flags,\n \t\t\t struct commit_list **result)\n {\n \tstruct commit_list *list = NULL, **tail = result;\n @@ commit-reach.c: static int merge_bases_many(struct repository *r,\n \t}\n \n -\tif (paint_down_to_common(r, one, n, twos, 0, 0, &list)) {\n -+\tif (paint_down_to_common(r, one, n, twos, 0, 0, find_all, &list)) {\n ++\tif (paint_down_to_common(r, one, n, twos, 0, mb_flags, &list)) {\n \t\tcommit_list_free(list);\n \t\treturn -1;\n \t}\n @@ commit-reach.c: static int remove_redundant_no_gen(struct repository *r,\n \t\t}\n \t\tif (paint_down_to_common(r, array[i], filled,\n -\t\t\t\t\t work, min_generation, 0, &common)) {\n -+\t\t\t\t\t work, min_generation, 0, 1, &common)) {\n ++\t\t\t\t\t work, min_generation,\n ++\t\t\t\t\t MERGE_BASE_FIND_ALL, &common)) {\n \t\t\tclear_commit_marks(array[i], all_flags);\n \t\t\tclear_commit_marks_many(filled, work, all_flags);\n \t\t\tcommit_list_free(common);\n @@ commit-reach.c: static int get_merge_bases_many_0(struct repository *r,\n \t\t\t\t size_t n,\n \t\t\t\t struct commit **twos,\n \t\t\t\t int cleanup,\n -+\t\t\t\t int find_all,\n ++\t\t\t\t enum merge_base_flags mb_flags,\n \t\t\t\t struct commit_list **result)\n {\n \tstruct commit_list *list, **tail = result;\n @@ commit-reach.c: static int get_merge_bases_many_0(struct repository *r,\n \tint ret;\n \n -\tif (merge_bases_many(r, one, n, twos, result) < 0)\n -+\tif (merge_bases_many(r, one, n, twos, find_all, result) < 0)\n ++\tif (merge_bases_many(r, one, n, twos, mb_flags, result) < 0)\n \t\treturn -1;\n \tfor (i = 0; i < n; i++) {\n \t\tif (one == twos[i])\n @@ commit-reach.c: int repo_get_merge_bases_many(struct repository *r,\n \t\t\t struct commit_list **result)\n {\n -\treturn get_merge_bases_many_0(r, one, n, twos, 1, result);\n -+\treturn get_merge_bases_many_0(r, one, n, twos, 1, 1, result);\n ++\treturn get_merge_bases_many_0(r, one, n, twos, 1,\n ++\t\t\t\t MERGE_BASE_FIND_ALL, result);\n }\n \n int repo_get_merge_bases_many_dirty(struct repository *r,\n \t\t\t\t struct commit *one,\n \t\t\t\t size_t n,\n \t\t\t\t struct commit **twos,\n -+\t\t\t\t int find_all,\n ++\t\t\t\t enum merge_base_flags mb_flags,\n \t\t\t\t struct commit_list **result)\n {\n -\treturn get_merge_bases_many_0(r, one, n, twos, 0, result);\n -+\treturn get_merge_bases_many_0(r, one, n, twos, 0, find_all, result);\n ++\treturn get_merge_bases_many_0(r, one, n, twos, 0, mb_flags, result);\n }\n \n int repo_get_merge_bases(struct repository *r,\n @@ commit-reach.c: int repo_get_merge_bases(struct repository *r,\n \t\t\t struct commit_list **result)\n {\n -\treturn get_merge_bases_many_0(r, one, 1, &two, 1, result);\n -+\treturn get_merge_bases_many_0(r, one, 1, &two, 1, 1, result);\n ++\treturn get_merge_bases_many_0(r, one, 1, &two, 1,\n ++\t\t\t\t MERGE_BASE_FIND_ALL, result);\n }\n \n /*\n @@ commit-reach.c: int repo_in_merge_bases_many(struct repository *r, struct commit *commit,\n + \tstruct commit_list *bases = NULL;\n + \tint ret = 0, i;\n + \ttimestamp_t generation, max_generation = GENERATION_NUMBER_ZERO;\n ++\tenum merge_base_flags mb_flags = MERGE_BASE_FIND_ALL;\n ++\n ++\tif (ignore_missing_commits)\n ++\t\tmb_flags |= MERGE_BASE_IGNORE_MISSING_COMMITS;\n + \n + \tif (repo_parse_commit(r, commit))\n + \t\treturn ignore_missing_commits ? 0 : -1;\n +@@ commit-reach.c: int repo_in_merge_bases_many(struct repository *r, struct commit *commit,\n \n \tif (paint_down_to_common(r, commit,\n \t\t\t\t nr_reference, reference,\n -\t\t\t\t generation, ignore_missing_commits, &bases))\n -+\t\t\t\t generation, ignore_missing_commits, 1, &bases))\n ++\t\t\t\t generation, mb_flags, &bases))\n \t\tret = -1;\n \telse if (commit->object.flags & PARENT2)\n \t\tret = 1;\n @@ commit-reach.h: int repo_get_merge_bases_many(struct repository *r,\n \t\t\t struct commit **twos,\n \t\t\t struct commit_list **result);\n -/* To be used only when object flags after this call no longer matter */\n ++enum merge_base_flags {\n ++\tMERGE_BASE_FIND_ALL = (1 << 0),\n ++\tMERGE_BASE_IGNORE_MISSING_COMMITS = (1 << 1),\n ++};\n ++\n +/*\n + * To be used only when object flags after this call no longer matter.\n -+ * When find_all is false and generation numbers are available, returns\n -+ * after finding the first merge-base, skipping the STALE drain.\n ++ * Without MERGE_BASE_FIND_ALL and with generation numbers available,\n ++ * returns after finding the first merge-base, skipping the STALE drain.\n + */\n int repo_get_merge_bases_many_dirty(struct repository *r,\n \t\t\t\t struct commit *one, size_t n,\n \t\t\t\t struct commit **twos,\n -+\t\t\t\t int find_all,\n ++\t\t\t\t enum merge_base_flags mb_flags,\n \t\t\t\t struct commit_list **result);\n \n int get_octopus_merge_bases(struct commit_list *in, struct commit_list **result);\n\n\n builtin/merge-base.c | 4 +-\n commit-reach.c | 36 +++++++++----\n commit-reach.h | 12 ++++-\n t/t6010-merge-base.sh | 119 ++++++++++++++++++++++++++++++++++++++++++\n t/t6600-test-reach.sh | 40 ++++++++++++++\n 5 files changed, 200 insertions(+), 11 deletions(-)\n\ndiff --git a/builtin/merge-base.c b/builtin/merge-base.c\nindex c7ee97fa6a..a87011c6cd 100644\n--- a/builtin/merge-base.c\n+++ b/builtin/merge-base.c\n@@ -11,10 +11,12 @@\n \n static int show_merge_base(struct commit **rev, size_t rev_nr, int show_all)\n {\n+\tenum merge_base_flags flags = show_all ? MERGE_BASE_FIND_ALL : 0;\n \tstruct commit_list *result = NULL, *r;\n \n \tif (repo_get_merge_bases_many_dirty(the_repository, rev[0],\n-\t\t\t\t\t rev_nr - 1, rev + 1, &result) < 0) {\n+\t\t\t\t\t rev_nr - 1, rev + 1,\n+\t\t\t\t\t flags, &result) < 0) {\n \t\tcommit_list_free(result);\n \t\treturn -1;\n \t}\ndiff --git a/commit-reach.c b/commit-reach.c\nindex d3a9b3ed6f..5a52be90a6 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -54,7 +54,7 @@ static int paint_down_to_common(struct repository *r,\n \t\t\t\tstruct commit *one, int n,\n \t\t\t\tstruct commit **twos,\n \t\t\t\ttimestamp_t min_generation,\n-\t\t\t\tint ignore_missing_commits,\n+\t\t\t\tenum merge_base_flags mb_flags,\n \t\t\t\tstruct commit_list **result)\n {\n \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n@@ -97,6 +97,14 @@ static int paint_down_to_common(struct repository *r,\n \t\t\tif (!(commit->object.flags & RESULT)) {\n \t\t\t\tcommit->object.flags |= RESULT;\n \t\t\t\ttail = commit_list_append(commit, tail);\n+\t\t\t\t/*\n+\t\t\t\t * The queue is generation-ordered; no\n+\t\t\t\t * remaining common ancestor can be a\n+\t\t\t\t * descendant of this one.\n+\t\t\t\t */\n+\t\t\t\tif (!(mb_flags & MERGE_BASE_FIND_ALL) &&\n+\t\t\t\t generation < GENERATION_NUMBER_INFINITY)\n+\t\t\t\t\tbreak;\n \t\t\t}\n \t\t\t/* Mark parents of a found merge stale */\n \t\t\tflags |= STALE;\n@@ -118,7 +126,7 @@ static int paint_down_to_common(struct repository *r,\n \t\t\t\t * corrupt commits would already have been\n \t\t\t\t * dispatched with a `die()`.\n \t\t\t\t */\n-\t\t\t\tif (ignore_missing_commits)\n+\t\t\t\tif (mb_flags & MERGE_BASE_IGNORE_MISSING_COMMITS)\n \t\t\t\t\treturn 0;\n \t\t\t\treturn error(_(\"could not parse commit %s\"),\n \t\t\t\t\t oid_to_hex(&p->object.oid));\n@@ -136,6 +144,7 @@ static int paint_down_to_common(struct repository *r,\n static int merge_bases_many(struct repository *r,\n \t\t\t struct commit *one, int n,\n \t\t\t struct commit **twos,\n+\t\t\t enum merge_base_flags mb_flags,\n \t\t\t struct commit_list **result)\n {\n \tstruct commit_list *list = NULL, **tail = result;\n@@ -165,7 +174,7 @@ static int merge_bases_many(struct repository *r,\n \t\t\t\t oid_to_hex(&twos[i]->object.oid));\n \t}\n \n-\tif (paint_down_to_common(r, one, n, twos, 0, 0, &list)) {\n+\tif (paint_down_to_common(r, one, n, twos, 0, mb_flags, &list)) {\n \t\tcommit_list_free(list);\n \t\treturn -1;\n \t}\n@@ -246,7 +255,8 @@ static int remove_redundant_no_gen(struct repository *r,\n \t\t\t\tmin_generation = curr_generation;\n \t\t}\n \t\tif (paint_down_to_common(r, array[i], filled,\n-\t\t\t\t\t work, min_generation, 0, &common)) {\n+\t\t\t\t\t work, min_generation,\n+\t\t\t\t\t MERGE_BASE_FIND_ALL, &common)) {\n \t\t\tclear_commit_marks(array[i], all_flags);\n \t\t\tclear_commit_marks_many(filled, work, all_flags);\n \t\t\tcommit_list_free(common);\n@@ -425,6 +435,7 @@ static int get_merge_bases_many_0(struct repository *r,\n \t\t\t\t size_t n,\n \t\t\t\t struct commit **twos,\n \t\t\t\t int cleanup,\n+\t\t\t\t enum merge_base_flags mb_flags,\n \t\t\t\t struct commit_list **result)\n {\n \tstruct commit_list *list, **tail = result;\n@@ -432,7 +443,7 @@ static int get_merge_bases_many_0(struct repository *r,\n \tsize_t cnt, i;\n \tint ret;\n \n-\tif (merge_bases_many(r, one, n, twos, result) < 0)\n+\tif (merge_bases_many(r, one, n, twos, mb_flags, result) < 0)\n \t\treturn -1;\n \tfor (i = 0; i < n; i++) {\n \t\tif (one == twos[i])\n@@ -475,16 +486,18 @@ int repo_get_merge_bases_many(struct repository *r,\n \t\t\t struct commit **twos,\n \t\t\t struct commit_list **result)\n {\n-\treturn get_merge_bases_many_0(r, one, n, twos, 1, result);\n+\treturn get_merge_bases_many_0(r, one, n, twos, 1,\n+\t\t\t\t MERGE_BASE_FIND_ALL, result);\n }\n \n int repo_get_merge_bases_many_dirty(struct repository *r,\n \t\t\t\t struct commit *one,\n \t\t\t\t size_t n,\n \t\t\t\t struct commit **twos,\n+\t\t\t\t enum merge_base_flags mb_flags,\n \t\t\t\t struct commit_list **result)\n {\n-\treturn get_merge_bases_many_0(r, one, n, twos, 0, result);\n+\treturn get_merge_bases_many_0(r, one, n, twos, 0, mb_flags, result);\n }\n \n int repo_get_merge_bases(struct repository *r,\n@@ -492,7 +505,8 @@ int repo_get_merge_bases(struct repository *r,\n \t\t\t struct commit *two,\n \t\t\t struct commit_list **result)\n {\n-\treturn get_merge_bases_many_0(r, one, 1, &two, 1, result);\n+\treturn get_merge_bases_many_0(r, one, 1, &two, 1,\n+\t\t\t\t MERGE_BASE_FIND_ALL, result);\n }\n \n /*\n@@ -537,6 +551,10 @@ int repo_in_merge_bases_many(struct repository *r, struct commit *commit,\n \tstruct commit_list *bases = NULL;\n \tint ret = 0, i;\n \ttimestamp_t generation, max_generation = GENERATION_NUMBER_ZERO;\n+\tenum merge_base_flags mb_flags = MERGE_BASE_FIND_ALL;\n+\n+\tif (ignore_missing_commits)\n+\t\tmb_flags |= MERGE_BASE_IGNORE_MISSING_COMMITS;\n \n \tif (repo_parse_commit(r, commit))\n \t\treturn ignore_missing_commits ? 0 : -1;\n@@ -555,7 +573,7 @@ int repo_in_merge_bases_many(struct repository *r, struct commit *commit,\n \n \tif (paint_down_to_common(r, commit,\n \t\t\t\t nr_reference, reference,\n-\t\t\t\t generation, ignore_missing_commits, &bases))\n+\t\t\t\t generation, mb_flags, &bases))\n \t\tret = -1;\n \telse if (commit->object.flags & PARENT2)\n \t\tret = 1;\ndiff --git a/commit-reach.h b/commit-reach.h\nindex 6012402dfc..41607d8952 100644\n--- a/commit-reach.h\n+++ b/commit-reach.h\n@@ -17,10 +17,20 @@ int repo_get_merge_bases_many(struct repository *r,\n \t\t\t struct commit *one, size_t n,\n \t\t\t struct commit **twos,\n \t\t\t struct commit_list **result);\n-/* To be used only when object flags after this call no longer matter */\n+enum merge_base_flags {\n+\tMERGE_BASE_FIND_ALL = (1 << 0),\n+\tMERGE_BASE_IGNORE_MISSING_COMMITS = (1 << 1),\n+};\n+\n+/*\n+ * To be used only when object flags after this call no longer matter.\n+ * Without MERGE_BASE_FIND_ALL and with generation numbers available,\n+ * returns after finding the first merge-base, skipping the STALE drain.\n+ */\n int repo_get_merge_bases_many_dirty(struct repository *r,\n \t\t\t\t struct commit *one, size_t n,\n \t\t\t\t struct commit **twos,\n+\t\t\t\t enum merge_base_flags mb_flags,\n \t\t\t\t struct commit_list **result);\n \n int get_octopus_merge_bases(struct commit_list *in, struct commit_list **result);\ndiff --git a/t/t6010-merge-base.sh b/t/t6010-merge-base.sh\nindex 44c726ea39..f6c85d4f53 100755\n--- a/t/t6010-merge-base.sh\n+++ b/t/t6010-merge-base.sh\n@@ -305,4 +305,123 @@ test_expect_success 'merge-base --octopus --all for complex tree' '\n \ttest_cmp expected actual\n '\n \n+# The following tests verify that \"git merge-base\" (without --all)\n+# returns the same result with and without a commit-graph.\n+# This exercises the early-exit optimisation in paint_down_to_common\n+# that skips the STALE drain when generation numbers are available.\n+\n+test_expect_success 'setup for commit-graph tests' '\n+\tgit init graph-repo &&\n+\t(\n+\t\tcd graph-repo &&\n+\n+\t\t# Build a forked DAG:\n+\t\t#\n+\t\t# L1---L2 (left)\n+\t\t# /\n+\t\t# S\n+\t\t# \\\n+\t\t# R1---R2 (right)\n+\t\t#\n+\t\ttest_commit GS &&\n+\t\tgit checkout -b left &&\n+\t\ttest_commit L1 &&\n+\t\ttest_commit L2 &&\n+\t\tgit checkout GS &&\n+\t\tgit checkout -b right &&\n+\t\ttest_commit GR1 &&\n+\t\ttest_commit GR2\n+\t)\n+'\n+\n+test_expect_success 'merge-base without commit-graph' '\n+\t(\n+\t\tcd graph-repo &&\n+\t\trm -f .git/objects/info/commit-graph &&\n+\t\tgit merge-base left right >actual &&\n+\t\tgit rev-parse GS >expected &&\n+\t\ttest_cmp expected actual\n+\t)\n+'\n+\n+test_expect_success 'merge-base with commit-graph' '\n+\t(\n+\t\tcd graph-repo &&\n+\t\tgit commit-graph write --reachable &&\n+\t\tgit merge-base left right >actual &&\n+\t\tgit rev-parse GS >expected &&\n+\t\ttest_cmp expected actual\n+\t)\n+'\n+\n+test_expect_success 'merge-base --all with commit-graph' '\n+\t(\n+\t\tcd graph-repo &&\n+\t\tgit merge-base --all left right >actual &&\n+\t\tgit rev-parse GS >expected &&\n+\t\ttest_cmp expected actual\n+\t)\n+'\n+\n+test_expect_success 'merge-base agrees with --all for single result' '\n+\t(\n+\t\tcd graph-repo &&\n+\t\tgit commit-graph write --reachable &&\n+\t\tgit merge-base left right >actual.single &&\n+\t\tgit merge-base --all left right >actual.all &&\n+\t\ttest_cmp actual.all actual.single\n+\t)\n+'\n+\n+test_expect_success 'setup for deep chain commit-graph test' '\n+\tgit init deep-repo &&\n+\t(\n+\t\tcd deep-repo &&\n+\n+\t\t# Build a deep forked DAG:\n+\t\t#\n+\t\t# L1--L2--...--L20 (left)\n+\t\t# /\n+\t\t# S\n+\t\t# \\\n+\t\t# R1--R2--...--R20 (right)\n+\t\t#\n+\t\ttest_commit DS &&\n+\t\tgit checkout -b left &&\n+\t\tfor i in $(test_seq 1 20)\n+\t\tdo\n+\t\t\ttest_commit DL$i || return 1\n+\t\tdone &&\n+\t\tgit checkout DS &&\n+\t\tgit checkout -b right &&\n+\t\tfor i in $(test_seq 1 20)\n+\t\tdo\n+\t\t\ttest_commit DR$i || return 1\n+\t\tdone\n+\t)\n+'\n+\n+test_expect_success 'deep chain: merge-base matches with and without commit-graph' '\n+\t(\n+\t\tcd deep-repo &&\n+\t\trm -f .git/objects/info/commit-graph &&\n+\t\tgit merge-base left right >actual.no-graph &&\n+\t\tgit rev-parse DS >expected &&\n+\t\ttest_cmp expected actual.no-graph &&\n+\t\tgit commit-graph write --reachable &&\n+\t\tgit merge-base left right >actual.graph &&\n+\t\ttest_cmp expected actual.graph\n+\t)\n+'\n+\n+test_expect_success 'deep chain: --all and non---all agree with commit-graph' '\n+\t(\n+\t\tcd deep-repo &&\n+\t\tgit commit-graph write --reachable &&\n+\t\tgit merge-base left right >actual.single &&\n+\t\tgit merge-base --all left right >actual.all &&\n+\t\ttest_cmp actual.all actual.single\n+\t)\n+'\n+\n test_done\ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nindex dc0421ed2f..51c23b7683 100755\n--- a/t/t6600-test-reach.sh\n+++ b/t/t6600-test-reach.sh\n@@ -882,4 +882,44 @@ test_expect_success 'rev-list --maximal-only matches merge-base --independent' '\n \ttest_cmp expect.sorted actual.sorted\n '\n \n+# The following tests verify the early-exit optimisation in\n+# paint_down_to_common when merge-base is invoked without --all.\n+# Each test checks all four commit-graph configurations.\n+\n+merge_base_all_modes () {\n+\ttest_when_finished rm -rf .git/objects/info/commit-graph &&\n+\tgit merge-base \"$@\" >actual &&\n+\ttest_cmp expect actual &&\n+\tcp commit-graph-full .git/objects/info/commit-graph &&\n+\tgit merge-base \"$@\" >actual &&\n+\ttest_cmp expect actual &&\n+\tcp commit-graph-half .git/objects/info/commit-graph &&\n+\tgit merge-base \"$@\" >actual &&\n+\ttest_cmp expect actual &&\n+\tcp commit-graph-no-gdat .git/objects/info/commit-graph &&\n+\tgit merge-base \"$@\" >actual &&\n+\ttest_cmp expect actual\n+}\n+\n+test_expect_success 'merge-base without --all (unique base)' '\n+\tgit rev-parse commit-5-3 >expect &&\n+\tmerge_base_all_modes commit-5-7 commit-8-3\n+'\n+\n+test_expect_success 'merge-base without --all is one of --all results' '\n+\ttest_when_finished rm -rf .git/objects/info/commit-graph &&\n+\n+\tcp commit-graph-full .git/objects/info/commit-graph &&\n+\tgit merge-base --all commit-5-7 commit-4-8 commit-6-6 commit-8-3 >all &&\n+\tgit merge-base commit-5-7 commit-4-8 commit-6-6 commit-8-3 >single &&\n+\ttest_line_count = 1 single &&\n+\tgrep -F -f single all &&\n+\n+\tcp commit-graph-half .git/objects/info/commit-graph &&\n+\tgit merge-base --all commit-5-7 commit-4-8 commit-6-6 commit-8-3 >all &&\n+\tgit merge-base commit-5-7 commit-4-8 commit-6-6 commit-8-3 >single &&\n+\ttest_line_count = 1 single &&\n+\tgrep -F -f single all\n+'\n+\n test_done\n\nbase-commit: 94f057755b7941b321fd11fec1b2e3ca5313a4e0\n-- \ngitgitgadget\n"},{"id":"543045","messageId":"agHFxwc_L64hTL7i@pks.im","threadId":"65609","inReplyTo":"pull.2109.v3.git.1778498532730.gitgitgadget@gmail.com","subject":"Re: [PATCH v3] commit-reach: early exit paint_down_to_common for single merge-base","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-05-11T12:04:23Z","receivedAt":"2026-05-11T12:04:30Z","isPatch":true,"body":"On Mon, May 11, 2026 at 11:22:12AM +0000, Kristofer Karlsson via GitGitGadget wrote:\n> Changes since v2 (thanks Patrick for the suggestion):\n> \n> * Replaced the boolean find_all and ignore_missing_commits parameters\n> in paint_down_to_common() with a single enum merge_base_flags\n> mb_flags, reducing the function from 8 to 7 parameters. The enum is\n> defined in commit-reach.h with MERGE_BASE_FIND_ALL and\n> MERGE_BASE_IGNORE_MISSING_COMMITS.\n> \n> * Named the enum merge_base_flags rather than\n> paint_down_to_common_flags since the flags express caller intent and\n> are threaded through multiple layers including the public\n> repo_get_merge_bases_many_dirty() API.\n> \n> * Used mb_flags as the parameter name to avoid shadowing the existing\n> local int flags (commit object flags) inside paint_down_to_common().\n\nThanks for making these changes. I think it would make sense to split\nthis up into two commits though, where the first commit only introduces\nthe new enum (without the new flag) and the second commit then adds the\nnew flag and the performance optimization.\n\nThat'd help quite a bit with the review as it splits up the changes into\na refactoring-only change without any intended semantic change, and\nanother commit that then does result in a user-visible change.\n\nPatrick\n"},{"id":"543050","messageId":"pull.2109.v4.git.1778504352.gitgitgadget@gmail.com","threadId":"65609","inReplyTo":"pull.2109.v3.git.1778498532730.gitgitgadget@gmail.com","subject":"[PATCH v4 0/2] [RFC] commit-reach: skip STALE drain when only one merge-base needed","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-05-11T12:59:10Z","receivedAt":"2026-05-11T12:59:16Z","isPatch":true,"body":"Context for what this is all about.\n\nI am working with a very large git monorepo and have been investigating\nperformance issues. After some digging I ended up looking more deeply into\ngit merge-base. I saw it had an --all parameter but the default is to only\nreturn a single merge-base. Looking through the code and adding debug\ntiming, I realized that although the total time to compute the merge-base\nwas high, a very small amount of time was spent finding the initial\nmerge-base value that was later returned.\n\nThe optimization is actually quite dramatic in a large repo - runtime went\ndown from 5000ms to 50ms, so it's roughly a 100x optimization. This comes\nfrom an exploding frontier of STALE commits to drain.\n\nThus, my idea is simply to return early from the function once we know what\nwill be returned. This only works if we find a candidate that we know will\nnot be pruned later - but fortunately if we have a commit graph with\ngenerations we will visit commits in order such that it will actually not be\npruned.\n\nCC: Derrick Stolee stolee@gmail.com\n\nChanges since v1 (thanks Junio for the review):\n\n * Dropped the has_gens variable entirely. If a commit has a finite\n generation then it is in the commit-graph, and so are all its ancestors —\n no additional check is needed to know the queue ordering is sound.\n Without a commit-graph every commit gets INFINITY and the guard never\n fires. This also avoids the misleading interaction with callers that pass\n non-zero min_generation without having generation data.\n\n * Simplified the early exit guard from three conditions to two: !find_all\n && generation < GENERATION_NUMBER_INFINITY.\n\n * Fixed multi-line comment style per CodingGuidelines.\n\n * Replaced \"dominate\" with concrete reasoning about queue ordering.\n\n * Did not extract a helper function: after the simplifications above the\n inner block is four lines and reads naturally inline. The right boundary\n for a helper is not obvious (it could absorb just the result marking, or\n also the RESULT flag check, or also the PARENT1|PARENT2 test) and each\n level requires more local state passed by pointer. Happy to extract one\n if preferred.\n\nChanges since v2 (thanks Patrick for the suggestion):\n\n * Split into two commits: the first is a pure refactoring that introduces\n enum merge_base_flags and replaces the boolean ignore_missing_commits\n parameter, the second adds the new MERGE_BASE_FIND_ALL flag and the early\n exit optimization.\n\n * Replaced the boolean find_all and ignore_missing_commits parameters in\n paint_down_to_common() with a single enum merge_base_flags mb_flags,\n reducing the function from 8 to 7 parameters. The enum is threaded\n through merge_bases_many(), get_merge_bases_many_0(), and the public\n repo_get_merge_bases_many_dirty() API.\n\n * Named the enum merge_base_flags rather than paint_down_to_common_flags\n since the flags express caller intent and are threaded through multiple\n layers including the public API.\n\n * Used mb_flags as the parameter name to avoid shadowing the existing local\n int flags (commit object flags) inside paint_down_to_common().\n\nKristofer Karlsson (2):\n commit-reach: introduce merge_base_flags enum\n commit-reach: early exit paint_down_to_common for single merge-base\n\n builtin/merge-base.c | 4 +++-\n commit-reach.c | 36 +++++++++++++++++++++++++++---------\n commit-reach.h | 12 +++++++++++-\n t/t6600-test-reach.sh | 40 ++++++++++++++++++++++++++++++++++++++++\n 4 files changed, 81 insertions(+), 11 deletions(-)\n\n\nbase-commit: 94f057755b7941b321fd11fec1b2e3ca5313a4e0\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2109%2Fspkrka%2Fmerge-base-early-exit-v4\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2109/spkrka/merge-base-early-exit-v4\nPull-Request: https://github.com/gitgitgadget/git/pull/2109\n\nRange-diff vs v3:\n\n 1: e4dada892f ! 1: 12d9e1c85f commit-reach: early exit paint_down_to_common for single merge-base\n @@ Metadata\n Author: Kristofer Karlsson \n \n ## Commit message ##\n - commit-reach: early exit paint_down_to_common for single merge-base\n + commit-reach: introduce merge_base_flags enum\n \n - Commits not in the commit-graph get GENERATION_NUMBER_INFINITY and\n - sort to the top of the priority queue. After those, commits with\n - finite generation numbers are popped in non-increasing order.\n - When MERGE_BASE_FIND_ALL is not set the first doubly-painted commit\n - with a finite generation is therefore a best merge-base: no commit\n - still in the queue can be a descendant of it. Skip the expensive\n - STALE drain in this case.\n + Replace the boolean ignore_missing_commits parameter in\n + paint_down_to_common() with an enum merge_base_flags, and thread\n + the flags through merge_bases_many(), get_merge_bases_many_0(),\n + and the public repo_get_merge_bases_many_dirty() API.\n \n - Introduce enum merge_base_flags with MERGE_BASE_FIND_ALL and\n - MERGE_BASE_IGNORE_MISSING_COMMITS, replacing the two boolean\n - parameters in paint_down_to_common(). Thread the flags through\n - merge_bases_many(), get_merge_bases_many_0(), and the public\n - repo_get_merge_bases_many_dirty() API. git merge-base (without\n - --all) passes 0, triggering the early exit.\n + This makes callsites with boolean parameters easier to read and\n + prepares the function for additional flags in a subsequent commit.\n \n - On a 2.2M-commit merge-heavy monorepo with commit-graph:\n -\n - HEAD vs ~500: 5,229ms -> 24ms\n - HEAD vs ~1000: 4,214ms -> 39ms\n - HEAD vs ~5000: 3,799ms -> 46ms\n - HEAD vs ~10000: 3,827ms -> 61ms\n + No functional change: the single caller that used\n + ignore_missing_commits (repo_in_merge_bases_many) now sets\n + MERGE_BASE_IGNORE_MISSING_COMMITS in the flags word, and all\n + other callers pass 0.\n \n Signed-off-by: Kristofer Karlsson \n \n ## builtin/merge-base.c ##\n -@@\n - \n - static int show_merge_base(struct commit **rev, size_t rev_nr, int show_all)\n - {\n -+\tenum merge_base_flags flags = show_all ? MERGE_BASE_FIND_ALL : 0;\n +@@ builtin/merge-base.c: static int show_merge_base(struct commit **rev, size_t rev_nr, int show_all)\n \tstruct commit_list *result = NULL, *r;\n \n \tif (repo_get_merge_bases_many_dirty(the_repository, rev[0],\n -\t\t\t\t\t rev_nr - 1, rev + 1, &result) < 0) {\n +\t\t\t\t\t rev_nr - 1, rev + 1,\n -+\t\t\t\t\t flags, &result) < 0) {\n ++\t\t\t\t\t 0, &result) < 0) {\n \t\tcommit_list_free(result);\n \t\treturn -1;\n \t}\n @@ commit-reach.c: static int paint_down_to_common(struct repository *r,\n \t\t\t\tstruct commit_list **result)\n {\n \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n -@@ commit-reach.c: static int paint_down_to_common(struct repository *r,\n - \t\t\tif (!(commit->object.flags & RESULT)) {\n - \t\t\t\tcommit->object.flags |= RESULT;\n - \t\t\t\ttail = commit_list_append(commit, tail);\n -+\t\t\t\t/*\n -+\t\t\t\t * The queue is generation-ordered; no\n -+\t\t\t\t * remaining common ancestor can be a\n -+\t\t\t\t * descendant of this one.\n -+\t\t\t\t */\n -+\t\t\t\tif (!(mb_flags & MERGE_BASE_FIND_ALL) &&\n -+\t\t\t\t generation < GENERATION_NUMBER_INFINITY)\n -+\t\t\t\t\tbreak;\n - \t\t\t}\n - \t\t\t/* Mark parents of a found merge stale */\n - \t\t\tflags |= STALE;\n @@ commit-reach.c: static int paint_down_to_common(struct repository *r,\n \t\t\t\t * corrupt commits would already have been\n \t\t\t\t * dispatched with a `die()`.\n @@ commit-reach.c: static int merge_bases_many(struct repository *r,\n \t\tcommit_list_free(list);\n \t\treturn -1;\n \t}\n -@@ commit-reach.c: static int remove_redundant_no_gen(struct repository *r,\n - \t\t\t\tmin_generation = curr_generation;\n - \t\t}\n - \t\tif (paint_down_to_common(r, array[i], filled,\n --\t\t\t\t\t work, min_generation, 0, &common)) {\n -+\t\t\t\t\t work, min_generation,\n -+\t\t\t\t\t MERGE_BASE_FIND_ALL, &common)) {\n - \t\t\tclear_commit_marks(array[i], all_flags);\n - \t\t\tclear_commit_marks_many(filled, work, all_flags);\n - \t\t\tcommit_list_free(common);\n @@ commit-reach.c: static int get_merge_bases_many_0(struct repository *r,\n \t\t\t\t size_t n,\n \t\t\t\t struct commit **twos,\n @@ commit-reach.c: int repo_get_merge_bases_many(struct repository *r,\n \t\t\t struct commit_list **result)\n {\n -\treturn get_merge_bases_many_0(r, one, n, twos, 1, result);\n -+\treturn get_merge_bases_many_0(r, one, n, twos, 1,\n -+\t\t\t\t MERGE_BASE_FIND_ALL, result);\n ++\treturn get_merge_bases_many_0(r, one, n, twos, 1, 0, result);\n }\n \n int repo_get_merge_bases_many_dirty(struct repository *r,\n @@ commit-reach.c: int repo_get_merge_bases(struct repository *r,\n \t\t\t struct commit_list **result)\n {\n -\treturn get_merge_bases_many_0(r, one, 1, &two, 1, result);\n -+\treturn get_merge_bases_many_0(r, one, 1, &two, 1,\n -+\t\t\t\t MERGE_BASE_FIND_ALL, result);\n ++\treturn get_merge_bases_many_0(r, one, 1, &two, 1, 0, result);\n }\n \n /*\n @@ commit-reach.c: int repo_in_merge_bases_many(struct repository *r, struct commit\n \tstruct commit_list *bases = NULL;\n \tint ret = 0, i;\n \ttimestamp_t generation, max_generation = GENERATION_NUMBER_ZERO;\n -+\tenum merge_base_flags mb_flags = MERGE_BASE_FIND_ALL;\n ++\tenum merge_base_flags mb_flags = 0;\n +\n +\tif (ignore_missing_commits)\n +\t\tmb_flags |= MERGE_BASE_IGNORE_MISSING_COMMITS;\n @@ commit-reach.h: int repo_get_merge_bases_many(struct repository *r,\n \t\t\t struct commit *one, size_t n,\n \t\t\t struct commit **twos,\n \t\t\t struct commit_list **result);\n --/* To be used only when object flags after this call no longer matter */\n +enum merge_base_flags {\n -+\tMERGE_BASE_FIND_ALL = (1 << 0),\n -+\tMERGE_BASE_IGNORE_MISSING_COMMITS = (1 << 1),\n ++\tMERGE_BASE_IGNORE_MISSING_COMMITS = (1 << 0),\n +};\n +\n -+/*\n -+ * To be used only when object flags after this call no longer matter.\n -+ * Without MERGE_BASE_FIND_ALL and with generation numbers available,\n -+ * returns after finding the first merge-base, skipping the STALE drain.\n -+ */\n + /* To be used only when object flags after this call no longer matter */\n int repo_get_merge_bases_many_dirty(struct repository *r,\n \t\t\t\t struct commit *one, size_t n,\n \t\t\t\t struct commit **twos,\n @@ commit-reach.h: int repo_get_merge_bases_many(struct repository *r,\n \t\t\t\t struct commit_list **result);\n \n int get_octopus_merge_bases(struct commit_list *in, struct commit_list **result);\n -\n - ## t/t6010-merge-base.sh ##\n -@@ t/t6010-merge-base.sh: test_expect_success 'merge-base --octopus --all for complex tree' '\n - \ttest_cmp expected actual\n - '\n - \n -+# The following tests verify that \"git merge-base\" (without --all)\n -+# returns the same result with and without a commit-graph.\n -+# This exercises the early-exit optimisation in paint_down_to_common\n -+# that skips the STALE drain when generation numbers are available.\n -+\n -+test_expect_success 'setup for commit-graph tests' '\n -+\tgit init graph-repo &&\n -+\t(\n -+\t\tcd graph-repo &&\n -+\n -+\t\t# Build a forked DAG:\n -+\t\t#\n -+\t\t# L1---L2 (left)\n -+\t\t# /\n -+\t\t# S\n -+\t\t# \\\n -+\t\t# R1---R2 (right)\n -+\t\t#\n -+\t\ttest_commit GS &&\n -+\t\tgit checkout -b left &&\n -+\t\ttest_commit L1 &&\n -+\t\ttest_commit L2 &&\n -+\t\tgit checkout GS &&\n -+\t\tgit checkout -b right &&\n -+\t\ttest_commit GR1 &&\n -+\t\ttest_commit GR2\n -+\t)\n -+'\n -+\n -+test_expect_success 'merge-base without commit-graph' '\n -+\t(\n -+\t\tcd graph-repo &&\n -+\t\trm -f .git/objects/info/commit-graph &&\n -+\t\tgit merge-base left right >actual &&\n -+\t\tgit rev-parse GS >expected &&\n -+\t\ttest_cmp expected actual\n -+\t)\n -+'\n -+\n -+test_expect_success 'merge-base with commit-graph' '\n -+\t(\n -+\t\tcd graph-repo &&\n -+\t\tgit commit-graph write --reachable &&\n -+\t\tgit merge-base left right >actual &&\n -+\t\tgit rev-parse GS >expected &&\n -+\t\ttest_cmp expected actual\n -+\t)\n -+'\n -+\n -+test_expect_success 'merge-base --all with commit-graph' '\n -+\t(\n -+\t\tcd graph-repo &&\n -+\t\tgit merge-base --all left right >actual &&\n -+\t\tgit rev-parse GS >expected &&\n -+\t\ttest_cmp expected actual\n -+\t)\n -+'\n -+\n -+test_expect_success 'merge-base agrees with --all for single result' '\n -+\t(\n -+\t\tcd graph-repo &&\n -+\t\tgit commit-graph write --reachable &&\n -+\t\tgit merge-base left right >actual.single &&\n -+\t\tgit merge-base --all left right >actual.all &&\n -+\t\ttest_cmp actual.all actual.single\n -+\t)\n -+'\n -+\n -+test_expect_success 'setup for deep chain commit-graph test' '\n -+\tgit init deep-repo &&\n -+\t(\n -+\t\tcd deep-repo &&\n -+\n -+\t\t# Build a deep forked DAG:\n -+\t\t#\n -+\t\t# L1--L2--...--L20 (left)\n -+\t\t# /\n -+\t\t# S\n -+\t\t# \\\n -+\t\t# R1--R2--...--R20 (right)\n -+\t\t#\n -+\t\ttest_commit DS &&\n -+\t\tgit checkout -b left &&\n -+\t\tfor i in $(test_seq 1 20)\n -+\t\tdo\n -+\t\t\ttest_commit DL$i || return 1\n -+\t\tdone &&\n -+\t\tgit checkout DS &&\n -+\t\tgit checkout -b right &&\n -+\t\tfor i in $(test_seq 1 20)\n -+\t\tdo\n -+\t\t\ttest_commit DR$i || return 1\n -+\t\tdone\n -+\t)\n -+'\n -+\n -+test_expect_success 'deep chain: merge-base matches with and without commit-graph' '\n -+\t(\n -+\t\tcd deep-repo &&\n -+\t\trm -f .git/objects/info/commit-graph &&\n -+\t\tgit merge-base left right >actual.no-graph &&\n -+\t\tgit rev-parse DS >expected &&\n -+\t\ttest_cmp expected actual.no-graph &&\n -+\t\tgit commit-graph write --reachable &&\n -+\t\tgit merge-base left right >actual.graph &&\n -+\t\ttest_cmp expected actual.graph\n -+\t)\n -+'\n -+\n -+test_expect_success 'deep chain: --all and non---all agree with commit-graph' '\n -+\t(\n -+\t\tcd deep-repo &&\n -+\t\tgit commit-graph write --reachable &&\n -+\t\tgit merge-base left right >actual.single &&\n -+\t\tgit merge-base --all left right >actual.all &&\n -+\t\ttest_cmp actual.all actual.single\n -+\t)\n -+'\n -+\n - test_done\n -\n - ## t/t6600-test-reach.sh ##\n -@@ t/t6600-test-reach.sh: test_expect_success 'rev-list --maximal-only matches merge-base --independent' '\n - \ttest_cmp expect.sorted actual.sorted\n - '\n - \n -+# The following tests verify the early-exit optimisation in\n -+# paint_down_to_common when merge-base is invoked without --all.\n -+# Each test checks all four commit-graph configurations.\n -+\n -+merge_base_all_modes () {\n -+\ttest_when_finished rm -rf .git/objects/info/commit-graph &&\n -+\tgit merge-base \"$@\" >actual &&\n -+\ttest_cmp expect actual &&\n -+\tcp commit-graph-full .git/objects/info/commit-graph &&\n -+\tgit merge-base \"$@\" >actual &&\n -+\ttest_cmp expect actual &&\n -+\tcp commit-graph-half .git/objects/info/commit-graph &&\n -+\tgit merge-base \"$@\" >actual &&\n -+\ttest_cmp expect actual &&\n -+\tcp commit-graph-no-gdat .git/objects/info/commit-graph &&\n -+\tgit merge-base \"$@\" >actual &&\n -+\ttest_cmp expect actual\n -+}\n -+\n -+test_expect_success 'merge-base without --all (unique base)' '\n -+\tgit rev-parse commit-5-3 >expect &&\n -+\tmerge_base_all_modes commit-5-7 commit-8-3\n -+'\n -+\n -+test_expect_success 'merge-base without --all is one of --all results' '\n -+\ttest_when_finished rm -rf .git/objects/info/commit-graph &&\n -+\n -+\tcp commit-graph-full .git/objects/info/commit-graph &&\n -+\tgit merge-base --all commit-5-7 commit-4-8 commit-6-6 commit-8-3 >all &&\n -+\tgit merge-base commit-5-7 commit-4-8 commit-6-6 commit-8-3 >single &&\n -+\ttest_line_count = 1 single &&\n -+\tgrep -F -f single all &&\n -+\n -+\tcp commit-graph-half .git/objects/info/commit-graph &&\n -+\tgit merge-base --all commit-5-7 commit-4-8 commit-6-6 commit-8-3 >all &&\n -+\tgit merge-base commit-5-7 commit-4-8 commit-6-6 commit-8-3 >single &&\n -+\ttest_line_count = 1 single &&\n -+\tgrep -F -f single all\n -+'\n -+\n - test_done\n -: ---------- > 2: 19f1605067 commit-reach: early exit paint_down_to_common for single merge-base\n\n-- \ngitgitgadget\n"},{"id":"543051","messageId":"12d9e1c85f68703d069440c05dcc3eb3592274ed.1778504352.git.gitgitgadget@gmail.com","threadId":"65609","inReplyTo":"pull.2109.v4.git.1778504352.gitgitgadget@gmail.com","subject":"[PATCH v4 1/2] commit-reach: introduce merge_base_flags enum","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-05-11T12:59:11Z","receivedAt":"2026-05-11T12:59:17Z","isPatch":true,"body":"From: Kristofer Karlsson \n\nReplace the boolean ignore_missing_commits parameter in\npaint_down_to_common() with an enum merge_base_flags, and thread\nthe flags through merge_bases_many(), get_merge_bases_many_0(),\nand the public repo_get_merge_bases_many_dirty() API.\n\nThis makes callsites with boolean parameters easier to read and\nprepares the function for additional flags in a subsequent commit.\n\nNo functional change: the single caller that used\nignore_missing_commits (repo_in_merge_bases_many) now sets\nMERGE_BASE_IGNORE_MISSING_COMMITS in the flags word, and all\nother callers pass 0.\n\nSigned-off-by: Kristofer Karlsson \n---\n builtin/merge-base.c | 3 ++-\n commit-reach.c | 23 +++++++++++++++--------\n commit-reach.h | 5 +++++\n 3 files changed, 22 insertions(+), 9 deletions(-)\n\ndiff --git a/builtin/merge-base.c b/builtin/merge-base.c\nindex c7ee97fa6a..9b50b4660e 100644\n--- a/builtin/merge-base.c\n+++ b/builtin/merge-base.c\n@@ -14,7 +14,8 @@ static int show_merge_base(struct commit **rev, size_t rev_nr, int show_all)\n \tstruct commit_list *result = NULL, *r;\n \n \tif (repo_get_merge_bases_many_dirty(the_repository, rev[0],\n-\t\t\t\t\t rev_nr - 1, rev + 1, &result) < 0) {\n+\t\t\t\t\t rev_nr - 1, rev + 1,\n+\t\t\t\t\t 0, &result) < 0) {\n \t\tcommit_list_free(result);\n \t\treturn -1;\n \t}\ndiff --git a/commit-reach.c b/commit-reach.c\nindex d3a9b3ed6f..766ba1156a 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -54,7 +54,7 @@ static int paint_down_to_common(struct repository *r,\n \t\t\t\tstruct commit *one, int n,\n \t\t\t\tstruct commit **twos,\n \t\t\t\ttimestamp_t min_generation,\n-\t\t\t\tint ignore_missing_commits,\n+\t\t\t\tenum merge_base_flags mb_flags,\n \t\t\t\tstruct commit_list **result)\n {\n \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n@@ -118,7 +118,7 @@ static int paint_down_to_common(struct repository *r,\n \t\t\t\t * corrupt commits would already have been\n \t\t\t\t * dispatched with a `die()`.\n \t\t\t\t */\n-\t\t\t\tif (ignore_missing_commits)\n+\t\t\t\tif (mb_flags & MERGE_BASE_IGNORE_MISSING_COMMITS)\n \t\t\t\t\treturn 0;\n \t\t\t\treturn error(_(\"could not parse commit %s\"),\n \t\t\t\t\t oid_to_hex(&p->object.oid));\n@@ -136,6 +136,7 @@ static int paint_down_to_common(struct repository *r,\n static int merge_bases_many(struct repository *r,\n \t\t\t struct commit *one, int n,\n \t\t\t struct commit **twos,\n+\t\t\t enum merge_base_flags mb_flags,\n \t\t\t struct commit_list **result)\n {\n \tstruct commit_list *list = NULL, **tail = result;\n@@ -165,7 +166,7 @@ static int merge_bases_many(struct repository *r,\n \t\t\t\t oid_to_hex(&twos[i]->object.oid));\n \t}\n \n-\tif (paint_down_to_common(r, one, n, twos, 0, 0, &list)) {\n+\tif (paint_down_to_common(r, one, n, twos, 0, mb_flags, &list)) {\n \t\tcommit_list_free(list);\n \t\treturn -1;\n \t}\n@@ -425,6 +426,7 @@ static int get_merge_bases_many_0(struct repository *r,\n \t\t\t\t size_t n,\n \t\t\t\t struct commit **twos,\n \t\t\t\t int cleanup,\n+\t\t\t\t enum merge_base_flags mb_flags,\n \t\t\t\t struct commit_list **result)\n {\n \tstruct commit_list *list, **tail = result;\n@@ -432,7 +434,7 @@ static int get_merge_bases_many_0(struct repository *r,\n \tsize_t cnt, i;\n \tint ret;\n \n-\tif (merge_bases_many(r, one, n, twos, result) < 0)\n+\tif (merge_bases_many(r, one, n, twos, mb_flags, result) < 0)\n \t\treturn -1;\n \tfor (i = 0; i < n; i++) {\n \t\tif (one == twos[i])\n@@ -475,16 +477,17 @@ int repo_get_merge_bases_many(struct repository *r,\n \t\t\t struct commit **twos,\n \t\t\t struct commit_list **result)\n {\n-\treturn get_merge_bases_many_0(r, one, n, twos, 1, result);\n+\treturn get_merge_bases_many_0(r, one, n, twos, 1, 0, result);\n }\n \n int repo_get_merge_bases_many_dirty(struct repository *r,\n \t\t\t\t struct commit *one,\n \t\t\t\t size_t n,\n \t\t\t\t struct commit **twos,\n+\t\t\t\t enum merge_base_flags mb_flags,\n \t\t\t\t struct commit_list **result)\n {\n-\treturn get_merge_bases_many_0(r, one, n, twos, 0, result);\n+\treturn get_merge_bases_many_0(r, one, n, twos, 0, mb_flags, result);\n }\n \n int repo_get_merge_bases(struct repository *r,\n@@ -492,7 +495,7 @@ int repo_get_merge_bases(struct repository *r,\n \t\t\t struct commit *two,\n \t\t\t struct commit_list **result)\n {\n-\treturn get_merge_bases_many_0(r, one, 1, &two, 1, result);\n+\treturn get_merge_bases_many_0(r, one, 1, &two, 1, 0, result);\n }\n \n /*\n@@ -537,6 +540,10 @@ int repo_in_merge_bases_many(struct repository *r, struct commit *commit,\n \tstruct commit_list *bases = NULL;\n \tint ret = 0, i;\n \ttimestamp_t generation, max_generation = GENERATION_NUMBER_ZERO;\n+\tenum merge_base_flags mb_flags = 0;\n+\n+\tif (ignore_missing_commits)\n+\t\tmb_flags |= MERGE_BASE_IGNORE_MISSING_COMMITS;\n \n \tif (repo_parse_commit(r, commit))\n \t\treturn ignore_missing_commits ? 0 : -1;\n@@ -555,7 +562,7 @@ int repo_in_merge_bases_many(struct repository *r, struct commit *commit,\n \n \tif (paint_down_to_common(r, commit,\n \t\t\t\t nr_reference, reference,\n-\t\t\t\t generation, ignore_missing_commits, &bases))\n+\t\t\t\t generation, mb_flags, &bases))\n \t\tret = -1;\n \telse if (commit->object.flags & PARENT2)\n \t\tret = 1;\ndiff --git a/commit-reach.h b/commit-reach.h\nindex 6012402dfc..a3f2cd80eb 100644\n--- a/commit-reach.h\n+++ b/commit-reach.h\n@@ -17,10 +17,15 @@ int repo_get_merge_bases_many(struct repository *r,\n \t\t\t struct commit *one, size_t n,\n \t\t\t struct commit **twos,\n \t\t\t struct commit_list **result);\n+enum merge_base_flags {\n+\tMERGE_BASE_IGNORE_MISSING_COMMITS = (1 << 0),\n+};\n+\n /* To be used only when object flags after this call no longer matter */\n int repo_get_merge_bases_many_dirty(struct repository *r,\n \t\t\t\t struct commit *one, size_t n,\n \t\t\t\t struct commit **twos,\n+\t\t\t\t enum merge_base_flags mb_flags,\n \t\t\t\t struct commit_list **result);\n \n int get_octopus_merge_bases(struct commit_list *in, struct commit_list **result);\n-- \ngitgitgadget\n\n"},{"id":"543052","messageId":"19f1605067e26c8e393c6c2e341844bcb3dc1b41.1778504352.git.gitgitgadget@gmail.com","threadId":"65609","inReplyTo":"pull.2109.v4.git.1778504352.gitgitgadget@gmail.com","subject":"[PATCH v4 2/2] commit-reach: early exit paint_down_to_common for single merge-base","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-05-11T12:59:12Z","receivedAt":"2026-05-11T12:59:19Z","isPatch":true,"body":"From: Kristofer Karlsson \n\nCommits not in the commit-graph get GENERATION_NUMBER_INFINITY and\nsort to the top of the priority queue. After those, commits with\nfinite generation numbers are popped in non-increasing order.\nWhen MERGE_BASE_FIND_ALL is not set the first doubly-painted commit\nwith a finite generation is therefore a best merge-base: no commit\nstill in the queue can be a descendant of it. Skip the expensive\nSTALE drain in this case.\n\nAdd MERGE_BASE_FIND_ALL to the merge_base_flags enum. Callers that\nneed every merge-base (repo_get_merge_bases_many, repo_get_merge_bases,\nrepo_in_merge_bases_many, remove_redundant_no_gen) pass the flag to\npreserve existing behavior. git merge-base (without --all) passes 0,\ntriggering the early exit.\n\nOn a 2.2M-commit merge-heavy monorepo with commit-graph:\n\n HEAD vs ~500: 5,229ms -> 24ms\n HEAD vs ~1000: 4,214ms -> 39ms\n HEAD vs ~5000: 3,799ms -> 46ms\n HEAD vs ~10000: 3,827ms -> 61ms\n\nSigned-off-by: Kristofer Karlsson \n---\n builtin/merge-base.c | 3 ++-\n commit-reach.c | 19 +++++++++++++++----\n commit-reach.h | 7 ++++++-\n t/t6600-test-reach.sh | 40 ++++++++++++++++++++++++++++++++++++++++\n 4 files changed, 63 insertions(+), 6 deletions(-)\n\ndiff --git a/builtin/merge-base.c b/builtin/merge-base.c\nindex 9b50b4660e..a87011c6cd 100644\n--- a/builtin/merge-base.c\n+++ b/builtin/merge-base.c\n@@ -11,11 +11,12 @@\n \n static int show_merge_base(struct commit **rev, size_t rev_nr, int show_all)\n {\n+\tenum merge_base_flags flags = show_all ? MERGE_BASE_FIND_ALL : 0;\n \tstruct commit_list *result = NULL, *r;\n \n \tif (repo_get_merge_bases_many_dirty(the_repository, rev[0],\n \t\t\t\t\t rev_nr - 1, rev + 1,\n-\t\t\t\t\t 0, &result) < 0) {\n+\t\t\t\t\t flags, &result) < 0) {\n \t\tcommit_list_free(result);\n \t\treturn -1;\n \t}\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 766ba1156a..5a52be90a6 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -97,6 +97,14 @@ static int paint_down_to_common(struct repository *r,\n \t\t\tif (!(commit->object.flags & RESULT)) {\n \t\t\t\tcommit->object.flags |= RESULT;\n \t\t\t\ttail = commit_list_append(commit, tail);\n+\t\t\t\t/*\n+\t\t\t\t * The queue is generation-ordered; no\n+\t\t\t\t * remaining common ancestor can be a\n+\t\t\t\t * descendant of this one.\n+\t\t\t\t */\n+\t\t\t\tif (!(mb_flags & MERGE_BASE_FIND_ALL) &&\n+\t\t\t\t generation < GENERATION_NUMBER_INFINITY)\n+\t\t\t\t\tbreak;\n \t\t\t}\n \t\t\t/* Mark parents of a found merge stale */\n \t\t\tflags |= STALE;\n@@ -247,7 +255,8 @@ static int remove_redundant_no_gen(struct repository *r,\n \t\t\t\tmin_generation = curr_generation;\n \t\t}\n \t\tif (paint_down_to_common(r, array[i], filled,\n-\t\t\t\t\t work, min_generation, 0, &common)) {\n+\t\t\t\t\t work, min_generation,\n+\t\t\t\t\t MERGE_BASE_FIND_ALL, &common)) {\n \t\t\tclear_commit_marks(array[i], all_flags);\n \t\t\tclear_commit_marks_many(filled, work, all_flags);\n \t\t\tcommit_list_free(common);\n@@ -477,7 +486,8 @@ int repo_get_merge_bases_many(struct repository *r,\n \t\t\t struct commit **twos,\n \t\t\t struct commit_list **result)\n {\n-\treturn get_merge_bases_many_0(r, one, n, twos, 1, 0, result);\n+\treturn get_merge_bases_many_0(r, one, n, twos, 1,\n+\t\t\t\t MERGE_BASE_FIND_ALL, result);\n }\n \n int repo_get_merge_bases_many_dirty(struct repository *r,\n@@ -495,7 +505,8 @@ int repo_get_merge_bases(struct repository *r,\n \t\t\t struct commit *two,\n \t\t\t struct commit_list **result)\n {\n-\treturn get_merge_bases_many_0(r, one, 1, &two, 1, 0, result);\n+\treturn get_merge_bases_many_0(r, one, 1, &two, 1,\n+\t\t\t\t MERGE_BASE_FIND_ALL, result);\n }\n \n /*\n@@ -540,7 +551,7 @@ int repo_in_merge_bases_many(struct repository *r, struct commit *commit,\n \tstruct commit_list *bases = NULL;\n \tint ret = 0, i;\n \ttimestamp_t generation, max_generation = GENERATION_NUMBER_ZERO;\n-\tenum merge_base_flags mb_flags = 0;\n+\tenum merge_base_flags mb_flags = MERGE_BASE_FIND_ALL;\n \n \tif (ignore_missing_commits)\n \t\tmb_flags |= MERGE_BASE_IGNORE_MISSING_COMMITS;\ndiff --git a/commit-reach.h b/commit-reach.h\nindex a3f2cd80eb..3f3a563d8a 100644\n--- a/commit-reach.h\n+++ b/commit-reach.h\n@@ -19,9 +19,14 @@ int repo_get_merge_bases_many(struct repository *r,\n \t\t\t struct commit_list **result);\n enum merge_base_flags {\n \tMERGE_BASE_IGNORE_MISSING_COMMITS = (1 << 0),\n+\tMERGE_BASE_FIND_ALL = (1 << 1),\n };\n \n-/* To be used only when object flags after this call no longer matter */\n+/*\n+ * To be used only when object flags after this call no longer matter.\n+ * Without MERGE_BASE_FIND_ALL and with generation numbers available,\n+ * returns after finding the first merge-base, skipping the STALE drain.\n+ */\n int repo_get_merge_bases_many_dirty(struct repository *r,\n \t\t\t\t struct commit *one, size_t n,\n \t\t\t\t struct commit **twos,\ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nindex dc0421ed2f..51c23b7683 100755\n--- a/t/t6600-test-reach.sh\n+++ b/t/t6600-test-reach.sh\n@@ -882,4 +882,44 @@ test_expect_success 'rev-list --maximal-only matches merge-base --independent' '\n \ttest_cmp expect.sorted actual.sorted\n '\n \n+# The following tests verify the early-exit optimisation in\n+# paint_down_to_common when merge-base is invoked without --all.\n+# Each test checks all four commit-graph configurations.\n+\n+merge_base_all_modes () {\n+\ttest_when_finished rm -rf .git/objects/info/commit-graph &&\n+\tgit merge-base \"$@\" >actual &&\n+\ttest_cmp expect actual &&\n+\tcp commit-graph-full .git/objects/info/commit-graph &&\n+\tgit merge-base \"$@\" >actual &&\n+\ttest_cmp expect actual &&\n+\tcp commit-graph-half .git/objects/info/commit-graph &&\n+\tgit merge-base \"$@\" >actual &&\n+\ttest_cmp expect actual &&\n+\tcp commit-graph-no-gdat .git/objects/info/commit-graph &&\n+\tgit merge-base \"$@\" >actual &&\n+\ttest_cmp expect actual\n+}\n+\n+test_expect_success 'merge-base without --all (unique base)' '\n+\tgit rev-parse commit-5-3 >expect &&\n+\tmerge_base_all_modes commit-5-7 commit-8-3\n+'\n+\n+test_expect_success 'merge-base without --all is one of --all results' '\n+\ttest_when_finished rm -rf .git/objects/info/commit-graph &&\n+\n+\tcp commit-graph-full .git/objects/info/commit-graph &&\n+\tgit merge-base --all commit-5-7 commit-4-8 commit-6-6 commit-8-3 >all &&\n+\tgit merge-base commit-5-7 commit-4-8 commit-6-6 commit-8-3 >single &&\n+\ttest_line_count = 1 single &&\n+\tgrep -F -f single all &&\n+\n+\tcp commit-graph-half .git/objects/info/commit-graph &&\n+\tgit merge-base --all commit-5-7 commit-4-8 commit-6-6 commit-8-3 >all &&\n+\tgit merge-base commit-5-7 commit-4-8 commit-6-6 commit-8-3 >single &&\n+\ttest_line_count = 1 single &&\n+\tgrep -F -f single all\n+'\n+\n test_done\n-- \ngitgitgadget\n"},{"id":"543103","messageId":"xmqqbjelqx2t.fsf@gitster.g","threadId":"65609","inReplyTo":"19f1605067e26c8e393c6c2e341844bcb3dc1b41.1778504352.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v4 2/2] commit-reach: early exit paint_down_to_common for single merge-base","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-05-12T00:40:42Z","receivedAt":"2026-05-12T00:40:45Z","isPatch":true,"body":"\"Kristofer Karlsson via GitGitGadget\" \nwrites:\n\n> From: Kristofer Karlsson \n>\n> Commits not in the commit-graph get GENERATION_NUMBER_INFINITY and\n> sort to the top of the priority queue. After those, commits with\n> finite generation numbers are popped in non-increasing order.\n> When MERGE_BASE_FIND_ALL is not set the first doubly-painted commit\n> with a finite generation is therefore a best merge-base: no commit\n> still in the queue can be a descendant of it. Skip the expensive\n> STALE drain in this case.\n>\n> Add MERGE_BASE_FIND_ALL to the merge_base_flags enum. Callers that\n> need every merge-base (repo_get_merge_bases_many, repo_get_merge_bases,\n> repo_in_merge_bases_many, remove_redundant_no_gen) pass the flag to\n> preserve existing behavior. git merge-base (without --all) passes 0,\n> triggering the early exit.\n>\n> On a 2.2M-commit merge-heavy monorepo with commit-graph:\n>\n> HEAD vs ~500: 5,229ms -> 24ms\n> HEAD vs ~1000: 4,214ms -> 39ms\n> HEAD vs ~5000: 3,799ms -> 46ms\n> HEAD vs ~10000: 3,827ms -> 61ms\n>\n> Signed-off-by: Kristofer Karlsson \n> ---\n> builtin/merge-base.c | 3 ++-\n> commit-reach.c | 19 +++++++++++++++----\n> commit-reach.h | 7 ++++++-\n> t/t6600-test-reach.sh | 40 ++++++++++++++++++++++++++++++++++++++++\n> 4 files changed, 63 insertions(+), 6 deletions(-)\n\nVery nicely done and well described.\n\n> diff --git a/builtin/merge-base.c b/builtin/merge-base.c\n> index 9b50b4660e..a87011c6cd 100644\n> --- a/builtin/merge-base.c\n> +++ b/builtin/merge-base.c\n> @@ -11,11 +11,12 @@\n> \n> static int show_merge_base(struct commit **rev, size_t rev_nr, int show_all)\n> {\n> +\tenum merge_base_flags flags = show_all ? MERGE_BASE_FIND_ALL : 0;\n\nCurious that only this variable, among 6 that this two-patch series\nintroduces for the type, is called \"flags\" while all others are\ncalled \"mb_flags\". No need to change it; the comment is mostly to\nshow I did read the two patches with reasonable attention to the\ndetail ;-).\n\nWill queue. Thanks.\n"},{"id":"543133","messageId":"CAL71e4MiOCx8OP-OjDoS1bPgDs-0yzC4v6tVsg9CLp2K-okQ0Q@mail.gmail.com","threadId":"65609","inReplyTo":"xmqqbjelqx2t.fsf@gitster.g","subject":"Re: [PATCH v4 2/2] commit-reach: early exit paint_down_to_common for single merge-base","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-05-12T05:16:05Z","receivedAt":"2026-05-12T05:16:17Z","isPatch":true,"body":"Thank you!\n\nAs for the difference in variable name, I will attribute it to a mix\nof oversight and personal preference to keep variable names short if\ntheir scope is very small (and longer names for things like fields or\nlarger scope).\nIn fact, I might have preferred flags instead of mb_flags within\npaint_down_to_common but it conflicted with the existing flags for the\ncommit so I had to differentiate them.\n\nThat said, I think it would also be fair to rename it to mb_flags everywhere.\n\nOn Tue, 12 May 2026 at 02:40, Junio C Hamano wrote:\n>\n> \"Kristofer Karlsson via GitGitGadget\" \n> writes:\n>\n> > From: Kristofer Karlsson \n> >\n> > Commits not in the commit-graph get GENERATION_NUMBER_INFINITY and\n> > sort to the top of the priority queue. After those, commits with\n> > finite generation numbers are popped in non-increasing order.\n> > When MERGE_BASE_FIND_ALL is not set the first doubly-painted commit\n> > with a finite generation is therefore a best merge-base: no commit\n> > still in the queue can be a descendant of it. Skip the expensive\n> > STALE drain in this case.\n> >\n> > Add MERGE_BASE_FIND_ALL to the merge_base_flags enum. Callers that\n> > need every merge-base (repo_get_merge_bases_many, repo_get_merge_bases,\n> > repo_in_merge_bases_many, remove_redundant_no_gen) pass the flag to\n> > preserve existing behavior. git merge-base (without --all) passes 0,\n> > triggering the early exit.\n> >\n> > On a 2.2M-commit merge-heavy monorepo with commit-graph:\n> >\n> > HEAD vs ~500: 5,229ms -> 24ms\n> > HEAD vs ~1000: 4,214ms -> 39ms\n> > HEAD vs ~5000: 3,799ms -> 46ms\n> > HEAD vs ~10000: 3,827ms -> 61ms\n> >\n> > Signed-off-by: Kristofer Karlsson \n> > ---\n> > builtin/merge-base.c | 3 ++-\n> > commit-reach.c | 19 +++++++++++++++----\n> > commit-reach.h | 7 ++++++-\n> > t/t6600-test-reach.sh | 40 ++++++++++++++++++++++++++++++++++++++++\n> > 4 files changed, 63 insertions(+), 6 deletions(-)\n>\n> Very nicely done and well described.\n>\n> > diff --git a/builtin/merge-base.c b/builtin/merge-base.c\n> > index 9b50b4660e..a87011c6cd 100644\n> > --- a/builtin/merge-base.c\n> > +++ b/builtin/merge-base.c\n> > @@ -11,11 +11,12 @@\n> >\n> > static int show_merge_base(struct commit **rev, size_t rev_nr, int show_all)\n> > {\n> > + enum merge_base_flags flags = show_all ? MERGE_BASE_FIND_ALL : 0;\n>\n> Curious that only this variable, among 6 that this two-patch series\n> introduces for the type, is called \"flags\" while all others are\n> called \"mb_flags\". No need to change it; the comment is mostly to\n> show I did read the two patches with reasonable attention to the\n> detail ;-).\n>\n> Will queue. Thanks.\n"}]}