Re: [PATCH v8 00/10] commit-reach: terminate merge-base walk when one side is exhausted

On Tue, Aug 11, 2026 at 2:42 AM Kristofer Karlsson via GitGitGadget
<[email protected]> wrote:
> Changes since v7:
>
>  * Moved topo_ceiling from patch 10 into patch 8 where the side-exhaustion
>    gate first needs it, so V1_MAX saturation is handled correctly at every
>    commit in the series.
>
>  * Renamed "finite/INFINITY region" to "ordered/unordered region" in
>    documentation and in general tried to tighten up the documentation around
>    this.
>
>  * Added code comment explaining why termination conditions must be checked
>    before decrementing counters in paint_queue_get().
>
>  * Minor wording and formatting fixes in commit messages, test comments, and
>    the t6099 ASCII graph.

I am quite pleased with how this series has turned out.  Not only does
it provide nice speedups, I think the structure of the series is
particularly nicely set up in a way that helps guide the discovery of
the idea behind the optimization for others to read, documents and
tests everything logically and thoroughly, and was a pleasant read.

I brought up several issues in previous versions, and this round
addresses them all.

Reviewed-by: Elijah Newren <[email protected]>


But, I just have to comment on a few things individually...

>      @@ Documentation/technical/paint-down-to-common.adoc (new)
>       +
>       +When the commit-graph has generation numbers v1 and no
>       +generation floor is specified, topological ordering
>      -+(via generation numbers) is disabled.  Topological levels are
>      ++(via generation numbers) is disabled. Topological levels are
>       +correct but unbalanced -- ordering by such generation numbers
>       +can sometimes cause the walk to detour too far before finding
>      -+merge bases.  Commit-date ordering typically reaches them in
>      ++merge bases. Commit-date ordering typically reaches them in
>       +fewer steps -- see this change for more details:
>       +
>       +   091f4cf3 (commit: don't use generation numbers if not needed,
>      @@ Documentation/technical/paint-down-to-common.adoc (new)
>       +of both worlds and do not need this fallback.
>       +
>       +For v1, `paint_down_to_common()` falls back to pure commit-date
>      -+ordering via `compare_commits_by_commit_date`.  Because commit
>      ++ordering via `compare_commits_by_commit_date`. Because commit
>       +dates are not monotonic (clock skew, rebases, etc.), the queue
>       +may visit commits out of topological order.

Don't think for a second that I didn't notice you murdering these
double spaces.  You villain!  ;-)

>   3:  f857577e0c !  3:  6208bcf3b3 t6600: add test cases for side-exhaustion edge cases
>      @@ t/t6600-test-reach.sh: test_expect_success 'setup' '
>       + #   ps-T1   ps-T2
>       + #
>       + # where ps-T1=merge(ps-Z,ps-B), ps-T2=merge(ps-W,ps-B), so
>      -+ # merge-base(ps-T1,ps-T2) = ps-B. During the walk, ps-X transitions
>      ++ # merge-base(ps-T1,ps-T2) = ps-B.  During the walk, ps-X transitions
>       + # to (PARENT1|PARENT2) via ps-Z and ps-W before ps-B is dequeued;
>       + # then the STALE-walk from ps-B transitions ps-X to
>       + # (PARENT1|PARENT2|STALE).
>      @@ t/t6600-test-reach.sh: test_expect_success 'setup' '
>       +
>       + # Build a side topology that lives entirely outside the half
>       + # commit-graph and has non-monotonic commit dates, to exercise the
>      -+ # INFINITY-gate in paint_down_to_common. With both tips outside
>      ++ # INFINITY-gate in paint_down_to_common.  With both tips outside
>       + # the graph, generation is INFINITY and the queue falls back to
>       + # commit-date order, which here is non-monotonic.
>       + #
>      @@ t/t6600-test-reach.sh: test_expect_success 'get_merge_bases_many' '
>       +
>       +test_expect_success 'get_merge_bases_many:pending-stale' '
>       + # Exercises the (PARENT1|PARENT2) -> (...|STALE) transition path in
>      -+ # paint_down_to_common(). See the topology comment in the setup test.
>      ++ # paint_down_to_common().  See the topology comment in the setup test.
>       + cat >input <<-\EOF &&
>       + A:ps-T1
>       + X:ps-T2
>      @@ t/t6600-test-reach.sh: test_expect_success 'get_merge_bases_many' '
>       +'
>       +
>       +test_expect_success 'get_merge_bases_many:infinity-both-sides' '
>      -+ # Exercises the push-time INFINITY-gate in paint_down_to_common(). See
>      ++ # Exercises the push-time INFINITY-gate in paint_down_to_common().  See
>       + # the pi-* topology comment in the setup test.
>       + cat >input <<-\EOF &&
>       + A:pi-X

...and now you're just toying with us.  :-)

>   8:  391fa07783 !  8:  4a6603731c commit-reach: terminate merge-base walk when one paint side is exhausted
[...]
>  10:  b655b24dc0 ! 10:  677e25077c commit-reach: remove commit-date ordering fallback
[...]

Okay, my last two range-diff comments were just jokes, but more
serious now: I think you did a nice job on the re-splitting.  Thanks
for doing that!