From: Derrick Stolee <stolee@gmail.com>
Date: Mon, 29 Jun 2026 12:40:22 GMT
Subject: Re: [PATCH v4 0/8] commit-reach: terminate merge-base walk when one side is exhausted
Message-ID: <5ef694a3-9164-4ab4-8835-136439f6d267@gmail.com>
In-Reply-To: <CAL71e4O8gTLm4WUcPF-ZbOYTuEzuNSVh0Qjf8ys1w4LVF9Hi8Q@mail.gmail.com>

On 6/29/2026 8:11 AM, Kristofer Karlsson wrote:
> 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;
...> 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