From: Derrick Stolee Date: Wed, 24 Jun 2026 14:02:03 GMT Subject: Re: [PATCH v2 7/7] commit-reach: terminate merge-base walk when one paint side is exhausted Message-ID: <6b0d81e7-7617-4fb4-9e39-cdf8bc778837@gmail.com> In-Reply-To: On 6/24/2026 8:14 AM, Kristofer Karlsson via GitGitGadget wrote: > From: Kristofer Karlsson > > Add an early termination check to paint_down_to_common() using the > per-side counters introduced earlier. 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. Having this as the last patch is truly a nice climax moment for the patch series! > @@ -94,6 +94,9 @@ ends when one of the following conditions holds: > > 1. The queue is empty. > 2. The queue contains only stale entries. > + 3. Side exhaustion: no pure PARENT1 or pure PARENT2 commits > + remain in the queue, no pending merge-base candidates exist, > + and the walk has entered the finite-generation region. ...> +Side-exhaustion condition > +~~~~~~~~~~~~~~~~~~~~~~~~~ > +A new merge-base requires commits from both sides to meet. When one > +side's exclusive counter reaches zero and there are no pending > +merge-base candidates, no future traversal step can produce a new > +candidate. > + > +This optimization only activates in the finite-generation region > +where topological ordering holds. In that region, children are > +always visited before parents, so paint flags are final at visit > +time and an exhausted side cannot reappear. In the INFINITY region, > +commit-date ordering can violate this guarantee, so the check is > +skipped. > + And these doc updates inline make me happy. > Related documentation > --------------------- > > diff --git a/commit-reach.c b/commit-reach.c > index e0d9874f99..f79d0b64d6 100644 > --- a/commit-reach.c > +++ b/commit-reach.c > @@ -133,17 +133,30 @@ static void paint_queue_put(struct paint_state *state, > > static struct commit *paint_queue_get(struct paint_state *state) > { > - struct commit *commit; > + struct commit *commit = prio_queue_get(&state->queue); > > - if (!state->p1_count && !state->p2_count && > - !state->pending_merge_bases) > + if (!commit) > return NULL; I see how the previous implementation has a termination condition before calling prio_queue_get(), which is technically more efficient. It does make this initial diff a bit more complicated because we are moving the prio_queue_get() line. If the introduction of the method in patch 5/7 looked like this: +static struct commit *paint_queue_get(struct paint_state *state) +{ + struct commit *commit = prio_queue_get(&state->queue); + + if (!commit) + return NULL; + + if (!state->p1_count && !state->p2_count && + !state->pending_merge_bases) + return NULL; + + commit->object.flags &= ~ENQUEUED; + paint_count_update(state, commit->object.flags, -1); + return commit; +} Then this diff would look cleaner. (This is the nittiest of nitpicks so feel free to ignore if this doesn't bother you at all.) > - commit = prio_queue_get(&state->queue); > - if (commit) { > - commit->object.flags &= ~ENQUEUED; > - paint_count_update(state, commit->object.flags, -1); > + commit->object.flags &= ~ENQUEUED; > + > + if (!state->pending_merge_bases) { > + if (!state->p1_count && !state->p2_count) > + return NULL; > + /* > + * 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 ((!state->p1_count || !state->p2_count) && > + commit_graph_generation(commit) < GENERATION_NUMBER_INFINITY) > + return NULL; > } > + > + paint_count_update(state, commit->object.flags, -1); > return commit; > } I like how the crux of this implementation is entirely within paint_queue_get() now. > diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh > index c1109fb42f..03175befb3 100755 > --- a/t/t6600-test-reach.sh > +++ b/t/t6600-test-reach.sh > @@ -332,12 +332,12 @@ test_expect_success 'merge-base --all commit-walk steps' ' > cp commit-graph-full .git/objects/info/commit-graph && > GIT_TRACE2_EVENT="$(pwd)/trace-full.txt" \ > git merge-base --all commit-9-9 commit-9-1 >actual && > - test_trace2_data paint_down_to_common steps 80 + test_trace2_data paint_down_to_common steps 9 > cp commit-graph-half .git/objects/info/commit-graph && > GIT_TRACE2_EVENT="$(pwd)/trace-half.txt" \ > git merge-base --all commit-9-9 commit-9-1 >actual && > - test_trace2_data paint_down_to_common steps 81 + test_trace2_data paint_down_to_common steps 57 ' I love to see these steps change. If you take my suggestion to update more tests with these checks, then this diff will get bigger (but in a deserved way). Also, when I suggested that 'test_all_modes' creates the trace files on our behalf, I forgot to mention that this specific test that you added in patch 4/7 simplifies by running the merge-base check under 'test_all_modes' and then checking the trace2 data on the three well-known files afterwards. Thanks, -Stolee