On 6/29/2026 8:11 AM, Kristofer Karlsson wrote:

On Sun, 28 Jun 2026 at 17:16, Derrick Stolee [off-list ref] wrote:

quoted

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;

...> I traced the history of this fallback. 
...> 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.

Thanks for digging into the history of this fallback and catching it
during review!

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.

I agree with your reasoning, data-backed discovery, and the course of
action to fix this. I'm happy that you're able to close the loop on
this long-standing performance issue even with v1 generation numbers.

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

I don't see any other concerns here. You're right that if we were to
have a different mode that changes the priority-queue ordering, then
the side-exhaustion optimization cannot be trusted, but you will
remove this possibility.

It _may_ be worth mentioning this with a comment when initializing
the queue order for the paint_queue, because the use of the queue
requires topological ordering.

Thanks,
-Stolee