[PATCH/RFC 3/6] commit-reach: terminate merge-base walk when one paint side is exhausted

From: Kristofer Karlsson via GitGitGadget <gitgitgadget@gmail.com>
Date: Jun 20, 2026, 10:36 UTC
Message-ID: <ed12a5cb5b76925cff08d2ab61efeda382b4477a.1781951820.git.gitgitgadget@gmail.com>
In-Reply-To: <pull.2149.git.1781951820.gitgitgadget@gmail.com>

From: Kristofer Karlsson <krka@spotify.com>

Add an early termination check to paint_down_to_common() using the per-side counters introduced in the previous commit. Once the walk enters the finite-generation region, terminate early when one side's exclusive count drops to zero -- no new merge-base can form without both paint sides meeting.

The check also waits for pending_merge_bases to reach zero, ensuring all merge-base candidates have been popped and recorded before exiting.

The INFINITY gate ensures correctness: commits without a commit-graph entry have GENERATION_NUMBER_INFINITY and are ordered by commit date, which is not topologically reliable. The optimization only fires once the walk enters the finite-generation region where ordering guarantees hold.

On large repositories with commit-graph, this yields 100-1000x speedups for merge-base queries where one side (e.g. a PR branch) is much smaller than the other.

Helped-by: Derrick Stolee <stolee@gmail.com>
Helped-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
 commit-reach.c | 13 +++++++++++++
 1 file changed, 13 insertions(+)

diff --git a/commit-reach.c b/commit-reach.c
index ba1e896f0f..fcd1ad0167 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -201,6 +201,19 @@ static int paint_down_to_common(struct repository *r,
 		if (queue.p1_count + queue.p2_count +
 		    queue.pending_merge_bases == 0)
 			break;
+
+		/*
+		 * Side exhaustion: a new merge-base can only form
+		 * when both PARENT1-only and PARENT2-only commits
+		 * remain in the queue.  In the finite-generation
+		 * region the queue is ordered topologically, so
+		 * no future step can add paint to visited commits
+		 * and an exhausted side cannot reappear.
+		 */
+		if (generation < GENERATION_NUMBER_INFINITY &&
+		    queue.pending_merge_bases == 0 &&
+		    (queue.p1_count == 0 || queue.p2_count == 0))
+			break;
 	}
 
 	clear_prio_queue(&queue.pq);

-- 
gitgitgadget