From: Kristofer Karlsson via GitGitGadget Date: Sat, 20 Jun 2026 10:36:56 GMT Subject: [PATCH/RFC 3/6] commit-reach: terminate merge-base walk when one paint side is exhausted Message-ID: In-Reply-To: From: Kristofer Karlsson 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 Helped-by: Elijah Newren Signed-off-by: Kristofer Karlsson --- 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