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.

Thanks, Kristofer

[1] https://lore.kernel.org/git/pull.2109.v4.git.1778504352.gitgitgadget@gmail.com/

On 6/12/2026 7:15 AM, Kristofer Karlsson wrote:

Generally, you'd replace the queue_has_nonstale() condition with a more generic queue_can_halt() condition.

This would mean that queue_can_halt() would need to know the following:

1. If we peek at the top of the queue, is that a commit with
   infinite generation number? If so, then we can only use
   queue_has_nonstale().

2. Otherwise, we know that all commits in the queue are ordered
   topologically and can use a different, faster check. To start,
   we need to keep going as long as at least one commit has only
   one side

The important thing to realize at this point is that commits in the queue have received flags from their children (children were walked topologically and "push" flags to their parents).

The STALE bit is pushed from commits that have bits for both sides of the merge. This isn't something that we can learn from just walking each side: we need some amount of walking within the intersection.

This doesn't matter if we are looking for a single merge base, but when we want the full set of independent merge bases, then the STALE bit becomes very important.

I think that it doesn't work when trying to get all merge bases. It requires

   A    X
  /| __/|
 | |/   |
 | B    |
 | |    |
..........
 | | __/
  \|/
   C

In this example, B can reach C through some long list of commits. This makes B (and X) have much higher generation number than C. After exhausting both sides of A...X, we have B and C in the queue with both side bits and neither are stale. But we need to walk from B to C to discover that C should be stale.

You are identifying a point where optimizations are possible, based on your measurements of the time spent in this walk waiting for queue_has_nonstale() to end the loop. Specifically, the cost of using a BFS approach is costing time.

One place that I would recommend here is to take the work you are doing to investigate the behavior of tips_reachable_from_bases() or get_reachable_subset() to see if we can use a DFS-based approach _in this case_ where we have exhausted both side and are only caring about the STALE bit checking these cases.

Remember that the DFS idea only helps in the case where we find a path between commits (B to C in this case) without walking all of the commits above the minimum generation (generation of C). In an alternate case where B and C are truly independent, this would not save any time. But these "they are mutually unreachable" cases always require walking the full set based on the generation number. The good news is that the vast majority of cases do not actually have multiple independent merge bases, so there is potential here.

Thanks, -Stolee

On 6/12/2026 2:52 PM, Derrick Stolee wrote:

Thank you for the quick and detailed response and your counterexample graph is exactly the right thing to worry about.

I think your response helped me identify a mistake in how I described the halt condition.

The required condition must then not be simply "one side exhausted". The walk must also continue while non-stale P1|P2 commits remain in the queue, since those still need STALE propagation - they are still merge-base candidates.

So the actual halt condition would be:

    no non-stale P1|P2 candidates in the queue
    AND (no pure-P1 OR no pure-P2)

In your example, B and C are both non-stale P1|P2 commits after both sides are exhausted. Therefore the walk continues. When B is processed it propagates STALE toward C through the d-chain, and because the finite-generation region is processed in descending generation order, that propagation reaches C before C is popped.

If this reasoning is correct, then the walk only terminates after merge-base candidates have either been processed or marked STALE, and the counterexample should produce [B] rather than [B, C].

Thanks, Kristofer

On 6/12/2026 10:32 AM, Kristofer Karlsson wrote:

And since STALE is added only after both P1 and P2 bits, the two conditions are identical to how queue_has_nonstale() terminates the loop.

That's the correct distinction: we need the set [B] and not [B,C] but we need to discover that B can reach C to remove it from the result set.

I think there is potential merit in "switching walk modes" to DFS when all queued commits have both P1 and P2, but it comes with a lot of complications. So tread carefully if you go down this road.

Thanks, -Stolee

On Fri, 12 Jun 2026 at 17:04, Derrick Stolee <stolee@gmail.com> wrote:

No, I think this part is different. I can demonstrate with an example queue state: [P1, stale, P1, stale, stale] With the old code, the non-stale tracker would consider this to be non-stale since it still has two P1 commits to process. My new approach would instead consider that a valid halt state - we can't find any new merge-bases at that point.

Yes, and I think that part works since we visit them in generational order, so B can invalidate C before C is reached.

On the DFS point: I may be misunderstanding the suggestion, but my current approach depends quite heavily on generation ordering. The reason the STALE propagation is safe is that, in the finite-generation region, descendants are processed before ancestors. If we switch to DFS, I think we would lose that ordering property unless the DFS is constrained in some additional way.

So I think I may not fully understand the DFS idea, and I am not sure if that type of optimization would be orthogonal to tweaking the halt condition or not.

Thanks, Kristofer

On 6/12/2026 11:21 AM, Kristofer Karlsson wrote:

Ah. this is indeed the detail I missed. For any i in {1, 2}, if Pi only appears alongside the STALE bit, then we can stop the walk. This tracks because the other bit can't contribute any new information.

A data shape that makes this particularly helpful is the "release branch" data shape that I used to justify the --negotiation-include option [1].

[1] https://lore.kernel.org/git/62e5ef1a4b800cb18b2e934f45303095d545613b.1779207896.git.gitgitgadget@gmail.com/

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.

My thought was focused on the case of "all queued commits have P1 and P2" and then we could determine which should be non-stale using DFS focused only on the current queued set.

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 your persistence in working on this through my misunderstanding.

Thanks, -Stolee

On Fri, 12 Jun 2026 at 17:48, Derrick Stolee <stolee@gmail.com> wrote:

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.

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.

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

On Fri, 13 Jun 2026, Kristofer Karlsson wrote:

I have to add a self-correction here: STALE does reach D through the main line. The real issue is that the bypass branch has a low generation number, so max_nonstale keeps the loop alive until the stale frontier drains all the way down.

In our monorepo, the concrete trigger is imported repositories. An import merge brings in a separate history with its own root at generation 0. As soon as the walk crosses one such import above the merge-base, max_nonstale forces it to drain the entire main graph. Instrumenting paint_down_to_common confirms this: `merge-base --all HEAD HEAD~1000` takes 2.3M steps, of which almost all are stale.

Thanks, Kristofer

On Fri, Jun 12, 2026 at 4:18 AM Kristofer Karlsson <krka@spotify.com> 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). 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?

On Sun, 14 Jun 2026 at 06:32, Elijah Newren <newren@gmail.com> wrote:

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 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.

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