Re: [PATCH v7 08/10] commit-reach: terminate merge-base walk when one paint side is exhausted

On Thu, Aug 6, 2026 at 4:05 AM Kristofer Karlsson via GitGitGadget
<[email protected]> wrote:
>
> From: Kristofer Karlsson <[email protected]>
>
> 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.

> 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 ?

>
> 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 <[email protected]>
> Helped-by: Elijah Newren <[email protected]>
> Signed-off-by: Kristofer Karlsson <[email protected]>
> ---
>  .../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" ?

> +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?

> +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" ?

>  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.

> +                       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.