Re: [PATCH v2 7/7] commit-reach: terminate merge-base walk when one paint side is exhausted
- From
Derrick Stolee <stolee@gmail.com>
- Date
- Jun 24, 2026, 14:02 UTC
- Message-ID
- <6b0d81e7-7617-4fb4-9e39-cdf8bc778837@gmail.com>
- In-Reply-To
- <d84b932e5b078edc8255b6944ecb67fc1aa086b0.1782303254.git.gitgitgadget@gmail.com>
On 6/24/2026 8:14 AM, Kristofer Karlsson via GitGitGadget wrote:
Show 7 quoted lines
> From: Kristofer Karlsson <krka@spotify.com> > > 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!
Show 7 quoted lines
> @@ -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
Show 13 quoted lines
> +~~~~~~~~~~~~~~~~~~~~~~~~~ > +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.
Show 18 quoted lines
> 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.)
Show 25 quoted lines
> - 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.
Show 17 quoted lines
> 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 <trace-full.txt && > + test_trace2_data paint_down_to_common steps 9 <trace-full.txt && > > 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 <trace-half.txt > + test_trace2_data paint_down_to_common steps 57 <trace-half.txt > '
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