Re: [RFC] commit-reach: terminate merge-base walk when one paint side is exhausted
- From
Elijah Newren <newren@gmail.com>
- Date
- Jun 14, 2026, 04:32 UTC
- Message-ID
- <CABPp-BGq8a-3ocJ+1HCgJutw1SBUvFg6YxtUamryfgEMx3qDYQ@mail.gmail.com>
- In-Reply-To
- <CAL71e4Mp7ewv0UGS8j=iTq6quyxLXzrr0uNDbWR8JKaOsTSVyA@mail.gmail.com>
On Fri, Jun 12, 2026 at 4:18 AM Kristofer Karlsson <krka@spotify.com> wrote:
Show 69 quoted lines
> > Hi! I previously sent a patch[1] to optimize paint_down_to_common > for the single merge-base case. I believe I have found a stronger > optimization, but before sending a patch I wanted to discuss the > correctness argument. > > The main problem to solve is that computing merge-bases is slow today > in some scenarios, especially large monorepos with complex graphs. > This affects multiple operations, including merge-base and merge-tree. > > The previous patch improved it for the special case of the > merge-base being part of the commit-graph and the caller only > needing to know about one merge-base. > > I have an idea to make it faster for fetching all merge-bases for > common flows in large repos, as long as the commit graph is > reasonably up to date. > > The key part is the exit condition in paint_down_to_common. > Instead of waiting for the queue to only contain stale entries, > it is enough to wait for one of the sides to be exhausted, > i.e. side 1 is exhausted if no more commits exist in the > traversal queue flagged with only PARENT1. For example, if > the two sides are origin/HEAD and a small PR branch, the PR > branch will quickly become exhausted at the merge-base, while > the main side will continue. > > Now you may ask: why is that a safe condition? > > The traversal in paint_down_to_common has two logical phases > due to the priority queue ordering: > > 1. Process all commits with infinite generation numbers. > This includes all commits when there is no commit-graph. > 2. Process all commits with finite generation numbers. > > These happen in strict order -- all INFINITY commits are popped > before any finite-generation commit. > > The optimization only applies after the walk enters the second phase. > In the first phase, the traversal behaves exactly as today > and uses the existing termination condition. > > In the second phase, traversal follows strict topological > order -- descendants are processed before ancestors. Paint flags > propagate from each processed commit to its parents, which have > strictly lower generation and are therefore not yet examined. > > A new merge-base candidate can only form when a PARENT1-only path > meets a PARENT2-only path. Once a commit acquires both paint flags > in this phase, any descendant carrying both paint flags would > already have been processed. > > Once one side is exhausted from the queue, no new meeting between > pure sides can occur. Any commit that subsequently acquires both > paint flags must inherit them from a commit that already had both > flags -- it is deeper in the graph and cannot affect the final > merge-base set. We can stop. > > On a large monorepo with previously expensive merge-base and > merge-tree queries, I observed speedups ranging from roughly 300x > to 1000x. The nice thing is that this works for merge-base --all > and every internal caller of paint_down_to_common -- we no longer > have to restrict the optimization to finding just the first merge-base. > > Does the correctness argument above hold? > > Happy to come back with a patch later if the logic holds and the > overall approach is wanted.
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). I had meant to fix that and then upstream it, but other fires have been keeping me busy. And I'm about to go on vacation on Monday.
I uploaded my version at https://github.com/gitgitgadget/git/pull/2150. Unfortunately, it conflicts with your recent good work in the area due to being based on a version of main from about a month ago.
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?