From: Kristofer Karlsson Date: Sat, 13 Jun 2026 09:42:08 GMT Subject: Re: [RFC] commit-reach: terminate merge-base walk when one paint side is exhausted Message-ID: In-Reply-To: <8c06cc48-d036-4d01-98d3-e94b5edb389c@gmail.com> On Fri, 12 Jun 2026 at 17:48, Derrick Stolee wrote: > Suppose developers are merging into 'main' frequently. On occasion, > the tip of 'main' is merged into a new 'release' branch. Thus, the > first-parent history of 'release' is long and completely separate > from the commit history of 'main'. To reach the queue_has_nonstale() > exit condition, we'd need to walk the entire history. > > However, if we focus on the single-side condition you are proposing, > we can stop walking once everything in the queue that is reachable > form 'main' is also reachable from that top merge-base. Exactly - I have a similar example and a minimal reproduction idea for the current problem: Consider two graph shapes for `git merge-base H B`: Shape 1 (fast): Shape 2 (slow): H B H B | | | | A | A | \ / / \ / C X C | | | ... \ / D | ... In shape 2, A is a merge commit with parents C and X. X branches off from an older commit D on the main line and gets merged back. This is extremely common in repositories that use merge commits (monorepos, release-branch workflows). In both shapes, C is the only merge-base. But in shape 2, the walk through X's ancestry is P1-only: STALE propagates through C's ancestors but never reaches D's lineage. The max_nonstale pointer stays alive until D's entire history is drained. On a 2.5M-commit monorepo, we measured this directly by creating test commits with `git commit-tree`: Shape 1: 10ms Shape 2: 4.85s Both running with stock git 2.53 and both found the merge-base C. A single merge bypass to old history is enough to force the walk through the entire graph. In practice, master's history contains many such merge commits, which is why we consistently see 5-7s wall-clock time for merge-base queries. With per-side tracking, the P2 side exhausts immediately after C is found (B's only parent C has been processed), and the walk terminates in 6ms regardless of how deep the P1-only bypass goes. As you noted, the "release branch" shape is another case where this helps -- the main side exhausts at the merge-base while release's first-parent history is entirely one-sided. > But I think your single-sided approach is a better way to get the gains > that you want. I think that case is much more likely to occur. Thanks for working through this with me. I started thinking the idea itself is not strong enough on its own, so I have attempted to write a more formal correctness proof covering the drain phase, result exactness, and the INFINITY/finite region boundary. It is too long to inline (~2000 words) and the high level argument is already in this thread, so linking it here instead - I consider it optional reading, since it's not really light reading and we can likely make progress without it: https://gist.github.com/spkrka/621695aa464df2a8c1837e9abca822e3 The proof assumes finite generation numbers (commit-graph present). The side-exhaustion check is guarded by generation < INFINITY in the implementation. I am far from an expert in logical proofs though, so this may not be strong enough to be useful, but it may be possible to fix it - or it will uncover some flaw that invalidates the idea. > Thanks for your persistence in working on this through my > misunderstanding. > To be fair, I think this was more a case of me not being fully able to explain the idea with enough precision initially, so I appreciate getting the opportunity to refine it with your very useful example case. Thanks, Kristofer