From: Kristofer Karlsson Date: Sun, 14 Jun 2026 11:47:51 GMT Subject: Re: [RFC] commit-reach: terminate merge-base walk when one paint side is exhausted Message-ID: In-Reply-To: On Sun, 14 Jun 2026 at 06:32, Elijah Newren wrote: > 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