Re: [RFC] commit-reach: terminate merge-base walk when one paint side is exhausted
- From
Kristofer Karlsson <krka@spotify.com>
- Date
- Jun 14, 2026, 11:47 UTC
- Message-ID
- <CAL71e4Ps-2_0+uuZu43N9pFnXBemoAohPs_eyRJf8taXHJPAXQ@mail.gmail.com>
- In-Reply-To
- <CABPp-BGq8a-3ocJ+1HCgJutw1SBUvFg6YxtUamryfgEMx3qDYQ@mail.gmail.com>
On Sun, 14 Jun 2026 at 06:32, Elijah Newren <newren@gmail.com> wrote:
Show 6 quoted lines
> Wow...it appears this optimization was discovered by 3 separate > people in the last month. This optimization was implemented and > is live at GitHub...but it feels incomplete to me because my > version doesn't handle both sides having an infinite generation > number (it just falls back to the old algorithm when that > happens).
It is nice to know that multiple people converged on the same idea independently -- that gives me a lot of confidence that we are exploiting a real and useful property of the graph/walk structure.
> I uploaded my version at > https://github.com/gitgitgadget/git/pull/2150.
I uploaded mine at https://github.com/gitgitgadget/git/pull/2149 (draft, still iterating on the series).
I realize this is getting into implementation details before the idea itself has been discussed on the list. I am happy to wait with a formal patch submission until there is more consensus on the approach -- but since you shared your implementation, I wanted to compare notes while it is fresh.
I integrated your new t6600 test cases into my branch -- thanks! They exercise important edge cases that my original tests missed. I also extended the perf test to cover the case where both tips are outside the commit-graph.
After looking at your implementation, I also moved from a max-pointer scheme to per-side counters. We ended up with slightly different implementations, but they are tracking the same underlying condition: whether either paint side still has non-stale exclusive commits remaining.
The main behavioral difference is handling of commits outside the commit-graph. Your version disables the optimization once both sides have touched such commits, while mine only enables the break after the walk reaches the finite-generation region. This still allows the optimization to fire when both tips start outside the graph, as soon as the walk crosses into commits covered by the commit-graph.
> Do you want to take this over, rebase it, and extend to the > infinite generation number case? Or do you want me to rebase > and see it through after my vacation? Or some other mixture?
I am happy to keep working on this -- starting from either your branch or mine, or some hybrid. I do not have a strong preference for which version it would be based on, but if either of them lands I would be happy. Enjoy your vacation!
Thanks, Kristofer