From: Kristofer Karlsson <krka@spotify.com>
Date: Mon, 29 Jun 2026 12:11:51 GMT
Subject: Re: [PATCH v4 0/8] commit-reach: terminate merge-base walk when one side is exhausted
Message-ID: <CAL71e4O8gTLm4WUcPF-ZbOYTuEzuNSVh0Qjf8ys1w4LVF9Hi8Q@mail.gmail.com>
In-Reply-To: <48bfdb11-2624-4aa6-8fbd-d3f894c33bcc@gmail.com>

On Sun, 28 Jun 2026 at 17:16, Derrick Stolee <stolee@gmail.com> wrote:
>
> I reviewed the v3 discussion, the range-diff, and reread patch 8. I think
> that this version is good to go.

Thanks for all your reviews and feedback. However, I found one more
problem that needs to be resolved before this is good to go.

paint_down_to_common() has this fallback:

    if (!min_generation && !corrected_commit_dates_enabled(r))
        queue.pq.compare = compare_commits_by_commit_date;

When this fires, the queue uses commit-date ordering instead of
generation ordering. The side-exhaustion optimization and my older
patch for !FIND_ALL early exit both check for reaching the finite
generation, but with date ordering, that check is wrong --
a commit can have a finite topo level (it is in a v1 commit graph)
while the queue is not ordered by generation. This unfortunately
means there is a regression for the !FIND_ALL optimization that
I should fix before 2.55 is final. I will send a small patch for
that separately: add tests that demonstrate the problem, and disable
the !FIND_ALL early exit when generation ordering is not active.

I traced the history of this fallback. The queue was switched from
date ordering to generation ordering in 3afc679b (2018-05). Then in
091f4cf3 (2018-08) you added the date fallback after finding that v1
topo levels caused "git merge-base v4.8 v4.9" on the Linux kernel to
walk 636k commits instead of 167k -- a side branch with a low topo
level stayed in the queue behind a long chain, preventing early STALE
propagation. Later, 8d00d7c3 (2021-01) tightened the fallback to
only fire without corrected commit dates, since v2 does not have the
regression.

The problem that 091f4cf3 addresses looks closely related to what
side-exhaustion solves: the walk goes deep into a subgraph where
only one paint side has presence. With side-exhaustion, the walk
terminates as soon as one paint side is exhausted from the queue,
so the deep walk never happens regardless of queue ordering.

I benchmarked "git merge-base --all v4.8 v4.9" on the Linux kernel
(the same case from 091f4cf3) with three configurations:

                    master (--all)    side-exhaust (--all, gen ordering)
  no graph:           3212 ms            3268 ms
  v1 graph:            188 ms              17 ms
  v2 graph:            227 ms              17 ms

With side-exhaustion, the v1 case no longer shows a regression
compared to the date fallback -- if anything, it is slightly faster
since the walk terminates earlier. This suggests that the workaround
from 091f4cf3 may no longer be needed when side-exhaustion is
present.

It is also worth noting that commitGraph.generationVersion has
defaulted to 2 since 2021, so the v1 fallback path is rarely
exercised in practice. Any commit-graph rewrite produces v2 data,
and only repos that have not rewritten their commit graph in over
four years would still have v1-only data.

If that reasoning holds, the fix for v5 would be to remove the date
fallback entirely, always using compare_commits_by_gen_then_commit_date.
This would:

 1. Fix the bug (finite generation always means generation-ordered
    queue).
 2. Remove corrected_commit_dates_enabled() which has no other
    callers.

The alternative would be to keep the fallback and disable the
optimizations that depend on ordering (via a flag like
paint_state.gen_ordered).

Do you see any cases I might be missing where removing the fallback
could cause problems?

Thanks,
Kristofer