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

[PATCH v4 2/2] commit-reach: early exit paint_down_to_common for single merge-base

From
Kristofer Karlsson via GitGitGadget <gitgitgadget@gmail.com>
Date
May 11, 2026, 12:59 UTC
Message-ID
<19f1605067e26c8e393c6c2e341844bcb3dc1b41.1778504352.git.gitgitgadget@gmail.com>
In-Reply-To
<pull.2109.v4.git.1778504352.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>

Commits not in the commit-graph get GENERATION_NUMBER_INFINITY and sort to the top of the priority queue. After those, commits with finite generation numbers are popped in non-increasing order. When MERGE_BASE_FIND_ALL is not set the first doubly-painted commit with a finite generation is therefore a best merge-base: no commit still in the queue can be a descendant of it. Skip the expensive STALE drain in this case.

Add MERGE_BASE_FIND_ALL to the merge_base_flags enum. Callers that need every merge-base (repo_get_merge_bases_many, repo_get_merge_bases, repo_in_merge_bases_many, remove_redundant_no_gen) pass the flag to preserve existing behavior. git merge-base (without --all) passes 0, triggering the early exit.

On a 2.2M-commit merge-heavy monorepo with commit-graph:
  HEAD vs ~500:   5,229ms -> 24ms
  HEAD vs ~1000:  4,214ms -> 39ms
  HEAD vs ~5000:  3,799ms -> 46ms
  HEAD vs ~10000: 3,827ms -> 61ms
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
 builtin/merge-base.c  |  3 ++-
 commit-reach.c        | 19 +++++++++++++++----
 commit-reach.h        |  7 ++++++-
 t/t6600-test-reach.sh | 40 ++++++++++++++++++++++++++++++++++++++++
 4 files changed, 63 insertions(+), 6 deletions(-)
diff --git a/builtin/merge-base.c b/builtin/merge-base.c
index 9b50b4660e..a87011c6cd 100644
--- a/builtin/merge-base.c
+++ b/builtin/merge-base.c
@@ -11,11 +11,12 @@
 
 static int show_merge_base(struct commit **rev, size_t rev_nr, int show_all)
 {
+	enum merge_base_flags flags = show_all ? MERGE_BASE_FIND_ALL : 0;
 	struct commit_list *result = NULL, *r;
 
 	if (repo_get_merge_bases_many_dirty(the_repository, rev[0],
 					    rev_nr - 1, rev + 1,
-					    0, &result) < 0) {
+					    flags, &result) < 0) {
 		commit_list_free(result);
 		return -1;
 	}
diff --git a/commit-reach.c b/commit-reach.c
index 766ba1156a..5a52be90a6 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -97,6 +97,14 @@ static int paint_down_to_common(struct repository *r,
 			if (!(commit->object.flags & RESULT)) {
 				commit->object.flags |= RESULT;
 				tail = commit_list_append(commit, tail);
+				/*
+				 * The queue is generation-ordered; no
+				 * remaining common ancestor can be a
+				 * descendant of this one.
+				 */
+				if (!(mb_flags & MERGE_BASE_FIND_ALL) &&
+				    generation < GENERATION_NUMBER_INFINITY)
+					break;
 			}
 			/* Mark parents of a found merge stale */
 			flags |= STALE;
@@ -247,7 +255,8 @@ static int remove_redundant_no_gen(struct repository *r,
 				min_generation = curr_generation;
 		}
 		if (paint_down_to_common(r, array[i], filled,
-					 work, min_generation, 0, &common)) {
+					 work, min_generation,
+					 MERGE_BASE_FIND_ALL, &common)) {
 			clear_commit_marks(array[i], all_flags);
 			clear_commit_marks_many(filled, work, all_flags);
 			commit_list_free(common);
@@ -477,7 +486,8 @@ int repo_get_merge_bases_many(struct repository *r,
 			      struct commit **twos,
 			      struct commit_list **result)
 {
-	return get_merge_bases_many_0(r, one, n, twos, 1, 0, result);
+	return get_merge_bases_many_0(r, one, n, twos, 1,
+				     MERGE_BASE_FIND_ALL, result);
 }
 
 int repo_get_merge_bases_many_dirty(struct repository *r,
@@ -495,7 +505,8 @@ int repo_get_merge_bases(struct repository *r,
 			 struct commit *two,
 			 struct commit_list **result)
 {
-	return get_merge_bases_many_0(r, one, 1, &two, 1, 0, result);
+	return get_merge_bases_many_0(r, one, 1, &two, 1,
+				     MERGE_BASE_FIND_ALL, result);
 }
 
 /*
@@ -540,7 +551,7 @@ int repo_in_merge_bases_many(struct repository *r, struct commit *commit,
 	struct commit_list *bases = NULL;
 	int ret = 0, i;
 	timestamp_t generation, max_generation = GENERATION_NUMBER_ZERO;
-	enum merge_base_flags mb_flags = 0;
+	enum merge_base_flags mb_flags = MERGE_BASE_FIND_ALL;
 
 	if (ignore_missing_commits)
 		mb_flags |= MERGE_BASE_IGNORE_MISSING_COMMITS;
diff --git a/commit-reach.h b/commit-reach.h
index a3f2cd80eb..3f3a563d8a 100644
--- a/commit-reach.h
+++ b/commit-reach.h
@@ -19,9 +19,14 @@ int repo_get_merge_bases_many(struct repository *r,
 			      struct commit_list **result);
 enum merge_base_flags {
 	MERGE_BASE_IGNORE_MISSING_COMMITS = (1 << 0),
+	MERGE_BASE_FIND_ALL               = (1 << 1),
 };
 
-/* To be used only when object flags after this call no longer matter */
+/*
+ * To be used only when object flags after this call no longer matter.
+ * Without MERGE_BASE_FIND_ALL and with generation numbers available,
+ * returns after finding the first merge-base, skipping the STALE drain.
+ */
 int repo_get_merge_bases_many_dirty(struct repository *r,
 				    struct commit *one, size_t n,
 				    struct commit **twos,
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index dc0421ed2f..51c23b7683 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -882,4 +882,44 @@ test_expect_success 'rev-list --maximal-only matches merge-base --independent' '
 	test_cmp expect.sorted actual.sorted
 '
 
+# The following tests verify the early-exit optimisation in
+# paint_down_to_common when merge-base is invoked without --all.
+# Each test checks all four commit-graph configurations.
+
+merge_base_all_modes () {
+	test_when_finished rm -rf .git/objects/info/commit-graph &&
+	git merge-base "$@" >actual &&
+	test_cmp expect actual &&
+	cp commit-graph-full .git/objects/info/commit-graph &&
+	git merge-base "$@" >actual &&
+	test_cmp expect actual &&
+	cp commit-graph-half .git/objects/info/commit-graph &&
+	git merge-base "$@" >actual &&
+	test_cmp expect actual &&
+	cp commit-graph-no-gdat .git/objects/info/commit-graph &&
+	git merge-base "$@" >actual &&
+	test_cmp expect actual
+}
+
+test_expect_success 'merge-base without --all (unique base)' '
+	git rev-parse commit-5-3 >expect &&
+	merge_base_all_modes commit-5-7 commit-8-3
+'
+
+test_expect_success 'merge-base without --all is one of --all results' '
+	test_when_finished rm -rf .git/objects/info/commit-graph &&
+
+	cp commit-graph-full .git/objects/info/commit-graph &&
+	git merge-base --all commit-5-7 commit-4-8 commit-6-6 commit-8-3 >all &&
+	git merge-base commit-5-7 commit-4-8 commit-6-6 commit-8-3 >single &&
+	test_line_count = 1 single &&
+	grep -F -f single all &&
+
+	cp commit-graph-half .git/objects/info/commit-graph &&
+	git merge-base --all commit-5-7 commit-4-8 commit-6-6 commit-8-3 >all &&
+	git merge-base commit-5-7 commit-4-8 commit-6-6 commit-8-3 >single &&
+	test_line_count = 1 single &&
+	grep -F -f single all
+'
+
 test_done
-- 
gitgitgadget
Previous: Kristofer Karlsson via GitGitGadgetNext: Junio C Hamano
Message 9 of 11 in “commit-reach: early exit paint_down_to_common for single merge-base”
  1. commit-reach: early exit paint_down_to_common for single merge-baseKristofer Karlsson via GitGitGadget, May 8, 2026
  2. Junio C HamanoMay 11, 2026
  3. commit-reach: early exit paint_down_to_common for single merge-baseKristofer Karlsson via GitGitGadget, May 11, 2026
  4. Patrick SteinhardtMay 11, 2026
  5. commit-reach: early exit paint_down_to_common for single merge-baseKristofer Karlsson via GitGitGadget, May 11, 2026
  6. Patrick SteinhardtMay 11, 2026
  7. 0/2 [RFC] commit-reach: skip STALE drain when only one merge-base neededKristofer Karlsson via GitGitGadget, May 11, 2026
  8. 1/2 commit-reach: introduce merge_base_flags enumKristofer Karlsson via GitGitGadget, May 11, 2026
  9. 2/2 commit-reach: early exit paint_down_to_common for single merge-baseKristofer Karlsson via GitGitGadget, May 11, 2026
  10. Junio C HamanoMay 12, 2026
  11. Kristofer KarlssonMay 12, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.