[PATCH v3 0/8] commit-reach: terminate merge-base walk when one side is exhausted

["Kristofer Karlsson via GitGitGadget" <gitgitgadget@gmail.com>]

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

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]. Patches 2-3 incorporate test cases from Elijah's branch.

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

Patch layout:

1/8 Documentation/technical: add paint-down-to-common doc 2/8 t6600: add
test cases for side-exhaustion edge cases 3/8 t6099, t6600: add
side-exhaustion regression tests 4/8 commit-reach: add trace2
instrumentation to paint_down_to_common() 5/8 commit-reach: introduce struct
paint_state with per-side counters 6/8 commit-reach: remove unused
nonstale_queue dedup wrappers 7/8 commit-reach: terminate merge-base walk
when one paint side is exhausted 8/8 commit-reach: move min_generation check
into paint_queue_get()

Benchmarks

Step counts are deterministic (measured via trace2_data_intmax added in
patch 4). 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


Changes since v2:

 * New patch 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.

 * Widened the generation-monotonicity BUG assertion to fire
   unconditionally, not only when min_generation is set. The side-exhaustion
   optimization depends on correct generation ordering, so the assertion
   should always be active. This is a behavior change: the BUG() now fires
   for any generation ordering violation, regardless of the caller.

 * 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 deterministic
   step-count assertions in t6600.

 * Expanded switch statements to multi-line format per .clang-format.

 * Used !count style throughout instead of count == 0.

 * Updated technical documentation alongside code changes.

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

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

Kristofer Karlsson (7):
  Documentation/technical: add paint-down-to-common doc
  t6099, t6600: add side-exhaustion regression tests
  commit-reach: add trace2 instrumentation to paint_down_to_common()
  commit-reach: introduce struct paint_state with per-side counters
  commit-reach: remove unused nonstale_queue dedup wrappers
  commit-reach: terminate merge-base walk when one paint side is
    exhausted
  commit-reach: move min_generation check into paint_queue_get()

 Documentation/Makefile                        |   1 +
 Documentation/technical/meson.build           |   1 +
 .../technical/paint-down-to-common.adoc       | 137 +++++++++++++
 commit-reach.c                                | 147 ++++++++++----
 t/meson.build                                 |   1 +
 t/t6099-merge-base-side-exhaustion.sh         |  82 ++++++++
 t/t6600-test-reach.sh                         | 181 ++++++++++++++++--
 7 files changed, 501 insertions(+), 49 deletions(-)
 create mode 100644 Documentation/technical/paint-down-to-common.adoc
 create mode 100755 t/t6099-merge-base-side-exhaustion.sh


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

Range-diff vs v2:

 1:  19ed743bd1 = 1:  2593866bce Documentation/technical: add paint-down-to-common doc
 2:  6151b8e0a3 = 2:  9efc084850 t6600: add test cases for side-exhaustion edge cases
 3:  90f09ecb5c = 3:  14b0d86b93 t6099, t6600: add side-exhaustion regression tests
 4:  6ade4df2ed ! 4:  2592264cda commit-reach: add trace2 instrumentation to paint_down_to_common()
     @@ Commit message
      
          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_PERF. This provides a way to measure the impact of
     +    GIT_TRACE2_EVENT. This provides a way to measure the impact of
          future optimizations without relying on wall-clock benchmarks alone.
      
          Signed-off-by: Kristofer Karlsson <krka@spotify.com>
     @@ commit-reach.c: static int paint_down_to_common(struct repository *r,
       }
      
       ## t/t6600-test-reach.sh ##
     -@@ t/t6600-test-reach.sh: test_expect_success 'get_merge_bases_many:mixed-finite-infinity' '
     - 	test_all_modes get_merge_bases_many
     +@@ t/t6600-test-reach.sh: test_expect_success 'setup' '
       '
       
     -+test_expect_success 'merge-base --all commit-walk steps' '
     -+	test_when_finished rm -rf .git/objects/info/commit-graph \
     -+		.git/objects/info/commit-graphs &&
     -+	rm -rf .git/objects/info/commit-graph \
     -+		.git/objects/info/commit-graphs &&
     -+
     -+	GIT_TRACE2_EVENT="$(pwd)/trace-none.txt" \
     -+		git merge-base --all commit-9-9 commit-9-1 >actual &&
     -+	test_trace2_data paint_down_to_common steps 81 <trace-none.txt &&
     + run_all_modes () {
     +-	test_when_finished rm -rf .git/objects/info/commit-graph &&
     +-	"$@" <input >actual &&
     +-	test_cmp expect actual &&
     +-	cp commit-graph-full .git/objects/info/commit-graph &&
     +-	"$@" <input >actual &&
     +-	test_cmp expect actual &&
     +-	cp commit-graph-half .git/objects/info/commit-graph &&
     +-	"$@" <input >actual &&
     +-	test_cmp expect actual &&
     +-	cp commit-graph-no-gdat .git/objects/info/commit-graph &&
     +-	"$@" <input >actual &&
     +-	test_cmp expect actual
     ++	graph=.git/objects/info/commit-graph &&
     ++	test_when_finished rm -rf "$graph" "${graph}s" &&
     ++	rm -f trace-mode-*.txt &&
      +
     -+	cp commit-graph-full .git/objects/info/commit-graph &&
     -+	GIT_TRACE2_EVENT="$(pwd)/trace-full.txt" \
     -+		git merge-base --all commit-9-9 commit-9-1 >actual &&
     -+	test_trace2_data paint_down_to_common steps 80 <trace-full.txt &&
     ++	for mode in none full half no-gdat
     ++	do
     ++		rm -rf "$graph" "${graph}s" &&
     ++		cp "commit-graph-${mode}" "$graph" 2>/dev/null ||
     ++		true &&
     ++		GIT_TRACE2_EVENT="$(pwd)/trace-mode-${mode}.txt" \
     ++			"$@" <input >actual &&
     ++		test_cmp expect actual || return 1
     ++	done
     + }
     + 
     + test_all_modes () {
     + 	run_all_modes test-tool reach "$@"
     + }
     + 
     ++test_paint_down_steps () {
     ++	for mode in none full half no-gdat
     ++	do
     ++		test_trace2_data paint_down_to_common steps "$1" \
     ++			<"trace-mode-${mode}.txt" || return 1
     ++		shift
     ++	done
     ++}
      +
     -+	cp commit-graph-half .git/objects/info/commit-graph &&
     -+	GIT_TRACE2_EVENT="$(pwd)/trace-half.txt" \
     -+		git merge-base --all commit-9-9 commit-9-1 >actual &&
     -+	test_trace2_data paint_down_to_common steps 81 <trace-half.txt
     + test_expect_success 'ref_newer:miss' '
     + 	cat >input <<-\EOF &&
     + 	A:commit-5-7
     +@@ t/t6600-test-reach.sh: test_expect_success 'in_merge_bases_many:self' '
     + 	X:commit-6-8
     + 	EOF
     + 	echo "in_merge_bases_many(A,X):1" >expect &&
     +-	test_all_modes in_merge_bases_many
     ++	test_all_modes in_merge_bases_many &&
     ++	test_paint_down_steps 45 2 25 3
     + '
     + 
     + test_expect_success 'is_descendant_of:hit' '
     +@@ t/t6600-test-reach.sh: 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' '
     +@@ t/t6600-test-reach.sh: 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' '
     +@@ t/t6600-test-reach.sh: test_expect_success 'get_merge_bases_many:mixed-finite-infinity' '
     + 		echo "get_merge_bases_many(A,X):" &&
     + 		git rev-parse ps-X
     + 	} >expect &&
     +-	test_all_modes get_merge_bases_many
     ++	test_all_modes get_merge_bases_many &&
     ++	test_paint_down_steps 3 3 3 3
      +'
      +
     ++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_expect_success 'reduce_heads' '
     - 	cat >input <<-\EOF &&
     - 	X:commit-1-10
 5:  f24edd45f0 ! 5:  e82e0c72b6 commit-reach: introduce struct paint_state with per-side counters
     @@ Commit message
          (max_nonstale). This is equivalent behavior -- both conditions
          detect that no non-stale entries remain.
      
     -    The existing nonstale_queue is left in place for ahead_behind().
     +    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.
      
     -    Step counts (via trace2 from the previous commit) are identical
     -    before and after this refactoring, confirming no behavioral change.
     +    The existing nonstale_queue is left in place for ahead_behind().
      
          Signed-off-by: Kristofer Karlsson <krka@spotify.com>
      
     @@ commit-reach.c: static struct commit *nonstale_queue_get_dedup(struct nonstale_q
      +
      +static struct commit *paint_queue_get(struct paint_state *state)
      +{
     -+	struct commit *commit;
     ++	struct commit *commit = prio_queue_get(&state->queue);
     ++
     ++	if (!commit)
     ++		return NULL;
     ++
     ++	commit->object.flags &= ~ENQUEUED;
      +
      +	if (!state->p1_count && !state->p2_count &&
      +	    !state->pending_merge_bases)
      +		return NULL;
      +
     -+	commit = prio_queue_get(&state->queue);
     -+	if (commit) {
     -+		commit->object.flags &= ~ENQUEUED;
     -+		paint_count_update(state, commit->object.flags, -1);
     -+	}
     ++	paint_count_update(state, commit->object.flags, -1);
      +	return commit;
      +}
      +
     @@ commit-reach.c: static int paint_down_to_common(struct repository *r,
       	trace2_data_intmax("paint_down_to_common", r,
       			   "steps", steps);
       	commit_list_sort_by_date(result);
     +
     + ## t/t6600-test-reach.sh ##
     +@@ t/t6600-test-reach.sh: 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' '
     +@@ t/t6600-test-reach.sh: 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' '
 6:  8c72f01083 = 6:  e6181bf3c1 commit-reach: remove unused nonstale_queue dedup wrappers
 7:  d84b932e5b ! 7:  f3572a8a89 commit-reach: terminate merge-base walk when one paint side is exhausted
     @@ Commit message
          once the walk enters the finite-generation region where ordering
          guarantees hold.
      
     +    Widen the existing generation-monotonicity BUG assertion to fire
     +    unconditionally, not only when min_generation is set. The
     +    side-exhaustion optimization depends on correct generation ordering,
     +    so the assertion should always be active.
     +
          Step counts measured with trace2 on git.git with commit-graph:
      
            merge-base --all v2.0.0 v2.55.0-rc1:
     @@ Documentation/technical/paint-down-to-common.adoc: existing candidates by provin
      
       ## commit-reach.c ##
      @@ commit-reach.c: 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;
     -+	struct commit *commit = prio_queue_get(&state->queue);
     + 	struct commit *commit = prio_queue_get(&state->queue);
     +@@ commit-reach.c: static struct commit *paint_queue_get(struct paint_state *state)
     + 
     + 	commit->object.flags &= ~ENQUEUED;
       
      -	if (!state->p1_count && !state->p2_count &&
      -	    !state->pending_merge_bases)
     -+	if (!commit)
     - 		return NULL;
     - 
     --	commit = prio_queue_get(&state->queue);
     --	if (commit) {
     --		commit->object.flags &= ~ENQUEUED;
     --		paint_count_update(state, commit->object.flags, -1);
     -+	commit->object.flags &= ~ENQUEUED;
     -+
     +-		return NULL;
      +	if (!state->pending_merge_bases) {
     ++		/* only stale entries remain */
      +		if (!state->p1_count && !state->p2_count)
      +			return NULL;
     -+		/*
     -+		 * Side exhaustion: a new merge-base can only form
     -+		 * when both PARENT1-only and PARENT2-only commits
     -+		 * remain in the queue. In the finite-generation
     -+		 * region the queue is ordered topologically, so
     -+		 * no future step can add paint to visited commits
     -+		 * and an exhausted side cannot reappear.
     -+		 */
     ++
     ++		/* one side is exhausted */
      +		if ((!state->p1_count || !state->p2_count) &&
      +		    commit_graph_generation(commit) < GENERATION_NUMBER_INFINITY)
      +			return NULL;
     - 	}
     -+
     -+	paint_count_update(state, commit->object.flags, -1);
     ++	}
     + 
     + 	paint_count_update(state, commit->object.flags, -1);
       	return commit;
     - }
     +@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
     + 		timestamp_t generation = commit_graph_generation(commit);
     + 		steps++;
       
     +-		if (min_generation && generation > last_gen)
     ++		if (generation > last_gen)
     + 			BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
     + 			    generation, last_gen,
     + 			    oid_to_hex(&commit->object.oid));
      
       ## t/t6600-test-reach.sh ##
     -@@ t/t6600-test-reach.sh: test_expect_success 'merge-base --all commit-walk steps' '
     - 	cp commit-graph-full .git/objects/info/commit-graph &&
     - 	GIT_TRACE2_EVENT="$(pwd)/trace-full.txt" \
     - 		git merge-base --all commit-9-9 commit-9-1 >actual &&
     --	test_trace2_data paint_down_to_common steps 80 <trace-full.txt &&
     -+	test_trace2_data paint_down_to_common steps 9 <trace-full.txt &&
     +@@ t/t6600-test-reach.sh: 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
     + '
       
     - 	cp commit-graph-half .git/objects/info/commit-graph &&
     - 	GIT_TRACE2_EVENT="$(pwd)/trace-half.txt" \
     - 		git merge-base --all commit-9-9 commit-9-1 >actual &&
     --	test_trace2_data paint_down_to_common steps 81 <trace-half.txt
     -+	test_trace2_data paint_down_to_common steps 57 <trace-half.txt
     + test_expect_success 'is_descendant_of:hit' '
     +@@ t/t6600-test-reach.sh: 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 10
       '
       
       test_expect_success 'reduce_heads' '
 -:  ---------- > 8:  4b9f192d98 commit-reach: move min_generation check into paint_queue_get()

-- 
gitgitgadget