Re: [PATCH v7 08/10] commit-reach: terminate merge-base walk when one paint side is exhausted
- From
Elijah Newren <newren@gmail.com>
- Date
- Aug 7, 2026, 03:02 UTC
- Message-ID
- <CABPp-BE=MB-j2HOnZEFaf5wrdBz329+J1AKwyRWFwjP-5iao-w@mail.gmail.com>
- In-Reply-To
- <391fa07783a7819a60c0b0c2a3ea86fb13c95079.1786013982.git.gitgitgadget@gmail.com>
On Thu, Aug 6, 2026 at 4:05 AM Kristofer Karlsson via GitGitGadget <gitgitgadget@gmail.com> wrote:
Show 8 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.
...this is the insight behind this optimization, which the previous patch set up so nicely.
Show 9 quoted lines
> The check also waits for pending_merge_bases to reach zero, ensuring > all merge-base candidates have been dequeued 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.
What about GENERATION_NUMBER_V1_MAX ?
Show 22 quoted lines
> > Step counts measured with trace2 on git.git with commit-graph: > > merge-base --all v2.0.0 v2.55.0-rc1: > before: 72264 steps after: 44589 steps > > merge-base --all v2.55.0-rc1 v2.55.0-rc1~5: > before: 110 steps after: 7 steps > > Helped-by: Derrick Stolee <stolee@gmail.com> > Helped-by: Elijah Newren <newren@gmail.com> > Signed-off-by: Kristofer Karlsson <krka@spotify.com> > --- > .../technical/paint-down-to-common.adoc | 23 ++++++++++++++++++- > commit-reach.c | 18 ++++++++++++--- > t/t6600-test-reach.sh | 4 ++-- > 3 files changed, 39 insertions(+), 6 deletions(-) > > diff --git a/Documentation/technical/paint-down-to-common.adoc b/Documentation/technical/paint-down-to-common.adoc > index 37fa6f93c1..7c93f7e676 100644 > --- a/Documentation/technical/paint-down-to-common.adoc > +++ b/Documentation/technical/paint-down-to-common.adoc
[...]
> + 5. 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.
"finite" or "small enough" ?
Show 8 quoted lines
> +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
"finite-generation region" -> "reliably-ordered region" , or something like that?
Show 5 quoted lines
> +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.
"In the INFINITY region" -> "outside the reliably-ordered region" ?
Show 34 quoted lines
> Related documentation
> ---------------------
>
> diff --git a/commit-reach.c b/commit-reach.c
> index a62b5e4624..e03505b535 100644
> --- a/commit-reach.c
> +++ b/commit-reach.c
> @@ -132,6 +132,10 @@ static void paint_queue_put(struct paint_state *state,
> }
> }
>
> +/*
> + * Dequeue the next commit for the paint walk, or return NULL when
> + * no more merge bases can be discovered.
> + */
> static struct commit *paint_queue_get(struct paint_state *state)
> {
> struct commit *commit = prio_queue_get(&state->queue);
> @@ -141,9 +145,17 @@ static struct commit *paint_queue_get(struct paint_state *state)
>
> commit->object.flags &= ~ENQUEUED;
>
> - if (!state->parent1_count && !state->parent2_count &&
> - !state->mb_candidate_count)
> - return NULL;
> + if (!state->mb_candidate_count) {
> + /* only stale entries remain */
> + if (!state->parent1_count && !state->parent2_count)
> + return NULL;
> +
> + /* one side is exhausted */
> + if ((!state->parent1_count || !state->parent2_count) &&
> + state->gen_ordered &&
> + commit_graph_generation(commit) < GENERATION_NUMBER_INFINITY)At this point in the series, Documentation/technical/paint-down-to-common.adoc does point out the GENERATION_NUMBER_V1_MAX issue in one of the paragraphs; it's kind of glossed over in other later paragraphs (as I highlighted above), but there's a clear incongruence at this point in the series. I'm guessing you're going to fix that up in the next two patches, but the splitting feels a bit off.
Show 29 quoted lines
> + return NULL; > + } > > paint_count_update(state, commit->object.flags, -1); > return commit; > diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh > index f9895f5fd7..6bf17cb7b6 100755 > --- a/t/t6600-test-reach.sh > +++ b/t/t6600-test-reach.sh > @@ -297,7 +297,7 @@ test_expect_success 'in_merge_bases_many:self' ' > EOF > echo "in_merge_bases_many(A,X):1" >expect && > test_all_modes in_merge_bases_many && > - test_paint_down_steps 45 2 25 3 > + test_paint_down_steps 45 1 25 1 > ' > > test_expect_success 'is_descendant_of:hit' ' > @@ -414,7 +414,7 @@ test_expect_success 'merge-base --all commit-walk steps' ' > >input && > git rev-parse commit-9-1 >expect && > run_all_modes git merge-base --all commit-9-9 commit-9-1 && > - test_paint_down_steps 81 80 81 81 > + test_paint_down_steps 81 9 57 81 > ' > > test_expect_success 'merge-base --all with clock skew (side-exhaustion)' ' > -- > gitgitgadget
Other than the GENERATION_NUMBER_V1_MAX stuff, this commit looks good. There may be a way to reword things to allow the current split, but I'll keep reading to the next patches.