commit-reach: terminate merge-base walk when one side is exhausted

From: Kristofer Karlsson <[email protected]>

Add a paint_state struct for use by paint_down_to_common() that wraps a prio_queue with per-side commit counters. Each non-stale queued commit occupies exactly one counter bucket based on its paint flags: PARENT1-only, PARENT2-only, or both sides (a pending merge-base candidate).

The counters are maintained by paint_count_update() which adjusts the appropriate bucket by a signed delta. An exhaustive switch on the paint+stale bits documents all valid flag combinations in one place.

Convert paint_down_to_common() to use paint_state. The loop now drains the queue via paint_queue_get() which returns NULL when all counters reach zero, replacing the old pointer-based termination (max_nonstale). This is equivalent behavior -- both conditions detect that no non-stale entries remain.

paint_queue_get() uses a "pop first" form: it dequeues a commit, then checks the counters. This means the loop exits one iteration earlier than the old code in some topologies (the popped stale commit is never processed), so a few step counts drop by one.

The existing nonstale_queue is left in place for ahead_behind(), though nonstale_queue_put_dedup() and nonstale_queue_get_dedup() became unused and are removed.

---
 .../technical/paint-down-to-common.adoc       |   9 +-
 commit-reach.c                                | 103 +++++++++++++-----
 t/t6600-test-reach.sh                         |   6 +-
 3 files changed, 82 insertions(+), 36 deletions(-)

index cea0cc2f91..37fa6f93c1 100644
@@ -103,15 +103,12 @@ re-enqueued is bounded by the number of flag transitions.
 Termination
 -----------
 
-The walk uses a `nonstale_queue` wrapper around `prio_queue` that
-tracks `max_nonstale`: the lowest-priority non-stale commit enqueued
-so far. Once that commit is dequeued, every remaining entry is known
-to be STALE and the loop terminates. Specifically, the main loop
+The walk tracks the number of commits of each type in the queue
+(PARENT1-only, PARENT2-only, pending merge-base). The main loop
 ends when one of the following conditions holds:
 
   1. The queue is empty.
-  2. `max_nonstale` has been dequeued, meaning the queue only contains
-     STALE entries.
+  2. The queue contains only stale entries.
   3. Generation cutoff: the dequeued commit's generation is below
      a caller-supplied `min_generation` threshold.
   4. Single result: the caller only needs one merge base, one has

index 55aa220bb3..f9895f5fd7 100755
@@ -366,7 +366,7 @@ test_expect_success 'get_merge_bases_many:pending-stale' '
 		git rev-parse ps-B
 	} >expect &&
 	test_all_modes get_merge_bases_many &&
-	test_paint_down_steps 6 6 6 6
+	test_paint_down_steps 5 5 5 5
 '
 
 test_expect_success 'get_merge_bases_many:infinity-both-sides' '

@@ -381,7 +381,7 @@ test_expect_success 'get_merge_bases_many:infinity-both-sides' '
 		git rev-parse pi-B
 	} >expect &&
 	test_all_modes get_merge_bases_many &&
-	test_paint_down_steps 5 5 5 5
+	test_paint_down_steps 5 4 5 5
 '
 
 test_expect_success 'setup mixed finite/INFINITY topology' '

@@ -438,7 +438,7 @@ test_expect_success 'merge-base --all with clock skew and redundant ancestor (si
 	>input &&
 	git rev-parse se2-MB1 >expect &&
 	run_all_modes git merge-base --all se2-A se2-B &&
-	test_paint_down_steps 8 7 8 8
+	test_paint_down_steps 8 6 8 8
 '
 
 test_expect_success 'reduce_heads' '

gitgitgadget

Ooh, I like this setup for what comes later; it sets the stage perfectly for the key insight behind the optimization. Very nice.

became -> become

Looks good.

Good catch, will fix.

Yes, I should perhaps add a code comment for this to ensure it does not get corrupted in the future. Something like this:

/* must check exit conditions before decrementing counters
for the dequeued commit -- the counters may otherwise be be temporarily zero until the commit has been processed and its parent nodes have been enqueued.
*/

Or is it overkill?

Thanks,
Kristofer

My comment was meant more as a "review out loud; show how I'm thinking about the patch as I read it" kind of comment rather than as a note of something worth changing in the patch. The order _is_ important here, so the idea of adding a comment to reinforce it seems quite reasonable to consider (I thought about changing my comment to ask for one when reviewing), but I'm on the fence about whether it's important enough or overkill. I'm okay with the patch either way.

Although, if you do add one, as per the CodingGuidelines:

/*
* Multi-line comments include their delimiters
* on separate lines from the text.
*/

:-)

True, but your thinking out loud fortunately reminded me that I had the same thought process, and that the ordering may not be immediately obvious -- and thus we should document it.

I will add a comment for it...

... and I will be stricter about the formatting in the patches than I was in the email :)

Thanks,
Kristofer

From: Kristofer Karlsson <[email protected]>

Add an early termination check to paint_down_to_common() using the per-side counters introduced earlier. Once the walk enters the finite-generation region, terminate early when one side's exclusive count drops to zero -- no new merge-base can form without both paint sides meeting.

The check also waits for pending_merge_bases to reach zero, ensuring all merge-base candidates have been dequeued and recorded before exiting.

The INFINITY gate ensures correctness: commits without a commit-graph entry have GENERATION_NUMBER_INFINITY and are ordered by commit date, which is not topologically reliable. The optimization only fires once the walk enters the finite-generation region where ordering guarantees hold.

Step counts measured with trace2 on git.git with commit-graph:

merge-base --all v2.0.0 v2.55.0-rc1:

    before: 72264 steps    after: 44589 steps

merge-base --all v2.55.0-rc1 v2.55.0-rc1~5:
before: 110 steps after: 7 steps

---
 .../technical/paint-down-to-common.adoc       | 23 ++++++++++++++++++-
 commit-reach.c                                | 18 ++++++++++++---
 t/t6600-test-reach.sh                         |  4 ++--
 3 files changed, 39 insertions(+), 6 deletions(-)

index 37fa6f93c1..7c93f7e676 100644
@@ -114,6 +114,9 @@ ends when one of the following conditions holds:
   4. Single result: the caller only needs one merge base, one has
      been found, and the walk has entered the finite-generation
      region.
+  5. Side exhaustion: no pure PARENT1 or pure PARENT2 commits
+     remain in the queue, no pending merge-base candidates exist,
+     and the walk has entered the finite-generation region.
 
 Stale entry condition
 ~~~~~~~~~~~~~~~~~~~~~

@@ -124,6 +127,20 @@ existing candidates by proving one is an ancestor of another, but
 `remove_redundant()` handles that as a post-processing step, so it
 is safe to exit early.
 
+Side-exhaustion condition
+~~~~~~~~~~~~~~~~~~~~~~~~~
+A new merge-base requires commits from both sides to meet. When one
+side's exclusive counter reaches zero and there are no pending
+merge-base candidates, no future traversal step can produce a new
+candidate.
+
+This optimization only activates in the finite-generation region
+where topological ordering holds. In that region, children are
+always visited before parents, so paint flags are final at visit
+time and an exhausted side cannot reappear. In the INFINITY region,
+commit-date ordering can violate this guarantee, so the check is
+skipped.
+
 Generation cutoff
 ~~~~~~~~~~~~~~~~~
 Some callers (notably `remove_redundant()`) supply a `min_generation`

@@ -169,12 +186,16 @@ ordering via `compare_commits_by_commit_date`.  Because commit
 dates are not monotonic (clock skew, rebases, etc.), the queue
 may visit commits out of topological order.
 
-This disables the optimization that depends on generation ordering:
+This disables the optimizations that depend on generation ordering:
 
   - *Single result*: the first merge-base candidate found may not
     be the shallowest, because a deeper ancestor with a higher
     commit date can be dequeued first.
 
+  - *Side exhaustion*: one paint side can appear to drain from the
+    queue while commits from that side are still waiting with lower
+    dates, causing premature termination.
+
 Related documentation
 ---------------------
 

index a62b5e4624..e03505b535 100644
@@ -132,6 +132,10 @@ static void paint_queue_put(struct paint_state *state,
 	}
 }
 
+/*
+ * Dequeue the next commit for the paint walk, or return NULL when
+ * no more merge bases can be discovered.
+ */
 static struct commit *paint_queue_get(struct paint_state *state)
 {
 	struct commit *commit = prio_queue_get(&state->queue);

@@ -141,9 +145,17 @@ static struct commit *paint_queue_get(struct paint_state *state)
 
 	commit->object.flags &= ~ENQUEUED;
 
-	if (!state->parent1_count && !state->parent2_count &&
-	    !state->mb_candidate_count)
-		return NULL;
+	if (!state->mb_candidate_count) {
+		/* only stale entries remain */
+		if (!state->parent1_count && !state->parent2_count)
+			return NULL;
+
+		/* one side is exhausted */
+		if ((!state->parent1_count || !state->parent2_count) &&
+		    state->gen_ordered &&
+		    commit_graph_generation(commit) < GENERATION_NUMBER_INFINITY)
+			return NULL;
+	}
 
 	paint_count_update(state, commit->object.flags, -1);
 	return commit;

index f9895f5fd7..6bf17cb7b6 100755
@@ -297,7 +297,7 @@ test_expect_success 'in_merge_bases_many:self' '
 	EOF
 	echo "in_merge_bases_many(A,X):1" >expect &&
 	test_all_modes in_merge_bases_many &&
-	test_paint_down_steps 45 2 25 3
+	test_paint_down_steps 45 1 25 1
 '
 
 test_expect_success 'is_descendant_of:hit' '

@@ -414,7 +414,7 @@ test_expect_success 'merge-base --all commit-walk steps' '
 	>input &&
 	git rev-parse commit-9-1 >expect &&
 	run_all_modes git merge-base --all commit-9-9 commit-9-1 &&
-	test_paint_down_steps 81 80 81 81
+	test_paint_down_steps 81 9 57 81
 '
 
 test_expect_success 'merge-base --all with clock skew (side-exhaustion)' '

gitgitgadget

...this is the insight behind this optimization, which the previous patch set up so nicely.

What about GENERATION_NUMBER_V1_MAX ?

[...]

Other than the GENERATION_NUMBER_V1_MAX stuff, this commit looks good. There may be a way to reword things to allow the current split, but I'll keep reading to the next patches.

I am planning to rewrite the documentation to refer to the regions as (topologically) ordered vs unordered (I think you coined it in one of the other emails, and I quite prefer that over infinite/finite).

I guess I will need to rewrite the commit messages too, to reflect that. Hopefully fixed with v8, unless I miss something in that juggling.

I think finite was correct before, given that the alternative was the infinite region (GENERATION_NUMBER_INFINITE) but I will rephrase this as unordered and ordered for v8.

Agreed, I will pick something along those lines at the very least (maybe exactly, but no promise yet).

V1_MAX is introduced before it's referenced in code, though I think it's still valid as a concept for the existing docs, I just need to be careful how I frame it in terms of the implementation.

I will do something here, though I am not yet sure exactly what.

Thanks,
Kristofer

From: Kristofer Karlsson <[email protected]>

Consolidate the min_generation termination condition into paint_queue_get(), alongside the existing stale-entry and side-exhaustion checks.

Move last_gen into struct paint_state so that commit_graph_generation() is called exactly once per dequeued commit and the result is shared across all termination checks and the monotonicity BUG assertion.

---
 commit-reach.c | 31 ++++++++++++++++++-------------
 1 file changed, 18 insertions(+), 13 deletions(-)

index e03505b535..b50b0e4e47 100644
@@ -90,6 +90,8 @@ struct paint_state {
 	size_t parent2_count;
 	size_t mb_candidate_count;
 	int gen_ordered;
+	timestamp_t min_generation;
+	timestamp_t last_gen;
 };
 
 static void paint_count_update(struct paint_state *state,

@@ -139,11 +141,23 @@ static void paint_queue_put(struct paint_state *state,
 static struct commit *paint_queue_get(struct paint_state *state)
 {
 	struct commit *commit = prio_queue_get(&state->queue);
+	timestamp_t generation;
 
 	if (!commit)
 		return NULL;
 
 	commit->object.flags &= ~ENQUEUED;
+	generation = commit_graph_generation(commit);
+
+	if (state->min_generation && generation > state->last_gen)
+		BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
+		    generation, state->last_gen,
+		    oid_to_hex(&commit->object.oid));
+	state->last_gen = generation;
+
+	/* generation cutoff */
+	if (generation < state->min_generation)
+		return NULL;
 
 	if (!state->mb_candidate_count) {
 		/* only stale entries remain */

@@ -153,7 +167,7 @@ static struct commit *paint_queue_get(struct paint_state *state)
 		/* one side is exhausted */
 		if ((!state->parent1_count || !state->parent2_count) &&
 		    state->gen_ordered &&
-		    commit_graph_generation(commit) < GENERATION_NUMBER_INFINITY)
+		    generation < GENERATION_NUMBER_INFINITY)
 			return NULL;
 	}
 

@@ -180,9 +194,10 @@ static int paint_down_to_common(struct repository *r,
 	struct commit *commit;
 	int i;
 	int steps = 0;
-	timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
 	struct commit_list **tail = result;
 
+	state.min_generation = min_generation;
+	state.last_gen = GENERATION_NUMBER_INFINITY;
 	if (!min_generation && !corrected_commit_dates_enabled(r)) {
 		state.queue.compare = compare_commits_by_commit_date;
 		state.gen_ordered = 0;

@@ -201,18 +216,8 @@ static int paint_down_to_common(struct repository *r,
 	while ((commit = paint_queue_get(&state))) {
 		struct commit_list *parents;
 		int flags;
-		timestamp_t generation = commit_graph_generation(commit);
 		steps++;
 
-		if (min_generation && generation > last_gen)
-			BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
-			    generation, last_gen,
-			    oid_to_hex(&commit->object.oid));
-		last_gen = generation;
-
-		if (generation < min_generation)
-			break;
-
 		flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
 		if (flags == (PARENT1 | PARENT2)) {
 			if (!(commit->object.flags & RESULT)) {

@@ -225,7 +230,7 @@ static int paint_down_to_common(struct repository *r,
 				 */
 				if (!(mb_flags & MERGE_BASE_FIND_ALL) &&
 				    state.gen_ordered &&
-				    generation < GENERATION_NUMBER_INFINITY)
+				    state.last_gen < GENERATION_NUMBER_INFINITY)
 					break;
 			}
 			/* Mark parents of a found merge stale */

gitgitgadget

From: Kristofer Karlsson <[email protected]>

Remove the fallback that switched paint_down_to_common() from generation ordering to commit-date ordering when the commit-graph lacks corrected commit dates (v1 graph with topo levels only).

The fallback was added in 091f4cf3 (commit: don't use generation numbers if not needed, 2018-08-30) to avoid a performance regression on the Linux kernel repo where v1 topo levels caused "git merge-base v4.8 v4.9" to walk 636k commits instead of 167k. A side branch with a low topo level stayed in the queue behind a long chain, preventing early STALE propagation.

Side-exhaustion (added in the previous commits) solves this differently by terminating the walk as soon as one paint side empties from the queue, preventing the deep walk regardless of queue ordering. Benchmarks of "git merge-base --all v4.8 v4.9" on the Linux kernel repo show that side-exhaustion reduces the step count far below what the date-ordering fallback achieved:

steps time

  no graph, baseline:   167,413    3.25 s
  v1 graph, baseline:   167,413    0.25 s
  v2 graph, baseline:   167,441    0.29 s
  v1 graph, this series:  5,725    0.02 s
  v2 graph, this series:  3,887    0.01 s

With generation ordering always active, the existing min_generation check in paint_queue_get() correctly identifies when the walk has reached the finite generation region. The date ordering fallback broke this invariant: a commit could have a finite topo level while the queue was date-ordered, causing the early exit to fire before all merge bases were found.

For v1 commit-graphs where generation numbers saturate at GENERATION_NUMBER_V1_MAX, introduce a topological ceiling that the early exit gates compare against instead of GENERATION_NUMBER_INFINITY. This ensures saturated commits are treated as unordered, preventing premature termination when generation values are unreliable.

---
 .../technical/paint-down-to-common.adoc       | 51 +++----------------
 commit-reach.c                                | 23 +++++----
 t/t6600-test-reach.sh                         | 23 ++++-----
 3 files changed, 27 insertions(+), 70 deletions(-)

index 7c93f7e676..bdd5ffb5c3 100644
@@ -44,10 +44,6 @@ ancestor is necessarily redundant.
 INFINITY and finite generation regions
 --------------------------------------
 
-The properties in this section assume generation-number ordering (the
-default comparator). They do NOT hold when the date-ordering fallback
-is active -- see <<date-ordering-fallback>>.
-
 The commit-graph stores a generation number for each commit.
 Commits not in the commit-graph have generation
 `GENERATION_NUMBER_INFINITY`. The graph is closed under

@@ -91,10 +87,12 @@ traversal: children are always visited before their parents. This
 means that paint on already-visited commits is final -- no future
 traversal step can add paint to them.
 
-In the INFINITY region, commit-date ordering can violate this: a
-parent with a later date can be visited before a child with an earlier
-date. Paint flags are therefore NOT final at visit time, and a
-commit visited with only one side's paint may later gain the other.
+In the INFINITY region, all commits share the same generation
+value, so the queue breaks ties by commit date. This can violate
+topological ordering: a parent with a later date can be visited
+before a child with an earlier date. Paint flags are therefore
+NOT final at visit time, and a commit visited with only one
+side's paint may later gain the other.
 
 Paint flags are only added, never removed. Since each flag can be set
 at most once per commit, the number of times a commit can be

@@ -159,43 +157,6 @@ descendant of this candidate (generation ordering guarantees
 children are visited first), so it cannot be redundant and the walk
 can stop immediately.
 
-This optimization is NOT safe when the date-ordering fallback is
-active, because commit-date order can visit a deeper ancestor
-before a shallower one -- see <<date-ordering-fallback>>.
-
-[[date-ordering-fallback]]
-Date-ordering fallback
-----------------------
-
-When the commit-graph has generation numbers v1 and no
-generation floor is specified, topological ordering
-(via generation numbers) is disabled.  Topological levels are
-correct but unbalanced -- ordering by such generation numbers
-can sometimes cause the walk to detour too far before finding
-merge bases.  Commit-date ordering typically reaches them in
-fewer steps -- see this change for more details:
-
-   091f4cf3 (commit: don't use generation numbers if not needed,
-   2018-08-30)
-
-With generation number v2 (corrected commit dates) we have the best
-of both worlds and do not need this fallback.
-
-For v1, `paint_down_to_common()` falls back to pure commit-date
-ordering via `compare_commits_by_commit_date`.  Because commit
-dates are not monotonic (clock skew, rebases, etc.), the queue
-may visit commits out of topological order.
-
-This disables the optimizations that depend on generation ordering:
-
-  - *Single result*: the first merge-base candidate found may not
-    be the shallowest, because a deeper ancestor with a higher
-    commit date can be dequeued first.
-
-  - *Side exhaustion*: one paint side can appear to drain from the
-    queue while commits from that side are still waiting with lower
-    dates, causing premature termination.
-
 Related documentation
 ---------------------
 

index b50b0e4e47..85bda146e6 100644
@@ -89,9 +89,9 @@ struct paint_state {
 	size_t parent1_count;
 	size_t parent2_count;
 	size_t mb_candidate_count;
-	int gen_ordered;
 	timestamp_t min_generation;
 	timestamp_t last_gen;
+	timestamp_t topo_ceiling;
 };
 
 static void paint_count_update(struct paint_state *state,

@@ -166,8 +166,7 @@ static struct commit *paint_queue_get(struct paint_state *state)
 
 		/* one side is exhausted */
 		if ((!state->parent1_count || !state->parent2_count) &&
-		    state->gen_ordered &&
-		    generation < GENERATION_NUMBER_INFINITY)
+		    generation < state->topo_ceiling)
 			return NULL;
 	}
 

@@ -187,9 +186,13 @@ static int paint_down_to_common(struct repository *r,
 				enum merge_base_flags mb_flags,
 				struct commit_list **result)
 {
+	/*
+	 * Generation ordering is required for the side-exhaustion and
+	 * single-result early exits, which rely on topological traversal
+	 * order (children visited before parents) in the finite region.
+	 */
 	struct paint_state state = {
-		.queue = { compare_commits_by_gen_then_commit_date },
-		.gen_ordered = 1,
+		.queue = { compare_commits_by_gen_then_commit_date }
 	};
 	struct commit *commit;
 	int i;

@@ -198,10 +201,9 @@ static int paint_down_to_common(struct repository *r,
 
 	state.min_generation = min_generation;
 	state.last_gen = GENERATION_NUMBER_INFINITY;
-	if (!min_generation && !corrected_commit_dates_enabled(r)) {
-		state.queue.compare = compare_commits_by_commit_date;
-		state.gen_ordered = 0;
-	}
+	state.topo_ceiling = corrected_commit_dates_enabled(r)
+		? GENERATION_NUMBER_INFINITY
+		: GENERATION_NUMBER_V1_MAX;
 
 	one->object.flags |= PARENT1;
 	if (!n) {

@@ -229,8 +231,7 @@ static int paint_down_to_common(struct repository *r,
 				 * descendant of this one.
 				 */
 				if (!(mb_flags & MERGE_BASE_FIND_ALL) &&
-				    state.gen_ordered &&
-				    state.last_gen < GENERATION_NUMBER_INFINITY)
+				    state.last_gen < state.topo_ceiling)
 					break;
 			}
 			/* Mark parents of a found merge stale */

index 6bf17cb7b6..445449a458 100755
@@ -381,7 +381,7 @@ test_expect_success 'get_merge_bases_many:infinity-both-sides' '
 		git rev-parse pi-B
 	} >expect &&
 	test_all_modes get_merge_bases_many &&
-	test_paint_down_steps 5 4 5 5
+	test_paint_down_steps 5 4 5 4
 '
 
 test_expect_success 'setup mixed finite/INFINITY topology' '

@@ -414,31 +414,26 @@ test_expect_success 'merge-base --all commit-walk steps' '
 	>input &&
 	git rev-parse commit-9-1 >expect &&
 	run_all_modes git merge-base --all commit-9-9 commit-9-1 &&
-	test_paint_down_steps 81 9 57 81
+	test_paint_down_steps 81 9 57 37
 '
 
 test_expect_success 'merge-base --all with clock skew (side-exhaustion)' '
-	# Verify correct merge base under clock skew.  se-D (the
-	# merge base) has a higher date than its child se-C.
-	# Generation ordering ensures se-C is visited before se-D,
-	# so P1 paint propagates correctly and se-D is found.
+	# Verify that the merge base is computed correctly even
+	# when commits have non-monotonic commit dates.
 	>input &&
 	git rev-parse se-D >expect &&
 	run_all_modes git merge-base --all se-A se-B &&
-	test_paint_down_steps 6 4 6 6
+	test_paint_down_steps 6 4 6 4
 '
 
 test_expect_success 'merge-base --all with clock skew and redundant ancestor (side-exhaustion)' '
-	# Verify correct merge base when clock skew could cause a
-	# too-deep result.  MB1 is the correct merge base; MB2 is
-	# its ancestor.  A reaches MB2 via E (high date) and MB1
-	# via C (low date).  Generation ordering ensures C is
-	# visited before side-exhaustion fires, so MB1 is found
-	# and remove_redundant correctly discards MB2.
+	# Verify that the correct merge base is found even when
+	# non-monotonic commit dates could cause a redundant
+	# ancestor to be visited first.
 	>input &&
 	git rev-parse se2-MB1 >expect &&
 	run_all_modes git merge-base --all se2-A se2-B &&
-	test_paint_down_steps 8 6 8 8
+	test_paint_down_steps 8 6 8 6
 '
 
 test_expect_success 'reduce_heads' '

gitgitgadget

Nice!

Even better!

Should the work associated with this paragraph come earlier so 8/10 doesn't have its weird split?

The code and tests look good, my main issue is that the documentation and code are not consistent at patch 08/10, so we need some way of correcting that. I don't know whether that means splitting the code differently in patches 8 & 10, or splitting the documentation differently or something else. Thoughts?

Anyway, nicely done overall, this is nearly ready to merge; it just needs a few small touch-ups.

I am thinking that I am mostly happy with the sequencing of the code changes, but aligning it with the documentation seems to be the messy part.

I am going to spend some time on reworking the documentation overall because I think that's the main remaining work and feedback on the code changes seem to have slowed down to effectively zero (which I'm happy about, though I've always found it easier to write correct code than useful documentation, so now the real work starts).

We could of course introduce the topo_ceiling already in patch 8, but there would be no behavior change since gen_ordered is disabled for v1 commit-graphs.

But let me know if you still want me to move that code change, I don't feel too strongly about it.

Agreed, since I am new to this I have ran into multiple gotchas when dealing with both v1 and v2, so the more we can unify the code paths, the better. And I suppose the performance improvement is a nice bonus (though people who still have v1 graphs and are using the latest git version should probably just switch to v2 instead).

I did consider making this a utility function but I realized that this was the only part of the code where topological ordering mattered for correctness so it was nice that I could avoid that.

Yes, I will take a whole new stab at the documentation changes as a whole since a lot of things have changed in the code since v1. This potentially means a larger rewrite so it will likely take a few days days until I am happy enough with it.

Thanks, happy to hear that!
Kristofer

Optimize paint_down_to_common() for merge-base queries that hit large one-sided histories.

When the walk from one side reaches a commit with a very low generation number that the other side never paints, the walk is forced to drain most of the graph. A common trigger is a repository import that grafts a separate history with its own root, but any merge that introduces a low-generation commit never painted by the other side has the same effect.

A new merge-base candidate can only be discovered when exclusive PARENT1 and PARENT2 paint meet. This series teaches paint_down_to_common() to stop as soon as one side has no exclusive commits left in the queue; once one side is exhausted, no further candidates can appear.

origin/HEAD  o   o  PR HEAD
             |   |
   (import)  o   :
            / \ /
           |   o  merge-base
           |   |
           :   :  (~2.5M commits)
           |   |

import root main root

In the RFC thread [1], Derrick Stolee provided a criss-cross counterexample that sharpened the halt condition, and Elijah Newren independently discovered the same optimization and shared an implementation in PR #2150 [2]. Patch 3 incorporates test cases from Elijah's branch.

This series implements the optimization only after the walk enters the ordered region, where generation ordering guarantees that paint on visited commits is final.

Patch 2 adds a test_trace2_data_singular helper to test-lib-functions.sh that reports expected/actual values on assertion failure instead of a silent grep exit. This was invaluable during development for iterating on step counts across the series, and should be valuable for repairing tests after future algorithmic changes. Happy to drop it if it is considered unnecessary infrastructure.

The final patch removes the commit-date ordering fallback introduced by 091f4cf3 (commit: don't use generation numbers if not needed, 2018-08-30). With side-exhaustion in place, the fallback is no longer needed for performance, and removing it ensures the queue is always generation-ordered regardless of graph version, so every termination condition can rely on a single ordering invariant. This patch can be dropped if the scope is too broad for this series.

Benchmarks

Trace2 step counts are deterministic (measured via trace2_data_intmax added in patch 5). Wall-clock times are best-of-11 runs.

2.6M-commit monorepo with commit-graph:

                                      steps              wall-clock
merge-base --all  (across import)  2143438 ->      3     3.67s ->    5ms
merge-base --all  (1000 apart)     2692915 ->   1035     4.41s ->    7ms
merge-base --all  (5000 apart)     2692915 ->   6401     4.45s ->   13ms
merge-base --all  (HEAD vs import) 2698872 ->  45960     4.50s ->   79ms
merge-tree        (across import)  2143438 ->      3     4.42s ->   11ms

git.git (88k commits, commit-graph):

steps wall-clock

merge-base --all v2.0.0 v2.55.0-rc1 72264 ->  44589      110ms ->   68ms
merge-base --all HEAD HEAD~1000      9891 ->   3828       18ms ->   10ms
merge-base --all HEAD HEAD~10000    72303 ->  41487      101ms ->   50ms

This series is based on master.

[1]
https://lore.kernel.org/git/CAL71e4Ps-2_0+uuZu43N9pFnXBemoAohPs_eyRJf8taXHJPAXQ@mail.gmail.com/T/#u
[2] https://github.com/gitgitgadget/git/pull/2150

Changes since v7:

* Moved topo_ceiling from patch 10 into patch 8 where the side-exhaustion gate first needs it, so V1_MAX saturation is handled correctly at every commit in the series.

* Renamed "finite/INFINITY region" to "ordered/unordered region" in documentation and in general tried to tighten up the documentation around this.

* Added code comment explaining why termination conditions must be checked before decrementing counters in paint_queue_get().

* Minor wording and formatting fixes in commit messages, test comments, and the t6099 ASCII graph.

Changes since v6:

* Now based on master; all prerequisite topics have graduated.

* Added a topological ceiling concept for v1 commit-graph support. When the commit-graph uses v1 topological levels (no GDAT chunk), generation numbers saturate at V1_MAX, breaking ordering guarantees in the same way as INFINITY. Patch 10 introduces a topo_ceiling (V1_MAX for v1, INFINITY for v2) that the side-exhaustion and single-result gates compare against, so saturated commits are treated as unordered.

* Used $LF variable instead of a literal newline in the test_trace2_data_singular helper (patch 2), matching the existing pattern in test-lib. (Suggested by Rene Scharfe.)

* Improved the min_generation / generation cutoff documentation to explain why callers can safely terminate early, rather than just stating the threshold rule.

Changes since v5:

* Rebased on next, which now contains kk/commit-reach-find-all-fix. The gen_ordered guard from that topic is carried through patches 7-9 via state.gen_ordered, then removed in patch 10 along with the date-ordering fallback.

* Minor documentation and test comment improvements.

Changes since v4:

* New patch 2/10: added test_trace2_data_singular helper to test-lib-functions.sh. Shows expected/actual values on assertion failure instead of a silent grep failure. Makes iterating on step counts much easier.

* New patch 6/10: added clock-skew topologies (se-, se2-) that expose side-exhaustion bugs when the commit-date ordering fallback fires with a v1 commit graph. All topologies use a shared skew_commit helper. Includes step count assertions for edge-case tests from patch 3.

* Folded the nonstale_queue dedup wrapper removal (previously separate patch 6/8) into the paint_state introduction in patch 7/10.

* New patch 10/10: remove the commit-date ordering fallback in paint_down_to_common(). The fallback (091cf18e) was a performance optimization for v1 commit graphs, but it breaks the generation ordering invariant that both the side-exhaustion and single-result optimizations depend on. With side-exhaustion in place, the fallback is no longer needed. If kept, this supersedes the separate "commit-reach: fix !FIND_ALL early exit with v1 commit graph" topic.

Changes since v3:

* Fixed BUG assertion that was accidentally made unconditional in v3:
restored the min_generation guard so it only fires when generation-based ordering is active.

* Moved generation cutoff and single-result termination conditions into the documentation in patch 1, since they describe existing behavior.

* Renamed paint_state counter fields for clarity: p1_count -> parent1_count, p2_count -> parent2_count, pending_merge_bases -> mb_candidate_count. Changed counter types from int to size_t. (Suggested by Rene Scharfe.)

Changes since v2:

* New patch 9/10 (was 8/8): moved the min_generation termination check and the last_gen monotonicity assertion into paint_queue_get(), consolidating halt conditions. commit_graph_generation() is now called once per dequeued commit and shared across all checks.

* Moved all halt conditions inside paint_queue_get() with the "pop first"
form: pop, check, then decrement counters. This keeps the optimization commit's diff minimal (just inserting the new checks between pop and decrement).

* Shortened the doc comment on paint_queue_get() to describe what it does rather than how. Inline comments on each return NULL explain the specific halt condition.

* Replaced the manual commit-graph setup in the step-count test with run_all_modes, which now sets GIT_TRACE2_EVENT per mode and produces trace-mode-{none,full,half,no-gdat}.txt files.

* Added a test_paint_down_steps helper for concise 4-mode step assertions with diagnostic output on mismatch (prints "expected X, got Y" instead of a silent grep failure).

* Added step-count assertions to the single-walk edge-case tests:
in_merge_bases_many:self, pending-stale, infinity-both-sides, mixed-finite-infinity.

* Included step counts alongside wall-clock times in the benchmark tables.

Changes since v1:

* Reordered patches: documentation first (describing the existing algorithm), tests before code changes, so they demonstrate passing with old logic first.

* Dropped the ahead_behind decoupling patch. paint_state is now a NEW struct alongside nonstale_queue instead of replacing it. ahead_behind() is completely untouched.

* Removed nonstale_queue_put_dedup() and nonstale_queue_get_dedup() (dead code after the conversion) in a separate commit.

* Renamed: struct paint_queue -> paint_state, field pq -> queue, paint_count_add/remove -> paint_count_update (single function with signed delta parameter).

* Split the old paint_count_transition (which handled both old and new flags in one call) into separate remove/add calls with a signed delta. This eliminates the need for the case 0 handler (which tracked "not in the queue") and allows an exhaustive switch on (PARENT1 | PARENT2 | STALE) that documents all valid flag combinations, with BUG() in default.

* Added trace2_data_intmax() instrumentation to report the number of commits visited per paint walk (separate commit), with step-count assertions in tests for deterministic regression detection.

cc: Derrick Stolee [email protected] cc: Elijah Newren [email protected] cc:
Kristofer Karlsson [email protected] cc: René Scharfe [email protected] cc: SZEDER Gábor [email protected]

Elijah Newren (1):
t6600: add test cases for side-exhaustion edge cases

Kristofer Karlsson (9):
Documentation/technical: add paint-down-to-common doc
test-lib-functions: improve diagnostic output for trace2 data
assertions
t6099: add side-exhaustion regression test
commit-reach: add trace2 instrumentation to paint_down_to_common()
t6600: add clock-skew topologies and step counts for edge cases
commit-reach: introduce struct paint_state with per-side counters
commit-reach: terminate merge-base walk when one paint side is
exhausted
commit-reach: move min_generation check into paint_queue_get()
commit-reach: remove commit-date ordering fallback

 Documentation/Makefile                        |   1 +
 Documentation/technical/meson.build           |   1 +
 .../technical/paint-down-to-common.adoc       | 155 +++++++++++
 commit-reach.c                                | 165 +++++++++---
 t/meson.build                                 |   1 +
 t/t6099-merge-base-side-exhaustion.sh         |  82 ++++++
 t/t6600-test-reach.sh                         | 241 +++++++++++++++++-
 t/test-lib-functions.sh                       |  35 +++
 8 files changed, 627 insertions(+), 54 deletions(-)
 create mode 100644 Documentation/technical/paint-down-to-common.adoc
 create mode 100755 t/t6099-merge-base-side-exhaustion.sh

base-commit: 010afd3166ddc64c9863b1506f12cbcdda0d4ea1
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2149%2Fspkrka%2Fside-exhaust-pr-v8
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2149/spkrka/side-exhaust-pr-v8
Pull-Request: https://github.com/gitgitgadget/git/pull/2149

Range-diff vs v7:

1: c1f303353c ! 1: d74c9d5781 Documentation/technical: add paint-down-to-common doc
@@ Documentation/technical/paint-down-to-common.adoc (new)
+
+The walk uses a priority queue ordered by generation number +(highest first), breaking ties by commit date. Each step dequeues
-+the highest-priority commit (this is when we say a commit is -+"visited") and propagates its paint flags to its parents, enqueuing -+them if they gained new flags. When a commit receives both PARENT1 -+and PARENT2, it is a merge-base candidate. A candidate gains the -+STALE flag so its ancestors propagate staleness -- any deeper common -+ancestor is necessarily redundant.
++the highest-priority commit and propagates its paint flags to its ++parents, enqueuing any parent that gained new flags. When a ++commit receives both PARENT1 and PARENT2, it is a merge-base ++candidate. A candidate gains the STALE flag so its ancestors ++propagate staleness -- any deeper common ancestor is necessarily ++redundant.
+
+[[generation-regions]]
-+INFINITY and finite generation regions
-+--------------------------------------
++Topologically ordered and unordered generation regions
++------------------------------------------------------
+
-+The properties in this section assume generation-number ordering (the -+default comparator). They do NOT hold when the date-ordering fallback -+is active -- see <<date-ordering-fallback>>.
-+
-+The commit-graph stores a generation number for each commit. -+Commits not in the commit-graph have generation -+GENERATION_NUMBER_INFINITY. The graph is closed under -+reachability: if a commit is in the graph, all its ancestors are -+too. This partitions the commit graph into two regions:
++Commits fall into two regions based on whether their generation ++numbers provide a topological ordering guarantee:
+
+....
-+ +---------------------------------------+
-+ | INFINITY region |
-+ | generation = INFINITY |
-+ | queue order: heuristic (commit date) |
-+ +---------------------------------------+
-+ |
-+ v
-+ +---------------------------------------+
-+ | Finite region |
-+ | generation = finite |
-+ | queue order: topological |
-+ +---------------------------------------+
++ +------------------------------------------+
++ | Unordered region |
++ | generation = INFINITY or V1_MAX |
++ | queue order: heuristic (commit date) |
++ +------------------------------------------+
++ |
++ v
++ +------------------------------------------+
++ | Ordered region |
++ | generation = finite, unsaturated |
++ | queue order: topological |
++ +------------------------------------------+
+....
+
-+When the commit-graph is enabled, the INFINITY region is typically -+very small -- it only contains commits added since the last -+commit-graph refresh.
-+
-+With v1 commit-graphs (topological levels, no GDAT chunk), -+generation numbers saturate at GENERATION_NUMBER_V1_MAX. -+Saturated commits share the same generation value despite -+different topological depths, which breaks ordering guarantees
-+in the same way as INFINITY. The early exit gates compare
-+against GENERATION_NUMBER_V1_MAX for v1 graphs and -+GENERATION_NUMBER_INFINITY for v2 graphs, so that saturated -+commits are treated as unordered.
-+
-+All reachable INFINITY-generation commits are visited before any -+finite-generation commit, because INFINITY is larger than any finite -+value. Once the walk crosses into the finite region, it stays there. -+
-+In the finite region, generation ordering guarantees topological -+traversal: children are always visited before their parents. This -+means that paint on already-visited commits is final -- no future -+traversal step can add paint to them.
-+
-+In the INFINITY region, commit-date ordering can violate this: a -+parent with a later date can be visited before a child with an earlier -+date. Paint flags are therefore NOT final at visit time, and a -+commit visited with only one side's paint may later gain the other. -+
-+Paint flags are only added, never removed. Since each flag can be set -+at most once per commit, the number of times a commit can be -+re-enqueued is bounded by the number of flag transitions.
++In the ordered region, a child's generation is strictly greater ++than its parent's. Same-generation commits are necessarily ++independent, so the queue always processes children before
++their parents.
++
++In the unordered region, parent-child pairs can share the same ++generation number, so topological order is not guaranteed. The ++queue uses commit-date as a heuristic, which typically produces
++a reasonable traversal order but may process a parent before
++its child.
++
++Commits not in the commit-graph have generation INFINITY; v1 ++commit-graphs saturate at V1_MAX. Both place commits in the ++unordered region. Any optimization that depends on generation ++ordering must account for this saturation boundary.
++
++With generation ordering, values in the unordered region exceed ++those in the ordered region. The walk may therefore transition ++from the unordered region into the ordered region, but never in ++the reverse direction. Without a commit-graph, every commit has INFINITY ++and the walk operates entirely in the unordered region.
++
++In the ordered region, paint on a dequeued commit is final --
++no future step can add flags to it. In the unordered region,
++a dequeued commit may later gain additional paint. Paint flags ++are only added, never removed, bounding the number of
++re-enqueues per commit.
+
+Termination
+-----------
@@ Documentation/technical/paint-down-to-common.adoc (new)
+ 3. Generation cutoff: the dequeued commit's generation is below
+ a caller-supplied min_generation threshold.
+ 4. Single result: the caller only needs one merge base, one has
-+ been found, and the walk has entered the finite-generation
-+ region.
++ been found, and the walk has entered the ordered region.
+
+Stale entry condition
+~~~~~~~~~~~~~~~~~~~~~
@@ Documentation/technical/paint-down-to-common.adoc (new)
+
+Single result
+~~~~~~~~~~~~~
-+When only one merge base is needed, the walk is in the -+finite-generation region, and the queue uses generation ordering, -+the first candidate found is necessarily the highest-generation -+common ancestor. No remaining commit in the queue can be a -+descendant of this candidate (generation ordering guarantees -+children are visited first), so it cannot be redundant and the walk -+can stop immediately.
++When only one merge base is needed and the walk is in the
++ordered region with generation ordering, the first candidate ++found is necessarily the highest-generation common ancestor.
++No remaining commit in the queue can be a descendant of this ++candidate (generation ordering guarantees children are visited ++first), so it cannot be redundant and the walk can stop ++immediately.
+
+This optimization is NOT safe when the date-ordering fallback is +active, because commit-date order can visit a deeper ancestor
@@ Documentation/technical/paint-down-to-common.adoc (new)
+
+When the commit-graph has generation numbers v1 and no
+generation floor is specified, topological ordering
-+(via generation numbers) is disabled. Topological levels are ++(via generation numbers) is disabled. Topological levels are
+correct but unbalanced -- ordering by such generation numbers
+can sometimes cause the walk to detour too far before finding
-+merge bases. Commit-date ordering typically reaches them in ++merge bases. Commit-date ordering typically reaches them in
+fewer steps -- see this change for more details:
+
+ 091f4cf3 (commit: don't use generation numbers if not needed,
@@ Documentation/technical/paint-down-to-common.adoc (new)
+of both worlds and do not need this fallback.
+
+For v1, paint_down_to_common() falls back to pure commit-date
-+ordering via compare_commits_by_commit_date. Because commit ++ordering via compare_commits_by_commit_date. Because commit
+dates are not monotonic (clock skew, rebases, etc.), the queue
+may visit commits out of topological order.
+

  2:  57ecc0b18a =  2:  37ec7e9aa3 test-lib-functions: improve diagnostic output for trace2 data assertions
  3:  f857577e0c !  3:  6208bcf3b3 t6600: add test cases for side-exhaustion edge cases
     @@ t/t6600-test-reach.sh: test_expect_success 'setup' '
      +	#   ps-T1   ps-T2
      +	#
      +	# where ps-T1=merge(ps-Z,ps-B), ps-T2=merge(ps-W,ps-B), so
     -+	# merge-base(ps-T1,ps-T2) = ps-B. During the walk, ps-X transitions
     ++	# merge-base(ps-T1,ps-T2) = ps-B.  During the walk, ps-X transitions
      +	# to (PARENT1|PARENT2) via ps-Z and ps-W before ps-B is dequeued;
      +	# then the STALE-walk from ps-B transitions ps-X to
      +	# (PARENT1|PARENT2|STALE).
     @@ t/t6600-test-reach.sh: test_expect_success 'setup' '
      +
      +	# Build a side topology that lives entirely outside the half
      +	# commit-graph and has non-monotonic commit dates, to exercise the
     -+	# INFINITY-gate in paint_down_to_common. With both tips outside
     ++	# INFINITY-gate in paint_down_to_common.  With both tips outside
      +	# the graph, generation is INFINITY and the queue falls back to
      +	# commit-date order, which here is non-monotonic.
      +	#
     @@ t/t6600-test-reach.sh: test_expect_success 'get_merge_bases_many' '
      +
      +test_expect_success 'get_merge_bases_many:pending-stale' '
      +	# Exercises the (PARENT1|PARENT2) -> (...|STALE) transition path in
     -+	# paint_down_to_common(). See the topology comment in the setup test.
     ++	# paint_down_to_common().  See the topology comment in the setup test.
      +	cat >input <<-\EOF &&
      +	A:ps-T1
      +	X:ps-T2
     @@ t/t6600-test-reach.sh: test_expect_success 'get_merge_bases_many' '
      +'
      +
      +test_expect_success 'get_merge_bases_many:infinity-both-sides' '
     -+	# Exercises the push-time INFINITY-gate in paint_down_to_common(). See
     ++	# Exercises the push-time INFINITY-gate in paint_down_to_common().  See
      +	# the pi-* topology comment in the setup test.
      +	cat >input <<-\EOF &&
      +	A:pi-X
  4:  e8565ce020 !  4:  f4bb58fd46 t6099, t6600: add side-exhaustion regression tests
     @@ Metadata
      Author: Kristofer Karlsson <[email protected]>
      
       ## Commit message ##
     -    t6099, t6600: add side-exhaustion regression tests
     +    t6099: add side-exhaustion regression test
      
          Add t6099 to test the case where multiple merge-base candidates exist
          and one is an ancestor of another. This exercises the side-exhaustion
          optimization in paint_down_to_common together with the
          remove_redundant safety net in get_merge_bases_many_0.
      
     -    Add a mixed finite/INFINITY test to t6600 where one tip is outside
     -    the commit-graph (INFINITY generation) and the other is inside.
     -    This exercises the region transition: the walk starts in the
     -    INFINITY region where side-exhaustion is disabled, then crosses
     -    into the finite region where it can fire.
     -
          Signed-off-by: Kristofer Karlsson <[email protected]>
      
       ## t/meson.build ##
     @@ t/t6099-merge-base-side-exhaustion.sh (new)
      +
      +Graph shape (parents are below children):
      +
     -+   A ----------- X
     -+   |\           /|
     -+   | B---------/ |
     -+   | |           |
     -+   e2 \         f2
     -+   |   |         |
     -+   e1 d1        f1
     -+    \  |        /
     -+     \ |       /
     -+      \|      /
     ++   A ----- X
     ++   |\     /|
     ++   | B---/ |
     ++   |  \    |
     ++   e2  \   f2
     ++   |   |   |
     ++   e1  d1  f1
     ++    \  |  /
     ++     \ | /
     ++      \|/
      +       C
      +
      +A and X are the two tips.

5: 490be76bef ! 5: 53cb1a9690 commit-reach: add trace2 instrumentation to paint_down_to_common()
@@ Commit message
GIT_TRACE2_EVENT. This provides a way to measure the impact of
future optimizations without relying on wall-clock benchmarks alone.

+ Some step counts already vary across commit-graph modes (e.g.
+ in_merge_bases_many:self) because the pre-existing min_generation
+ optimization short-circuits the walk when generation data is
+ available.
+

## commit-reach.c ##
6: 75d58639fc ! 6: e40c759756 t6600: add clock-skew topologies and step counts for edge cases
@@ t/t6600-test-reach.sh: test_expect_success 'merge-base --all commit-walk steps'
'

+test_expect_success 'merge-base --all with clock skew (side-exhaustion)' '
-+ # Verify correct merge base under clock skew. se-D (the
-+ # merge base) has a higher date than its child se-C.
-+ # Generation ordering ensures se-C is visited before se-D,
-+ # so P1 paint propagates correctly and se-D is found.
++ # Verify that the merge base is computed correctly even
++ # when commits have non-monotonic commit dates.
+ >input &&
+ git rev-parse se-D >expect &&
+ run_all_modes git merge-base --all se-A se-B &&
@@ t/t6600-test-reach.sh: test_expect_success 'merge-base --all commit-walk steps'
+'
+
+test_expect_success 'merge-base --all with clock skew and redundant ancestor (side-exhaustion)' '
-+ # Verify correct merge base when clock skew could cause a
-+ # too-deep result. MB1 is the correct merge base; MB2 is
-+ # its ancestor. A reaches MB2 via E (high date) and MB1
-+ # via C (low date). Generation ordering ensures C is
-+ # visited before side-exhaustion fires, so MB1 is found
-+ # and remove_redundant correctly discards MB2.
++ # Verify that the correct merge base is found even when
++ # non-monotonic commit dates could cause a redundant
++ # ancestor to be visited first.
+ >input &&
+ git rev-parse se2-MB1 >expect &&
+ run_all_modes git merge-base --all se2-A se2-B &&
7: a1c8e89ef9 ! 7: bbb83f8eaa commit-reach: introduce struct paint_state with per-side counters
@@ Commit message

The existing nonstale_queue is left in place for ahead_behind(), though nonstale_queue_put_dedup() and nonstale_queue_get_dedup()
- became unused and are removed.
+ become unused and are removed.

## Documentation/technical/paint-down-to-common.adoc ##
-@@ Documentation/technical/paint-down-to-common.adoc: re-enqueued is bounded by the number of flag transitions. +@@ Documentation/technical/paint-down-to-common.adoc: re-enqueues per commit.
Termination
-----------

@@ commit-reach.c: static void clear_nonstale_queue(struct nonstale_queue *queue)
}

-static struct commit *nonstale_queue_get_dedup(struct nonstale_queue *queue)
++/*
++ * Dequeue the next commit for the paint walk, or return NULL when
++ * no more merge bases can be discovered.
++ */
+static struct commit *paint_queue_get(struct paint_state *state)
{
- struct commit *commit = nonstale_queue_get(queue);
@@ commit-reach.c: static void clear_nonstale_queue(struct nonstale_queue *queue)
+
+ commit->object.flags &= ~ENQUEUED;
+
++ /*
++ * Check exit condition before decrementing: the counters
++ * still include this commit, so the last non-stale commit
++ * sees a non-zero count and is returned for processing.
++ */
+ if (!state->parent1_count && !state->parent2_count &&
+ !state->mb_candidate_count)
+ return NULL;
8: 391fa07783 ! 8: 4a6603731c commit-reach: terminate merge-base walk when one paint side is exhausted
@@ Commit message

Add an early termination check to paint_down_to_common() using the per-side counters introduced earlier. Once the walk enters the
- finite-generation region, terminate early when one side's exclusive
- count drops to zero -- no new merge-base can form without both paint
+ ordered region, terminate early when one side's exclusive count
+ drops to zero -- no new merge-base can form without both paint
sides meeting.

The check also waits for pending_merge_bases to reach zero, ensuring all merge-base candidates have been dequeued and recorded before exiting.

- The INFINITY gate ensures correctness: commits without a commit-graph
- entry have GENERATION_NUMBER_INFINITY and are ordered by commit date,
- which is not topologically reliable. The optimization only fires
- once the walk enters the finite-generation region where ordering
- guarantees hold.
+ The optimization is gated by gen_ordered (which excludes v1
+ commit-graphs that use the date-ordering fallback) and by a
+ generation check against topo_ceiling. topo_ceiling is
+ GENERATION_NUMBER_INFINITY for v2 graphs and
+ GENERATION_NUMBER_V1_MAX for v1 graphs, so that saturated commits
+ are treated as unordered. Together these ensure the check only
+ fires in the ordered region where topological ordering holds.
+
+ The same topo_ceiling boundary is applied to the existing
+ single-result early exit so that all generation-dependent gates
+ express the same saturation-aware boundary consistently.

Step counts measured with trace2 on git.git with commit-graph:

@@ Commit message

## Documentation/technical/paint-down-to-common.adoc ##
+@@ Documentation/technical/paint-down-to-common.adoc: its child.
+ Commits not in the commit-graph have generation INFINITY; v1
+ commit-graphs saturate at V1_MAX. Both place commits in the
+ unordered region. Any optimization that depends on generation
+-ordering must account for this saturation boundary.
++ordering must account for this saturation boundary. The early
++exit gates compare against a topological ceiling --
++GENERATION_NUMBER_V1_MAX for v1 graphs and
++GENERATION_NUMBER_INFINITY for v2 graphs -- so that saturated
++commits are treated as unordered.
+
+ With generation ordering, values in the unordered region exceed
+ those in the ordered region. The walk may therefore transition
@@ Documentation/technical/paint-down-to-common.adoc: ends when one of the following conditions holds:
+ a caller-supplied min_generation threshold.
4. Single result: the caller only needs one merge base, one has
- been found, and the walk has entered the finite-generation
- region.
+ been found, and the walk has entered the ordered region.
+ 5. Side exhaustion: no pure PARENT1 or pure PARENT2 commits
+ remain in the queue, no pending merge-base candidates exist,
-+ and the walk has entered the finite-generation region.
++ and the walk has entered the ordered region.

Stale entry condition
~~~~~~~~~~~~~~~~~~~~~
@@ Documentation/technical/paint-down-to-common.adoc: existing candidates by provin
+A new merge-base requires commits from both sides to meet. When one
+side's exclusive counter reaches zero and there are no pending
+merge-base candidates, no future traversal step can produce a new
-+candidate.
-+
-+This optimization only activates in the finite-generation region
-+where topological ordering holds. In that region, children are
-+always visited before parents, so paint flags are final at visit
-+time and an exhausted side cannot reappear. In the INFINITY region,
-+commit-date ordering can violate this guarantee, so the check is
-+skipped.
++candidate. This optimization only activates in the ordered region,
++where paint flags are final at visit time; in the unordered region,
++a side that appears exhausted could reappear through late paint
++propagation.
+
Generation cutoff
~~~~~~~~~~~~~~~~~
Some callers (notably remove_redundant()) supply a min_generation
-@@ Documentation/technical/paint-down-to-common.adoc: ordering via compare_commits_by_commit_date. Because commit +@@ Documentation/technical/paint-down-to-common.adoc: ordering via compare_commits_by_commit_date. Because commit
dates are not monotonic (clock skew, rebases, etc.), the queue
may visit commits out of topological order.

@@ Documentation/technical/paint-down-to-common.adoc: ordering via `compare_commits

## commit-reach.c ##
-@@ commit-reach.c: static void paint_queue_put(struct paint_state *state,
- }
- }
+@@ commit-reach.c: struct paint_state {
+ size_t parent2_count;
+ size_t mb_candidate_count;
+ int gen_ordered;
++ timestamp_t topo_ceiling;
+ };

-+/*
-+ * Dequeue the next commit for the paint walk, or return NULL when -+ * no more merge bases can be discovered.
-+ */
- static struct commit *paint_queue_get(struct paint_state *state)
- {
- struct commit *commit = prio_queue_get(&state->queue);
+ static void paint_count_update(struct paint_state *state,
@@ commit-reach.c: static struct commit *paint_queue_get(struct paint_state *state)
-
- commit->object.flags &= ~ENQUEUED;
-
+ * still include this commit, so the last non-stale commit
+ * sees a non-zero count and is returned for processing.
+ */
- if (!state->parent1_count && !state->parent2_count &&
- !state->mb_candidate_count)
- return NULL;
@@ commit-reach.c: static struct commit *paint_queue_get(struct paint_state *state)
+ /* one side is exhausted */
+ if ((!state->parent1_count || !state->parent2_count) &&
+ state->gen_ordered &&
-+ commit_graph_generation(commit) < GENERATION_NUMBER_INFINITY)
++ commit_graph_generation(commit) < state->topo_ceiling)
+ return NULL;
+ }

paint_count_update(state, commit->object.flags, -1); return commit;
+@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
+ timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
+ struct commit_list **tail = result;
+
++ state.topo_ceiling = corrected_commit_dates_enabled(r)
++ ? GENERATION_NUMBER_INFINITY
++ : GENERATION_NUMBER_V1_MAX;
+ if (!min_generation && !corrected_commit_dates_enabled(r)) {
+ state.queue.compare = compare_commits_by_commit_date;
+ state.gen_ordered = 0;
+@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
+ */
+ if (!(mb_flags & MERGE_BASE_FIND_ALL) &&
+ state.gen_ordered &&
+- generation < GENERATION_NUMBER_INFINITY)
++ generation < state.topo_ceiling)
+ break;
+ }
+ /* Mark parents of a found merge stale */

## t/t6600-test-reach.sh ##
@@ t/t6600-test-reach.sh: test_expect_success 'in_merge_bases_many:self' '
9: cd3273eb15 ! 9: 9a0f4df49a commit-reach: move min_generation check into paint_queue_get()

     @@ commit-reach.c: struct paint_state {
       	int gen_ordered;
      +	timestamp_t min_generation;
      +	timestamp_t last_gen;
     + 	timestamp_t topo_ceiling;
       };
       
     - static void paint_count_update(struct paint_state *state,
      @@ commit-reach.c: static void paint_queue_put(struct paint_state *state,
       static struct commit *paint_queue_get(struct paint_state *state)
       {
     @@ commit-reach.c: static void paint_queue_put(struct paint_state *state,
      +	if (generation < state->min_generation)
      +		return NULL;
       
     - 	if (!state->mb_candidate_count) {
     - 		/* only stale entries remain */
     + 	/*
     + 	 * Check exit condition before decrementing: the counters
      @@ commit-reach.c: static struct commit *paint_queue_get(struct paint_state *state)
       		/* one side is exhausted */
       		if ((!state->parent1_count || !state->parent2_count) &&
       		    state->gen_ordered &&
     --		    commit_graph_generation(commit) < GENERATION_NUMBER_INFINITY)
     -+		    generation < GENERATION_NUMBER_INFINITY)
     +-		    commit_graph_generation(commit) < state->topo_ceiling)
     ++		    generation < state->topo_ceiling)
       			return NULL;
       	}
       
     @@ commit-reach.c: static int paint_down_to_common(struct repository *r,
       
      +	state.min_generation = min_generation;
      +	state.last_gen = GENERATION_NUMBER_INFINITY;
     - 	if (!min_generation && !corrected_commit_dates_enabled(r)) {
     - 		state.queue.compare = compare_commits_by_commit_date;
     - 		state.gen_ordered = 0;
     + 	state.topo_ceiling = corrected_commit_dates_enabled(r)
     + 		? GENERATION_NUMBER_INFINITY
     + 		: GENERATION_NUMBER_V1_MAX;
      @@ commit-reach.c: static int paint_down_to_common(struct repository *r,
       	while ((commit = paint_queue_get(&state))) {
       		struct commit_list *parents;
     @@ commit-reach.c: static int paint_down_to_common(struct repository *r,
       				 */
       				if (!(mb_flags & MERGE_BASE_FIND_ALL) &&
       				    state.gen_ordered &&
     --				    generation < GENERATION_NUMBER_INFINITY)
     -+				    state.last_gen < GENERATION_NUMBER_INFINITY)
     +-				    generation < state.topo_ceiling)
     ++				    state.last_gen < state.topo_ceiling)
       					break;
       			}
       			/* Mark parents of a found merge stale */

10: b655b24dc0 ! 10: 677e25077c commit-reach: remove commit-date ordering fallback
@@ Commit message
v2 graph, this series: 3,887 0.01 s

With generation ordering always active, the existing min_generation
- check in paint_queue_get() correctly identifies when the walk has
- reached the finite generation region. The date ordering fallback
- broke this invariant: a commit could have a finite topo level
- while the queue was date-ordered, causing the early exit to fire
- before all merge bases were found.
+ check in paint_queue_get() can safely terminate once the walk
+ crosses below the caller's generation floor. The date ordering
+ fallback broke this invariant: a commit could have a finite topo
+ level while the queue was date-ordered, causing the early exit to
+ fire before all merge bases were found.

- For v1 commit-graphs where generation numbers saturate at
- GENERATION_NUMBER_V1_MAX, introduce a topological ceiling that
- the early exit gates compare against instead of
- GENERATION_NUMBER_INFINITY. This ensures saturated commits are
- treated as unordered, preventing premature termination when
- generation values are unreliable.
+ With the fallback removed, gen_ordered is always true and can be
+ dropped. The topo_ceiling field (introduced earlier) already
+ handles V1_MAX saturation, so the early exit gates need no further
+ changes.

## Documentation/technical/paint-down-to-common.adoc ##
-@@ Documentation/technical/paint-down-to-common.adoc: ancestor is necessarily redundant.
- INFINITY and finite generation regions
- --------------------------------------
-
--The properties in this section assume generation-number ordering (the
--default comparator). They do NOT hold when the date-ordering fallback
--is active -- see <<date-ordering-fallback>>.
--
- The commit-graph stores a generation number for each commit.
- Commits not in the commit-graph have generation
- GENERATION_NUMBER_INFINITY. The graph is closed under
-@@ Documentation/technical/paint-down-to-common.adoc: traversal: children are always visited before their parents. This
- means that paint on already-visited commits is final -- no future
- traversal step can add paint to them.
-
--In the INFINITY region, commit-date ordering can violate this: a
--parent with a later date can be visited before a child with an earlier
--date. Paint flags are therefore NOT final at visit time, and a
--commit visited with only one side's paint may later gain the other.
-+In the INFINITY region, all commits share the same generation
-+value, so the queue breaks ties by commit date. This can violate
-+topological ordering: a parent with a later date can be visited
-+before a child with an earlier date. Paint flags are therefore
-+NOT final at visit time, and a commit visited with only one
-+side's paint may later gain the other.
-
- Paint flags are only added, never removed. Since each flag can be set
- at most once per commit, the number of times a commit can be
-@@ Documentation/technical/paint-down-to-common.adoc: descendant of this candidate (generation ordering guarantees
- children are visited first), so it cannot be redundant and the walk
- can stop immediately.
+@@ Documentation/technical/paint-down-to-common.adoc: candidate (generation ordering guarantees children are visited
+ first), so it cannot be redundant and the walk can stop
+ immediately.

-This optimization is NOT safe when the date-ordering fallback is -active, because commit-date order can visit a deeper ancestor
@@ Documentation/technical/paint-down-to-common.adoc: descendant of this candidate
-
-When the commit-graph has generation numbers v1 and no
-generation floor is specified, topological ordering
--(via generation numbers) is disabled. Topological levels are
+-(via generation numbers) is disabled. Topological levels are
-correct but unbalanced -- ordering by such generation numbers
-can sometimes cause the walk to detour too far before finding
--merge bases. Commit-date ordering typically reaches them in
+-merge bases. Commit-date ordering typically reaches them in
-fewer steps -- see this change for more details:
-
- 091f4cf3 (commit: don't use generation numbers if not needed,
@@ Documentation/technical/paint-down-to-common.adoc: descendant of this candidate
-of both worlds and do not need this fallback.
-
-For v1, paint_down_to_common() falls back to pure commit-date
--ordering via compare_commits_by_commit_date. Because commit +-ordering via compare_commits_by_commit_date. Because commit
-dates are not monotonic (clock skew, rebases, etc.), the queue
-may visit commits out of topological order.
-
@@ commit-reach.c: struct paint_state {
- int gen_ordered;
timestamp_t min_generation;
timestamp_t last_gen;
-+ timestamp_t topo_ceiling;
- };
-
- static void paint_count_update(struct paint_state *state,
+ timestamp_t topo_ceiling;
@@ commit-reach.c: static struct commit *paint_queue_get(struct paint_state *state)

/* one side is exhausted */
if ((!state->parent1_count || !state->parent2_count) &&
- state->gen_ordered &&
-- generation < GENERATION_NUMBER_INFINITY)
-+ generation < state->topo_ceiling)
+ generation < state->topo_ceiling)
return NULL;
}
-
@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
enum merge_base_flags mb_flags, struct commit_list **result)
@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
+ /*
+ * Generation ordering is required for the side-exhaustion and
+ * single-result early exits, which rely on topological traversal
-+ * order (children visited before parents) in the finite region.
++ * order (children visited before parents) in the ordered region.
+ */
struct paint_state state = {
- .queue = { compare_commits_by_gen_then_commit_date },
@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
struct commit *commit;
int i;
@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
-
- state.min_generation = min_generation;
- state.last_gen = GENERATION_NUMBER_INFINITY;
+ state.topo_ceiling = corrected_commit_dates_enabled(r)
+ ? GENERATION_NUMBER_INFINITY
+ : GENERATION_NUMBER_V1_MAX;
- if (!min_generation && !corrected_commit_dates_enabled(r)) {
- state.queue.compare = compare_commits_by_commit_date;
- state.gen_ordered = 0;
- }
-+ state.topo_ceiling = corrected_commit_dates_enabled(r)
-+ ? GENERATION_NUMBER_INFINITY
-+ : GENERATION_NUMBER_V1_MAX;

one->object.flags |= PARENT1;
if (!n) {
@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
*/
if (!(mb_flags & MERGE_BASE_FIND_ALL) &&
- state.gen_ordered &&
-- state.last_gen < GENERATION_NUMBER_INFINITY)
-+ state.last_gen < state.topo_ceiling)
+ state.last_gen < state.topo_ceiling)
break;
}
- /* Mark parents of a found merge stale */

## t/t6600-test-reach.sh ##
@@ t/t6600-test-reach.sh: test_expect_success 'get_merge_bases_many:infinity-both-sides' '
@@ t/t6600-test-reach.sh: test_expect_success 'merge-base --all commit-walk steps'
'

test_expect_success 'merge-base --all with clock skew (side-exhaustion)' '
-- # Verify correct merge base under clock skew. se-D (the
-- # merge base) has a higher date than its child se-C.
-- # Generation ordering ensures se-C is visited before se-D,
-- # so P1 paint propagates correctly and se-D is found.
-+ # Verify that the merge base is computed correctly even
-+ # when commits have non-monotonic commit dates.
+@@ t/t6600-test-reach.sh: test_expect_success 'merge-base --all with clock skew (side-exhaustion)' '
>input &&
git rev-parse se-D >expect &&
run_all_modes git merge-base --all se-A se-B &&
@@ t/t6600-test-reach.sh: test_expect_success 'merge-base --all commit-walk steps'
'

test_expect_success 'merge-base --all with clock skew and redundant ancestor (side-exhaustion)' '
-- # Verify correct merge base when clock skew could cause a
-- # too-deep result. MB1 is the correct merge base; MB2 is
-- # its ancestor. A reaches MB2 via E (high date) and MB1
-- # via C (low date). Generation ordering ensures C is
-- # visited before side-exhaustion fires, so MB1 is found
-- # and remove_redundant correctly discards MB2.
-+ # Verify that the correct merge base is found even when
-+ # non-monotonic commit dates could cause a redundant
-+ # ancestor to be visited first.
+@@ t/t6600-test-reach.sh: test_expect_success 'merge-base --all with clock skew and redundant ancestor (si
>input &&
git rev-parse se2-MB1 >expect &&
run_all_modes git merge-base --all se2-A se2-B &&

gitgitgadget

From: Kristofer Karlsson <[email protected]>

Add a technical document describing the paint_down_to_common() algorithm used for merge-base computation, covering the paint walk, generation number regions, and termination conditions.

---
 Documentation/Makefile                        |   1 +
 Documentation/technical/meson.build           |   1 +
 .../technical/paint-down-to-common.adoc       | 174 ++++++++++++++++++
 commit-reach.c                                |   6 +-
 4 files changed, 181 insertions(+), 1 deletion(-)
 create mode 100644 Documentation/technical/paint-down-to-common.adoc

index 2699f0b24a..f8dea4b395 100644
@@ -129,6 +129,7 @@ TECH_DOCS += technical/long-running-process-protocol
 TECH_DOCS += technical/multi-pack-index
 TECH_DOCS += technical/packfile-uri
 TECH_DOCS += technical/pack-heuristics
+TECH_DOCS += technical/paint-down-to-common
 TECH_DOCS += technical/parallel-checkout
 TECH_DOCS += technical/partial-clone
 TECH_DOCS += technical/platform-support

index ec07088c57..9ce11d5e48 100644
@@ -18,6 +18,7 @@ articles = [
   'multi-pack-index.adoc',
   'packfile-uri.adoc',
   'pack-heuristics.adoc',
+  'paint-down-to-common.adoc',
   'parallel-checkout.adoc',
   'partial-clone.adoc',
   'platform-support.adoc',

index b53c6b1cdf..8541264136 100644
@@ -96,7 +96,11 @@ static struct commit *nonstale_queue_get_dedup(struct nonstale_queue *queue)
 	return commit;
 }
 
-/* all input commits in one and twos[] must have been parsed! */
+/*
+ * See Documentation/technical/paint-down-to-common.adoc
+ *
+ * All input commits in one and twos[] must have been parsed!
+ */
 static int paint_down_to_common(struct repository *r,
 				struct commit *one, int n,
 				struct commit **twos,

gitgitgadget

From: Kristofer Karlsson <[email protected]>

test_trace2_data is a bare grep that silently exits on failure. Add a more informative variant that verifies the event appears exactly once and reports what went wrong: key not found, multiple entries, or value mismatch. Diagnostics go to FD 4 like test_grep.

Before (value mismatch):

  $ test_trace2_data status count/changed 999 <trace2.txt
  $ echo $?
  1
  (no output)

After:

  $ test_trace2_data_singular status count/changed 999 <trace2.txt
  error: trace2 data 'status/count/changed'
    expected: 999
    actual:   0

---
 t/test-lib-functions.sh | 35 +++++++++++++++++++++++++++++++++++
 1 file changed, 35 insertions(+)

index 809c662124..8c6d327b03 100644
@@ -1996,6 +1996,41 @@ test_trace2_data () {
 	grep -e '"category":"'"$1"'","key":"'"$2"'","value":"'"$3"'"'
 }
 
+# Check that the given trace2 data event has the expected value and
+# appears exactly once.  Produces a diagnostic on failure.
+#
+#	test_trace2_data_singular <category> <key> <value> [<label>]
+test_trace2_data_singular () {
+	local category="$1" key="$2" expect_val="$3"
+	local label_suffix="${4:+ [$4]}"
+	local kv_pattern='"category":"'"$category"'","key":"'"$key"'","value":"\([^"]*\)"'
+	local actual
+
+	actual=$(sed -n "s|.*${kv_pattern}.*|\1|p") &&
+
+	if test -z "$actual"
+	then
+		echo >&4 "error: trace2 data '$category/$key'$label_suffix not found"
+		return 1
+	fi &&
+
+	case "$actual" in
+	*"$LF"*)
+		echo >&4 "error: trace2 data '$category/$key'$label_suffix has multiple entries, expected 1"
+		printf '%s\n' "$actual" | sed 's/^/  actual:   /' >&4
+		return 1
+		;;
+	esac &&
+
+	if test "$actual" != "$expect_val"
+	then
+		echo >&4 "error: trace2 data '$category/$key'$label_suffix"
+		echo >&4 "  expected: $expect_val"
+		echo >&4 "  actual:   $actual"
+		return 1
+	fi
+}
+
 # Given a GIT_TRACE2_EVENT log over stdin, writes to stdout a list of URLs
 # sent to git-remote-https child processes.
 test_remote_https_urls() {

gitgitgadget

From: Elijah Newren <[email protected]>

Add test cases to t6600-test-reach.sh that exercise edge cases in the side-exhaustion optimization for paint_down_to_common():

- in_merge_bases_many:self: commit is both A and one of the X inputs
- get_merge_bases_many:duplicate-twos: duplicate entries in X list
- get_merge_bases_many:pending-stale: STALE transition on an already-painted commit (ps-* diamond topology)
- get_merge_bases_many:infinity-both-sides: both tips outside the commit-graph with non-monotonic dates (pi-* topology)

---
 t/t6600-test-reach.sh | 110 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 110 insertions(+)

index 019fed9f5e..a113adfc8a 100755
@@ -85,6 +85,61 @@ test_expect_success 'setup' '
 	git branch -f skew-P2 "$skew_P2" &&
 	git tag skew-M2 "$skew_M2" &&
 
+	# Build a small side topology to exercise the (PARENT1|PARENT2) ->
+	# (PARENT1|PARENT2|STALE) transition in paint_down_to_common(); the
+	# 10x10 grid above does not exercise it because no merge-base candidate
+	# there is a descendant of another, so STALE never reaches a
+	# still-pending candidate.
+	#
+	#       ps-X
+	#       /|\
+	#      / | \
+	#   ps-Z ps-B ps-W
+	#     |  / \  |
+	#     | /   \ |
+	#     |/     \|
+	#   ps-T1   ps-T2
+	#
+	# where ps-T1=merge(ps-Z,ps-B), ps-T2=merge(ps-W,ps-B), so
+	# merge-base(ps-T1,ps-T2) = ps-B.  During the walk, ps-X transitions
+	# to (PARENT1|PARENT2) via ps-Z and ps-W before ps-B is dequeued;
+	# then the STALE-walk from ps-B transitions ps-X to
+	# (PARENT1|PARENT2|STALE).
+	git checkout --orphan ps-orphan &&
+	test_commit ps-X &&
+	git checkout -b ps-B-br ps-X && test_commit ps-B &&
+	git checkout -b ps-Z-br ps-X && test_commit ps-Z &&
+	git checkout -b ps-W-br ps-X && test_commit ps-W &&
+	git checkout -b ps-T1 ps-Z &&
+	git merge --no-ff -m ps-T1 ps-B &&
+	git checkout -b ps-T2 ps-W &&
+	git merge --no-ff -m ps-T2 ps-B &&
+
+	# Build a side topology that lives entirely outside the half
+	# commit-graph and has non-monotonic commit dates, to exercise the
+	# INFINITY-gate in paint_down_to_common.  With both tips outside
+	# the graph, generation is INFINITY and the queue falls back to
+	# commit-date order, which here is non-monotonic.
+	#
+	#   pi-X (date 500, PARENT1 tip) --> pi-P, pi-D
+	#   pi-D (date 480) --> pi-C
+	#   pi-C (date 200) --> pi-B
+	#   pi-B (date 100, PARENT2 tip) --> pi-P
+	#   pi-P (date 450, root)
+	#
+	# merge-base(pi-X, pi-B) = pi-B (it is an ancestor of pi-X and is
+	# itself one of the queried tips).
+	git checkout --orphan pi-orphan &&
+	test_commit --date "@450 +0000" pi-P &&
+	test_commit --date "@100 +0000" pi-B &&
+	test_commit --date "@200 +0000" pi-C &&
+	test_commit --date "@480 +0000" pi-D &&
+	GIT_AUTHOR_DATE="@500 +0000" GIT_COMMITTER_DATE="@500 +0000" \
+		git commit-tree -p pi-D -p pi-P -m pi-X pi-D^{tree} >pi-X-oid &&
+	pi_x="$(cat pi-X-oid)" &&
+	git branch -f pi-X-br "$pi_x" &&
+	git tag pi-X "$pi_x" &&
+
 	git commit-graph write --reachable &&
 	mv .git/objects/info/commit-graph commit-graph-full &&
 	chmod u+w commit-graph-full &&

@@ -182,6 +237,16 @@ test_expect_success 'in_merge_bases_many:miss-heuristic' '
 	test_all_modes in_merge_bases_many
 '
 
+test_expect_success 'in_merge_bases_many:self' '
+	cat >input <<-\EOF &&
+	A:commit-6-8
+	X:commit-5-9
+	X:commit-6-8
+	EOF
+	echo "in_merge_bases_many(A,X):1" >expect &&
+	test_all_modes in_merge_bases_many
+'
+
 test_expect_success 'is_descendant_of:hit' '
 	cat >input <<-\EOF &&
 	A:commit-5-7

@@ -219,6 +284,51 @@ test_expect_success 'get_merge_bases_many' '
 	test_all_modes get_merge_bases_many
 '
 
+test_expect_success 'get_merge_bases_many:duplicate-twos' '
+	cat >input <<-\EOF &&
+	A:commit-5-7
+	X:commit-4-8
+	X:commit-4-8
+	X:commit-6-6
+	X:commit-6-6
+	X:commit-8-3
+	EOF
+	{
+		echo "get_merge_bases_many(A,X):" &&
+		git rev-parse commit-5-6 \
+			      commit-4-7 | sort
+	} >expect &&
+	test_all_modes get_merge_bases_many
+'
+
+test_expect_success 'get_merge_bases_many:pending-stale' '
+	# Exercises the (PARENT1|PARENT2) -> (...|STALE) transition path in
+	# paint_down_to_common().  See the topology comment in the setup test.
+	cat >input <<-\EOF &&
+	A:ps-T1
+	X:ps-T2
+	EOF
+	{
+		echo "get_merge_bases_many(A,X):" &&
+		git rev-parse ps-B
+	} >expect &&
+	test_all_modes get_merge_bases_many
+'
+
+test_expect_success 'get_merge_bases_many:infinity-both-sides' '
+	# Exercises the push-time INFINITY-gate in paint_down_to_common().  See
+	# the pi-* topology comment in the setup test.
+	cat >input <<-\EOF &&
+	A:pi-X
+	X:pi-B
+	EOF
+	{
+		echo "get_merge_bases_many(A,X):" &&
+		git rev-parse pi-B
+	} >expect &&
+	test_all_modes get_merge_bases_many
+'
+
 test_expect_success 'reduce_heads' '
 	cat >input <<-\EOF &&
 	X:commit-1-10

gitgitgadget

From: Kristofer Karlsson <[email protected]>

Add t6099 to test the case where multiple merge-base candidates exist and one is an ancestor of another. This exercises the side-exhaustion optimization in paint_down_to_common together with the remove_redundant safety net in get_merge_bases_many_0.

---
 t/meson.build                         |  1 +
 t/t6099-merge-base-side-exhaustion.sh | 82 +++++++++++++++++++++++++++
 2 files changed, 83 insertions(+)
 create mode 100755 t/t6099-merge-base-side-exhaustion.sh

index a25f37d2f5..655c94f860 100644
@@ -795,6 +795,7 @@ integration_tests = [
   't6041-bisect-submodule.sh',
   't6050-replace.sh',
   't6060-merge-index.sh',
+  't6099-merge-base-side-exhaustion.sh',
   't6100-rev-list-in-order.sh',
   't6101-rev-parse-parents.sh',
   't6102-rev-list-unexpected-objects.sh',

gitgitgadget

From: Kristofer Karlsson <[email protected]>

Add a step counter and trace2_data_intmax() call so that the number of commits visited during the paint walk is observable via GIT_TRACE2_EVENT. This provides a way to measure the impact of future optimizations without relying on wall-clock benchmarks alone.

Some step counts already vary across commit-graph modes (e.g. in_merge_bases_many:self) because the pre-existing min_generation optimization short-circuits the walk when generation data is available.

---
 commit-reach.c        |  5 +++++
 t/t6600-test-reach.sh | 44 ++++++++++++++++++++++++++++++-------------
 2 files changed, 36 insertions(+), 13 deletions(-)

index 8541264136..d59e76a2e2 100644
@@ -11,6 +11,7 @@
 #include "tag.h"
 #include "commit-reach.h"
 #include "ewah/ewok.h"
+#include "trace2.h"
 
 /* Remember to update object flag allocation in object.h */
 #define PARENT1		(1u<<16)

@@ -113,6 +114,7 @@ static int paint_down_to_common(struct repository *r,
 	};
 	int i;
 	int gen_ordered = 1;
+	int steps = 0;
 	timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
 	struct commit_list **tail = result;
 

@@ -138,6 +140,7 @@ static int paint_down_to_common(struct repository *r,
 		struct commit_list *parents;
 		int flags;
 		timestamp_t generation = commit_graph_generation(commit);
+		steps++;
 
 		if (min_generation && generation > last_gen)
 			BUG("bad generation skip %"PRItime" > %"PRItime" at %s",

@@ -194,6 +197,8 @@ static int paint_down_to_common(struct repository *r,
 	}
 
 	clear_nonstale_queue(&queue);
+	trace2_data_intmax("paint_down_to_common", r,
+			   "steps", steps);
 	commit_list_sort_by_date(result);
 	return 0;
 }

gitgitgadget

From: Kristofer Karlsson <[email protected]>

Add topologies and tests exercising paint_down_to_common() under clock skew, where commit-date ordering (v1 commit-graph without corrected commit dates) violates the topological invariant that children are dequeued before parents:

- se-*: side-exhaustion fires too early when one paint side fully drains from the queue while a low-date ancestor on the other side is still queued

- se2-*: side-exhaustion returns a too-deep merge base because the correct (closer) base never receives both paint sides

Also add step counts to the edge-case tests from the previous commit, a mixed finite/INFINITY generation topology exercising the transition from INFINITY-generation commits to graph-backed commits, and step counts for the grid-based merge-base test.

---
 t/t6600-test-reach.sh | 93 ++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 91 insertions(+), 2 deletions(-)

index c0ac90680e..2a6c7c656e 100755
@@ -140,6 +140,48 @@ test_expect_success 'setup' '
 	git branch -f pi-X-br "$pi_x" &&
 	git tag pi-X "$pi_x" &&
 
+	# Clock-skew topology for side-exhaustion testing.
+	# D is the correct merge base but has a higher committer date
+	# than C (its child).  With date ordering, D would be dequeued
+	# before C, causing side-exhaustion to fire too early.
+	# Generation ordering prevents this by visiting children
+	# before parents regardless of dates.
+	#
+	#   se-A (date 7000) --> se-C (date 3000) --> se-D (date 5000) --> se-root (date 4000)
+	#   se-B (date 6000) --> se-D
+	#
+	se_root=$(skew_commit 4000 se-root) &&
+	se_D=$(skew_commit 5000 se-D -p "$se_root") &&
+	se_C=$(skew_commit 3000 se-C -p "$se_D") &&
+	se_A=$(skew_commit 7000 se-A -p "$se_C") &&
+	se_B=$(skew_commit 6000 se-B -p "$se_D") &&
+	git branch -f se-A "$se_A" &&
+	git branch -f se-B "$se_B" &&
+	git tag se-D "$se_D" &&
+
+	# Clock-skew topology with redundant ancestor for
+	# side-exhaustion testing.  MB1 is the correct merge base;
+	# MB2 is its parent.  A reaches MB2 via E (high date) and
+	# MB1 via C (low date).  B reaches MB1 via D.  With date
+	# ordering, side-exhaustion would fire before C is dequeued,
+	# missing MB1.  Generation ordering ensures both are found.
+	#
+	#   se2-A (date 8000) --> se2-C (date 2000) --> se2-MB1 (date 5000) --> se2-MB2 (date 4000) --> se2-root (date 1000)
+	#   se2-A              --> se2-E (date 6500) --> se2-MB2
+	#   se2-B (date 7000) --> se2-D (date 6000) --> se2-MB1
+	#
+	se2_root=$(skew_commit 1000 se2-root) &&
+	se2_MB2=$(skew_commit 4000 se2-MB2 -p "$se2_root") &&
+	se2_MB1=$(skew_commit 5000 se2-MB1 -p "$se2_MB2") &&
+	se2_C=$(skew_commit 2000 se2-C -p "$se2_MB1") &&
+	se2_D=$(skew_commit 6000 se2-D -p "$se2_MB1") &&
+	se2_E=$(skew_commit 6500 se2-E -p "$se2_MB2") &&
+	se2_A=$(skew_commit 8000 se2-A -p "$se2_C" -p "$se2_E") &&
+	se2_B=$(skew_commit 7000 se2-B -p "$se2_D") &&
+	git branch -f se2-A "$se2_A" &&
+	git branch -f se2-B "$se2_B" &&
+	git tag se2-MB1 "$se2_MB1" &&
+
 	git commit-graph write --reachable &&
 	mv .git/objects/info/commit-graph commit-graph-full &&
 	chmod u+w commit-graph-full &&

@@ -323,7 +365,8 @@ test_expect_success 'get_merge_bases_many:pending-stale' '
 		echo "get_merge_bases_many(A,X):" &&
 		git rev-parse ps-B
 	} >expect &&
-	test_all_modes get_merge_bases_many
+	test_all_modes get_merge_bases_many &&
+	test_paint_down_steps 6 6 6 6
 '
 
 test_expect_success 'get_merge_bases_many:infinity-both-sides' '

@@ -337,7 +380,34 @@ test_expect_success 'get_merge_bases_many:infinity-both-sides' '
 		echo "get_merge_bases_many(A,X):" &&
 		git rev-parse pi-B
 	} >expect &&
-	test_all_modes get_merge_bases_many
+	test_all_modes get_merge_bases_many &&
+	test_paint_down_steps 5 5 5 5
+'
+
+test_expect_success 'setup mixed finite/INFINITY topology' '
+	# Create a commit outside all saved commit-graph files so it always
+	# has INFINITY generation, while its parent (ps-X) is in the graph
+	# with a finite generation. Use the ps-* orphan topology so we do
+	# not pollute the grid-based rev-list tests.
+	git checkout ps-X &&
+	test_env GIT_TEST_COMMIT_GRAPH= test_commit pm-INF
+'
+
+test_expect_success 'get_merge_bases_many:mixed-finite-infinity' '
+	# One tip (pm-INF) is outside the commit-graph with INFINITY
+	# generation; the other (ps-B) is in the graph with finite
+	# generation. The walk starts in the INFINITY region and crosses
+	# into the finite region where side-exhaustion can fire.
+	cat >input <<-\EOF &&
+	A:pm-INF
+	X:ps-B
+	EOF
+	{
+		echo "get_merge_bases_many(A,X):" &&
+		git rev-parse ps-X
+	} >expect &&
+	test_all_modes get_merge_bases_many &&
+	test_paint_down_steps 3 3 3 3
 '
 
 test_expect_success 'merge-base --all commit-walk steps' '

@@ -347,6 +417,25 @@ test_expect_success 'merge-base --all commit-walk steps' '
 	test_paint_down_steps 81 80 81 81
 '
 
+test_expect_success 'merge-base --all with clock skew (side-exhaustion)' '
+	# Verify that the merge base is computed correctly even
+	# when commits have non-monotonic commit dates.
+	>input &&
+	git rev-parse se-D >expect &&
+	run_all_modes git merge-base --all se-A se-B &&
+	test_paint_down_steps 6 4 6 6
+'
+
+test_expect_success 'merge-base --all with clock skew and redundant ancestor (side-exhaustion)' '
+	# Verify that the correct merge base is found even when
+	# non-monotonic commit dates could cause a redundant
+	# ancestor to be visited first.
+	>input &&
+	git rev-parse se2-MB1 >expect &&
+	run_all_modes git merge-base --all se2-A se2-B &&
+	test_paint_down_steps 8 7 8 8
+'
+
 test_expect_success 'reduce_heads' '
 	cat >input <<-\EOF &&
 	X:commit-1-10

gitgitgadget

From: Kristofer Karlsson <[email protected]>

Add a paint_state struct for use by paint_down_to_common() that wraps a prio_queue with per-side commit counters. Each non-stale queued commit occupies exactly one counter bucket based on its paint flags: PARENT1-only, PARENT2-only, or both sides (a pending merge-base candidate).

The counters are maintained by paint_count_update() which adjusts the appropriate bucket by a signed delta. An exhaustive switch on the paint+stale bits documents all valid flag combinations in one place.

Convert paint_down_to_common() to use paint_state. The loop now drains the queue via paint_queue_get() which returns NULL when all counters reach zero, replacing the old pointer-based termination (max_nonstale). This is equivalent behavior -- both conditions detect that no non-stale entries remain.

paint_queue_get() uses a "pop first" form: it dequeues a commit, then checks the counters. This means the loop exits one iteration earlier than the old code in some topologies (the popped stale commit is never processed), so a few step counts drop by one.

The existing nonstale_queue is left in place for ahead_behind(), though nonstale_queue_put_dedup() and nonstale_queue_get_dedup() become unused and are removed.

---
 .../technical/paint-down-to-common.adoc       |   9 +-
 commit-reach.c                                | 112 +++++++++++++-----
 t/t6600-test-reach.sh                         |   6 +-
 3 files changed, 91 insertions(+), 36 deletions(-)

index 4bd3c2adb5..acf32bacd4 100644
@@ -93,15 +93,12 @@ re-enqueues per commit.
 Termination
 -----------
 
-The walk uses a `nonstale_queue` wrapper around `prio_queue` that
-tracks `max_nonstale`: the lowest-priority non-stale commit enqueued
-so far. Once that commit is dequeued, every remaining entry is known
-to be STALE and the loop terminates. Specifically, the main loop
+The walk tracks the number of commits of each type in the queue
+(PARENT1-only, PARENT2-only, pending merge-base). The main loop
 ends when one of the following conditions holds:
 
   1. The queue is empty.
-  2. `max_nonstale` has been dequeued, meaning the queue only contains
-     STALE entries.
+  2. The queue contains only stale entries.
   3. Generation cutoff: the dequeued commit's generation is below
      a caller-supplied `min_generation` threshold.
   4. Single result: the caller only needs one merge base, one has

index 2a6c7c656e..9f3a8f4743 100755
@@ -366,7 +366,7 @@ test_expect_success 'get_merge_bases_many:pending-stale' '
 		git rev-parse ps-B
 	} >expect &&
 	test_all_modes get_merge_bases_many &&
-	test_paint_down_steps 6 6 6 6
+	test_paint_down_steps 5 5 5 5
 '
 
 test_expect_success 'get_merge_bases_many:infinity-both-sides' '

@@ -381,7 +381,7 @@ test_expect_success 'get_merge_bases_many:infinity-both-sides' '
 		git rev-parse pi-B
 	} >expect &&
 	test_all_modes get_merge_bases_many &&
-	test_paint_down_steps 5 5 5 5
+	test_paint_down_steps 5 4 5 5
 '
 
 test_expect_success 'setup mixed finite/INFINITY topology' '

@@ -433,7 +433,7 @@ test_expect_success 'merge-base --all with clock skew and redundant ancestor (si
 	>input &&
 	git rev-parse se2-MB1 >expect &&
 	run_all_modes git merge-base --all se2-A se2-B &&
-	test_paint_down_steps 8 7 8 8
+	test_paint_down_steps 8 6 8 8
 '
 
 test_expect_success 'reduce_heads' '

gitgitgadget

From: Kristofer Karlsson <[email protected]>

Add an early termination check to paint_down_to_common() using the per-side counters introduced earlier. Once the walk enters the ordered region, terminate early when one side's exclusive count drops to zero -- no new merge-base can form without both paint sides meeting.

The check also waits for pending_merge_bases to reach zero, ensuring all merge-base candidates have been dequeued and recorded before exiting.

The optimization is gated by gen_ordered (which excludes v1 commit-graphs that use the date-ordering fallback) and by a generation check against topo_ceiling. topo_ceiling is GENERATION_NUMBER_INFINITY for v2 graphs and GENERATION_NUMBER_V1_MAX for v1 graphs, so that saturated commits are treated as unordered. Together these ensure the check only fires in the ordered region where topological ordering holds.

The same topo_ceiling boundary is applied to the existing single-result early exit so that all generation-dependent gates express the same saturation-aware boundary consistently.

Step counts measured with trace2 on git.git with commit-graph:

merge-base --all v2.0.0 v2.55.0-rc1:

    before: 72264 steps    after: 44589 steps

merge-base --all v2.55.0-rc1 v2.55.0-rc1~5:
before: 110 steps after: 7 steps

---
 .../technical/paint-down-to-common.adoc       | 25 +++++++++++++++++--
 commit-reach.c                                | 20 ++++++++++++---
 t/t6600-test-reach.sh                         |  4 +--
 3 files changed, 41 insertions(+), 8 deletions(-)

index acf32bacd4..2393bb03b6 100644
@@ -76,7 +76,11 @@ its child.
 Commits not in the commit-graph have generation INFINITY; v1
 commit-graphs saturate at V1_MAX. Both place commits in the
 unordered region. Any optimization that depends on generation
-ordering must account for this saturation boundary.
+ordering must account for this saturation boundary. The early
+exit gates compare against a topological ceiling --
+`GENERATION_NUMBER_V1_MAX` for v1 graphs and
+`GENERATION_NUMBER_INFINITY` for v2 graphs -- so that saturated
+commits are treated as unordered.
 
 With generation ordering, values in the unordered region exceed
 those in the ordered region. The walk may therefore transition

@@ -103,6 +107,9 @@ ends when one of the following conditions holds:
      a caller-supplied `min_generation` threshold.
   4. Single result: the caller only needs one merge base, one has
      been found, and the walk has entered the ordered region.
+  5. Side exhaustion: no pure PARENT1 or pure PARENT2 commits
+     remain in the queue, no pending merge-base candidates exist,
+     and the walk has entered the ordered region.
 
 Stale entry condition
 ~~~~~~~~~~~~~~~~~~~~~

@@ -113,6 +120,16 @@ existing candidates by proving one is an ancestor of another, but
 `remove_redundant()` handles that as a post-processing step, so it
 is safe to exit early.
 
+Side-exhaustion condition
+~~~~~~~~~~~~~~~~~~~~~~~~~
+A new merge-base requires commits from both sides to meet. When one
+side's exclusive counter reaches zero and there are no pending
+merge-base candidates, no future traversal step can produce a new
+candidate. This optimization only activates in the ordered region,
+where paint flags are final at visit time; in the unordered region,
+a side that appears exhausted could reappear through late paint
+propagation.
+
 Generation cutoff
 ~~~~~~~~~~~~~~~~~
 Some callers (notably `remove_redundant()`) supply a `min_generation`

@@ -158,12 +175,16 @@ ordering via `compare_commits_by_commit_date`. Because commit
 dates are not monotonic (clock skew, rebases, etc.), the queue
 may visit commits out of topological order.
 
-This disables the optimization that depends on generation ordering:
+This disables the optimizations that depend on generation ordering:
 
   - *Single result*: the first merge-base candidate found may not
     be the shallowest, because a deeper ancestor with a higher
     commit date can be dequeued first.
 
+  - *Side exhaustion*: one paint side can appear to drain from the
+    queue while commits from that side are still waiting with lower
+    dates, causing premature termination.
+
 Related documentation
 ---------------------
 

index 0f5ffec36e..7c5bbe00c3 100644
@@ -90,6 +90,7 @@ struct paint_state {
 	size_t parent2_count;
 	size_t mb_candidate_count;
 	int gen_ordered;
+	timestamp_t topo_ceiling;
 };
 
 static void paint_count_update(struct paint_state *state,

@@ -150,9 +151,17 @@ static struct commit *paint_queue_get(struct paint_state *state)
 	 * still include this commit, so the last non-stale commit
 	 * sees a non-zero count and is returned for processing.
 	 */
-	if (!state->parent1_count && !state->parent2_count &&
-	    !state->mb_candidate_count)
-		return NULL;
+	if (!state->mb_candidate_count) {
+		/* only stale entries remain */
+		if (!state->parent1_count && !state->parent2_count)
+			return NULL;
+
+		/* one side is exhausted */
+		if ((!state->parent1_count || !state->parent2_count) &&
+		    state->gen_ordered &&
+		    commit_graph_generation(commit) < state->topo_ceiling)
+			return NULL;
+	}
 
 	paint_count_update(state, commit->object.flags, -1);
 	return commit;

@@ -180,6 +189,9 @@ static int paint_down_to_common(struct repository *r,
 	timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
 	struct commit_list **tail = result;
 
+	state.topo_ceiling = corrected_commit_dates_enabled(r)
+		? GENERATION_NUMBER_INFINITY
+		: GENERATION_NUMBER_V1_MAX;
 	if (!min_generation && !corrected_commit_dates_enabled(r)) {
 		state.queue.compare = compare_commits_by_commit_date;
 		state.gen_ordered = 0;

@@ -222,7 +234,7 @@ static int paint_down_to_common(struct repository *r,
 				 */
 				if (!(mb_flags & MERGE_BASE_FIND_ALL) &&
 				    state.gen_ordered &&
-				    generation < GENERATION_NUMBER_INFINITY)
+				    generation < state.topo_ceiling)
 					break;
 			}
 			/* Mark parents of a found merge stale */

index 9f3a8f4743..23417897c8 100755
@@ -297,7 +297,7 @@ test_expect_success 'in_merge_bases_many:self' '
 	EOF
 	echo "in_merge_bases_many(A,X):1" >expect &&
 	test_all_modes in_merge_bases_many &&
-	test_paint_down_steps 45 2 25 3
+	test_paint_down_steps 45 1 25 1
 '
 
 test_expect_success 'is_descendant_of:hit' '

@@ -414,7 +414,7 @@ test_expect_success 'merge-base --all commit-walk steps' '
 	>input &&
 	git rev-parse commit-9-1 >expect &&
 	run_all_modes git merge-base --all commit-9-9 commit-9-1 &&
-	test_paint_down_steps 81 80 81 81
+	test_paint_down_steps 81 9 57 81
 '
 
 test_expect_success 'merge-base --all with clock skew (side-exhaustion)' '

gitgitgadget

From: Kristofer Karlsson <[email protected]>

Consolidate the min_generation termination condition into paint_queue_get(), alongside the existing stale-entry and side-exhaustion checks.

Move last_gen into struct paint_state so that commit_graph_generation() is called exactly once per dequeued commit and the result is shared across all termination checks and the monotonicity BUG assertion.

---
 commit-reach.c | 31 ++++++++++++++++++-------------
 1 file changed, 18 insertions(+), 13 deletions(-)

index 7c5bbe00c3..32e65a52b5 100644
@@ -90,6 +90,8 @@ struct paint_state {
 	size_t parent2_count;
 	size_t mb_candidate_count;
 	int gen_ordered;
+	timestamp_t min_generation;
+	timestamp_t last_gen;
 	timestamp_t topo_ceiling;
 };
 

@@ -140,11 +142,23 @@ static void paint_queue_put(struct paint_state *state,
 static struct commit *paint_queue_get(struct paint_state *state)
 {
 	struct commit *commit = prio_queue_get(&state->queue);
+	timestamp_t generation;
 
 	if (!commit)
 		return NULL;
 
 	commit->object.flags &= ~ENQUEUED;
+	generation = commit_graph_generation(commit);
+
+	if (state->min_generation && generation > state->last_gen)
+		BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
+		    generation, state->last_gen,
+		    oid_to_hex(&commit->object.oid));
+	state->last_gen = generation;
+
+	/* generation cutoff */
+	if (generation < state->min_generation)
+		return NULL;
 
 	/*
 	 * Check exit condition before decrementing: the counters

@@ -159,7 +173,7 @@ static struct commit *paint_queue_get(struct paint_state *state)
 		/* one side is exhausted */
 		if ((!state->parent1_count || !state->parent2_count) &&
 		    state->gen_ordered &&
-		    commit_graph_generation(commit) < state->topo_ceiling)
+		    generation < state->topo_ceiling)
 			return NULL;
 	}
 

@@ -186,9 +200,10 @@ static int paint_down_to_common(struct repository *r,
 	struct commit *commit;
 	int i;
 	int steps = 0;
-	timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
 	struct commit_list **tail = result;
 
+	state.min_generation = min_generation;
+	state.last_gen = GENERATION_NUMBER_INFINITY;
 	state.topo_ceiling = corrected_commit_dates_enabled(r)
 		? GENERATION_NUMBER_INFINITY
 		: GENERATION_NUMBER_V1_MAX;

@@ -210,18 +225,8 @@ static int paint_down_to_common(struct repository *r,
 	while ((commit = paint_queue_get(&state))) {
 		struct commit_list *parents;
 		int flags;
-		timestamp_t generation = commit_graph_generation(commit);
 		steps++;
 
-		if (min_generation && generation > last_gen)
-			BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
-			    generation, last_gen,
-			    oid_to_hex(&commit->object.oid));
-		last_gen = generation;
-
-		if (generation < min_generation)
-			break;
-
 		flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
 		if (flags == (PARENT1 | PARENT2)) {
 			if (!(commit->object.flags & RESULT)) {

@@ -234,7 +239,7 @@ static int paint_down_to_common(struct repository *r,
 				 */
 				if (!(mb_flags & MERGE_BASE_FIND_ALL) &&
 				    state.gen_ordered &&
-				    generation < state.topo_ceiling)
+				    state.last_gen < state.topo_ceiling)
 					break;
 			}
 			/* Mark parents of a found merge stale */

gitgitgadget

From: Kristofer Karlsson <[email protected]>

Remove the fallback that switched paint_down_to_common() from generation ordering to commit-date ordering when the commit-graph lacks corrected commit dates (v1 graph with topo levels only).

The fallback was added in 091f4cf3 (commit: don't use generation numbers if not needed, 2018-08-30) to avoid a performance regression on the Linux kernel repo where v1 topo levels caused "git merge-base v4.8 v4.9" to walk 636k commits instead of 167k. A side branch with a low topo level stayed in the queue behind a long chain, preventing early STALE propagation.

Side-exhaustion (added in the previous commits) solves this differently by terminating the walk as soon as one paint side empties from the queue, preventing the deep walk regardless of queue ordering. Benchmarks of "git merge-base --all v4.8 v4.9" on the Linux kernel repo show that side-exhaustion reduces the step count far below what the date-ordering fallback achieved:

steps time

  no graph, baseline:   167,413    3.25 s
  v1 graph, baseline:   167,413    0.25 s
  v2 graph, baseline:   167,441    0.29 s
  v1 graph, this series:  5,725    0.02 s
  v2 graph, this series:  3,887    0.01 s

With generation ordering always active, the existing min_generation check in paint_queue_get() can safely terminate once the walk crosses below the caller's generation floor. The date ordering fallback broke this invariant: a commit could have a finite topo level while the queue was date-ordered, causing the early exit to fire before all merge bases were found.

With the fallback removed, gen_ordered is always true and can be dropped. The topo_ceiling field (introduced earlier) already handles V1_MAX saturation, so the early exit gates need no further changes.

---
 .../technical/paint-down-to-common.adoc       | 37 -------------------
 commit-reach.c                                | 15 +++-----
 t/t6600-test-reach.sh                         |  8 ++--
 3 files changed, 10 insertions(+), 50 deletions(-)

index 2393bb03b6..c33c7ea7c1 100644
@@ -148,43 +148,6 @@ candidate (generation ordering guarantees children are visited
 first), so it cannot be redundant and the walk can stop
 immediately.
 
-This optimization is NOT safe when the date-ordering fallback is
-active, because commit-date order can visit a deeper ancestor
-before a shallower one -- see <<date-ordering-fallback>>.
-
-[[date-ordering-fallback]]
-Date-ordering fallback
-----------------------
-
-When the commit-graph has generation numbers v1 and no
-generation floor is specified, topological ordering
-(via generation numbers) is disabled. Topological levels are
-correct but unbalanced -- ordering by such generation numbers
-can sometimes cause the walk to detour too far before finding
-merge bases. Commit-date ordering typically reaches them in
-fewer steps -- see this change for more details:
-
-   091f4cf3 (commit: don't use generation numbers if not needed,
-   2018-08-30)
-
-With generation number v2 (corrected commit dates) we have the best
-of both worlds and do not need this fallback.
-
-For v1, `paint_down_to_common()` falls back to pure commit-date
-ordering via `compare_commits_by_commit_date`. Because commit
-dates are not monotonic (clock skew, rebases, etc.), the queue
-may visit commits out of topological order.
-
-This disables the optimizations that depend on generation ordering:
-
-  - *Single result*: the first merge-base candidate found may not
-    be the shallowest, because a deeper ancestor with a higher
-    commit date can be dequeued first.
-
-  - *Side exhaustion*: one paint side can appear to drain from the
-    queue while commits from that side are still waiting with lower
-    dates, causing premature termination.
-
 Related documentation
 ---------------------
 

index 32e65a52b5..ace49c0d91 100644
@@ -89,7 +89,6 @@ struct paint_state {
 	size_t parent1_count;
 	size_t parent2_count;
 	size_t mb_candidate_count;
-	int gen_ordered;
 	timestamp_t min_generation;
 	timestamp_t last_gen;
 	timestamp_t topo_ceiling;

@@ -172,7 +171,6 @@ static struct commit *paint_queue_get(struct paint_state *state)
 
 		/* one side is exhausted */
 		if ((!state->parent1_count || !state->parent2_count) &&
-		    state->gen_ordered &&
 		    generation < state->topo_ceiling)
 			return NULL;
 	}

@@ -193,9 +191,13 @@ static int paint_down_to_common(struct repository *r,
 				enum merge_base_flags mb_flags,
 				struct commit_list **result)
 {
+	/*
+	 * Generation ordering is required for the side-exhaustion and
+	 * single-result early exits, which rely on topological traversal
+	 * order (children visited before parents) in the ordered region.
+	 */
 	struct paint_state state = {
-		.queue = { compare_commits_by_gen_then_commit_date },
-		.gen_ordered = 1,
+		.queue = { compare_commits_by_gen_then_commit_date }
 	};
 	struct commit *commit;
 	int i;

@@ -207,10 +209,6 @@ static int paint_down_to_common(struct repository *r,
 	state.topo_ceiling = corrected_commit_dates_enabled(r)
 		? GENERATION_NUMBER_INFINITY
 		: GENERATION_NUMBER_V1_MAX;
-	if (!min_generation && !corrected_commit_dates_enabled(r)) {
-		state.queue.compare = compare_commits_by_commit_date;
-		state.gen_ordered = 0;
-	}
 
 	one->object.flags |= PARENT1;
 	if (!n) {

@@ -238,7 +236,6 @@ static int paint_down_to_common(struct repository *r,
 				 * descendant of this one.
 				 */
 				if (!(mb_flags & MERGE_BASE_FIND_ALL) &&
-				    state.gen_ordered &&
 				    state.last_gen < state.topo_ceiling)
 					break;
 			}

index 23417897c8..13c84e0a42 100755
@@ -381,7 +381,7 @@ test_expect_success 'get_merge_bases_many:infinity-both-sides' '
 		git rev-parse pi-B
 	} >expect &&
 	test_all_modes get_merge_bases_many &&
-	test_paint_down_steps 5 4 5 5
+	test_paint_down_steps 5 4 5 4
 '
 
 test_expect_success 'setup mixed finite/INFINITY topology' '

@@ -414,7 +414,7 @@ test_expect_success 'merge-base --all commit-walk steps' '
 	>input &&
 	git rev-parse commit-9-1 >expect &&
 	run_all_modes git merge-base --all commit-9-9 commit-9-1 &&
-	test_paint_down_steps 81 9 57 81
+	test_paint_down_steps 81 9 57 37
 '
 
 test_expect_success 'merge-base --all with clock skew (side-exhaustion)' '

@@ -423,7 +423,7 @@ test_expect_success 'merge-base --all with clock skew (side-exhaustion)' '
 	>input &&
 	git rev-parse se-D >expect &&
 	run_all_modes git merge-base --all se-A se-B &&
-	test_paint_down_steps 6 4 6 6
+	test_paint_down_steps 6 4 6 4
 '
 
 test_expect_success 'merge-base --all with clock skew and redundant ancestor (side-exhaustion)' '

@@ -433,7 +433,7 @@ test_expect_success 'merge-base --all with clock skew and redundant ancestor (si
 	>input &&
 	git rev-parse se2-MB1 >expect &&
 	run_all_modes git merge-base --all se2-A se2-B &&
-	test_paint_down_steps 8 6 8 8
+	test_paint_down_steps 8 6 8 6
 '
 
 test_expect_success 'reduce_heads' '

gitgitgadget

I am quite pleased with how this series has turned out. Not only does it provide nice speedups, I think the structure of the series is particularly nicely set up in a way that helps guide the discovery of the idea behind the optimization for others to read, documents and tests everything logically and thoroughly, and was a pleasant read.

I brought up several issues in previous versions, and this round addresses them all.

But, I just have to comment on a few things individually...

Don't think for a second that I didn't notice you murdering these double spaces. You villain! ;-)

...and now you're just toying with us. :-)

[...]

[...]

Okay, my last two range-diff comments were just jokes, but more serious now: I think you did a nice job on the re-splitting. Thanks for doing that!

That's very much appreciated, I know this has been a lot of content to review and there has been some unfortunate churn, especially around the textual sections.

Yes, well spotted -- this was unfortunate but needed I think. I realized that this document was inconsistent, so I decided to standardize on single spaces because that was the smaller change and it also aligned with other technical documents (such as commit-graph.adoc) ...

... and here I just restored your tests to their original glory, despite making the patch series as a whole feel a bit inconsistent.

Overall though, I wonder if it would be useful to codify a preference for double or single spacing after periods, even if that (obviously) does not imply we should reformat the entire code-base directly.

Thank you, writing documentation feels harder (for me) than coding, but I'm somewhat happy with the end state now :)

- Kristofer

This is a thing that is best left for "match the surrounding area" rule. As you mentioned earlier, it is not something we want to go back and churn every line to make it consistent.

Good. We can declare victory and mark the topic for 'next' now?

Thanks, both of you.

Yes, I would be very happy to have it advance to next, though I am of course biased.

Thanks,
Kristofer

Yes, I believe it's ready now.

Thanks.