[PATCH v7 00/10] commit-reach: terminate merge-base walk when one side is exhausted

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

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
finite-generation 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 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 stolee@gmail.com cc: Elijah Newren newren@gmail.com cc:
Kristofer Karlsson krka@spotify.com cc: René Scharfe l.s.r@web.de cc: SZEDER
Gábor szeder.dev@gmail.com

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, t6600: add side-exhaustion regression tests
  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       | 164 ++++++++++++
 commit-reach.c                                | 160 +++++++++---
 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, 631 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: 2c78326f810173a4f3aefd8021f1e07575412481
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2149%2Fspkrka%2Fside-exhaust-pr-v7
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2149/spkrka/side-exhaust-pr-v7
Pull-Request: https://github.com/gitgitgadget/git/pull/2149

Range-diff vs v6:

  1:  5ef4f08105 !  1:  c1f303353c Documentation/technical: add paint-down-to-common doc
     @@ Documentation/technical/paint-down-to-common.adoc (new)
      +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.
     @@ Documentation/technical/paint-down-to-common.adoc (new)
      +Generation cutoff
      +~~~~~~~~~~~~~~~~~
      +Some callers (notably `remove_redundant()`) supply a `min_generation`
     -+threshold -- the minimum generation of the input commits. No merge
     -+base can have a generation below this threshold, so the walk
     -+terminates as soon as it dequeues such a commit.
     ++threshold equal to the minimum generation of the input commits.
     ++These callers only need to determine reachability among the inputs,
     ++not find deep merge bases, so the walk can safely terminate when it
     ++dequeues a commit below this threshold.
      +
      +Single result
      +~~~~~~~~~~~~~
  2:  d0ee6d062e !  2:  57ecc0b18a test-lib-functions: improve diagnostic output for trace2 data assertions
     @@ t/test-lib-functions.sh: test_trace2_data () {
      +	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
  3:  21ecf6dc34 =  3:  f857577e0c t6600: add test cases for side-exhaustion edge cases
  4:  d4ecf4b698 =  4:  e8565ce020 t6099, t6600: add side-exhaustion regression tests
  5:  9e76f5fb62 =  5:  490be76bef commit-reach: add trace2 instrumentation to paint_down_to_common()
  6:  171b3cd3ae =  6:  75d58639fc t6600: add clock-skew topologies and step counts for edge cases
  7:  92a327a94c =  7:  a1c8e89ef9 commit-reach: introduce struct paint_state with per-side counters
  8:  0d552869be =  8:  391fa07783 commit-reach: terminate merge-base walk when one paint side is exhausted
  9:  598a963375 =  9:  cd3273eb15 commit-reach: move min_generation check into paint_queue_get()
 10:  6d617da1f7 ! 10:  b655b24dc0 commit-reach: remove commit-date ordering fallback
     @@ Commit message
          while the queue was date-ordered, causing the early exit to fire
          before all merge bases were found.
      
     -    Also remove corrected_commit_dates_enabled() from commit-graph.c
     -    which has no remaining callers.
     +    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.
      
          Signed-off-by: Kristofer Karlsson <krka@spotify.com>
      
     @@ Documentation/technical/paint-down-to-common.adoc: descendant of this candidate
       ---------------------
       
      
     - ## commit-graph.c ##
     -@@ commit-graph.c: int generation_numbers_enabled(struct repository *r)
     - 	return !!first_generation;
     - }
     - 
     --int corrected_commit_dates_enabled(struct repository *r)
     --{
     --	struct commit_graph *g;
     --
     --	g = prepare_commit_graph(r);
     --	if (!g || !g->num_commits)
     --		return 0;
     --
     --	return g->read_generation_data;
     --}
     --
     - struct bloom_filter_settings *get_bloom_filter_settings(struct repository *r)
     - {
     - 	struct commit_graph *g;
     -
     - ## commit-graph.h ##
     -@@ commit-graph.h: struct commit_graph *parse_commit_graph(struct repository *r,
     -  */
     - int generation_numbers_enabled(struct repository *r);
     - 
     --/*
     -- * Return 1 if and only if the repository has a commit-graph
     -- * file and generation data chunk has been written for the file.
     -- */
     --int corrected_commit_dates_enabled(struct repository *r);
     --
     - struct bloom_filter_settings *get_bloom_filter_settings(struct repository *r);
     - 
     - enum commit_graph_write_flags {
     -
       ## commit-reach.c ##
      @@ commit-reach.c: struct paint_state {
       	size_t parent1_count;
     @@ 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 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 < GENERATION_NUMBER_INFINITY)
     ++		    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,
      -		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 < GENERATION_NUMBER_INFINITY)
     ++				    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' '

-- 
gitgitgadget