[RFC] commit-reach: terminate merge-base walk when one paint side is exhausted

[RFC] commit-reach: terminate merge-base walk when one paint side is exhausted

[Kristofer Karlsson]

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/

Re: [RFC] commit-reach: terminate merge-base walk when one paint side is exhausted

[Derrick Stolee]

On 6/12/2026 7:15 AM, Kristofer Karlsson wrote:
> 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.

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

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

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

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

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.

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

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.

> Happy to come back with a patch later if the logic holds and the
> overall approach is wanted.
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

Re: [RFC] commit-reach: terminate merge-base walk when one paint side is exhausted

[Kristofer Karlsson]

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

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

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

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

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

Re: [RFC] commit-reach: terminate merge-base walk when one paint side is exhausted

[Derrick Stolee]

On 6/12/2026 10:32 AM, Kristofer Karlsson wrote:
> 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)

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

Re: [RFC] commit-reach: terminate merge-base walk when one paint side is exhausted

[Kristofer Karlsson]

On Fri, 12 Jun 2026 at 17:04, Derrick Stolee <stolee@gmail.com> wrote:
> > So the actual halt condition would be:
> >
> >     no non-stale P1|P2 candidates in the queue
> >     AND (no pure-P1 OR no pure-P2)
>
> 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.

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.

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

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

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

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

Re: [RFC] commit-reach: terminate merge-base walk when one paint side is exhausted

[Derrick Stolee]

On 6/12/2026 11:21 AM, Kristofer Karlsson wrote:
> On Fri, 12 Jun 2026 at 17:04, Derrick Stolee <stolee@gmail.com> wrote:
>>> So the actual halt condition would be:
>>>
>>>     no non-stale P1|P2 candidates in the queue
>>>     AND (no pure-P1 OR no pure-P2)
>>
>> 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.
> 
> 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.

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.
>>> 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].
>> 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.
> 
> Yes, and I think that part works since we visit them in generational order,
> so B can invalidate C before C is reached.
> 
>> 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.
>>
> 
> 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.
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