Re: [PATCH v4 0/8] commit-reach: terminate merge-base walk when one side is exhausted

On Sun, 28 Jun 2026 at 17:16, Derrick Stolee <stolee@gmail.com> wrote:

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