[PATCH v4 0/8] commit-reach: terminate merge-base walk when one side is exhausted
- From
Kristofer Karlsson via GitGitGadget <gitgitgadget@gmail.com>
- Date
- Jun 28, 2026, 12:25 UTC
- Message-ID
- <pull.2149.v4.git.1782649547.gitgitgadget@gmail.com>
- In-Reply-To
- <pull.2149.v3.git.1782479286.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 rootIn 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 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/8, 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 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 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 | 149 ++++++++++++++ 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, 513 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-v4 Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2149/spkrka/side-exhaust-pr-v4 Pull-Request: https://github.com/gitgitgadget/git/pull/2149
Range-diff vs v3:
1: 2593866bce ! 1: 3efb095b03 Documentation/technical: add paint-down-to-common doc
@@ Documentation/technical/paint-down-to-common.adoc (new)
+ 1. The queue is empty.
+ 2. `max_nonstale` has been dequeued, meaning the queue only contains
+ 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
++ been found, and the walk has entered the finite-generation
++ region.
+
+Stale entry condition
+~~~~~~~~~~~~~~~~~~~~~
@@ Documentation/technical/paint-down-to-common.adoc (new)
+`remove_redundant()` handles that as a post-processing step, so it
+is safe to exit early.
+
++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.
++
++Single result
++~~~~~~~~~~~~~
++When only one merge base is needed and the walk is in the
++finite-generation region, 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.
++
+Related documentation
+---------------------
+
2: 9efc084850 = 2: 1a0154b406 t6600: add test cases for side-exhaustion edge cases
3: 14b0d86b93 = 3: 017bf156c5 t6099, t6600: add side-exhaustion regression tests
4: 2592264cda = 4: df3b090a2b commit-reach: add trace2 instrumentation to paint_down_to_common()
5: e82e0c72b6 ! 5: fed9f2c368 commit-reach: introduce struct paint_state with per-side counters
@@ Documentation/technical/paint-down-to-common.adoc: re-enqueued is bounded by the
- 2. `max_nonstale` has been dequeued, meaning the queue only contains
- STALE entries.
+ 2. The queue contains only stale entries.
-
- Stale entry condition
- ~~~~~~~~~~~~~~~~~~~~~
+ 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
## commit-reach.c ##
@@ commit-reach.c: static struct commit *nonstale_queue_get_dedup(struct nonstale_queue *queue)
@@ commit-reach.c: static struct commit *nonstale_queue_get_dedup(struct nonstale_q
+ */
+struct paint_state {
+ struct prio_queue queue;
-+ int p1_count;
-+ int p2_count;
-+ int pending_merge_bases;
++ size_t parent1_count;
++ size_t parent2_count;
++ size_t mb_candidate_count;
+};
+
+static void paint_count_update(struct paint_state *state,
@@ commit-reach.c: static struct commit *nonstale_queue_get_dedup(struct nonstale_q
+{
+ switch (flags & (PARENT1 | PARENT2 | STALE)) {
+ case PARENT1:
-+ state->p1_count += delta;
++ state->parent1_count += delta;
+ break;
+
+ case PARENT2:
-+ state->p2_count += delta;
++ state->parent2_count += delta;
+ break;
+
+ case PARENT1 | PARENT2:
-+ state->pending_merge_bases += delta;
++ state->mb_candidate_count += delta;
+ break;
+
+ case PARENT1 | PARENT2 | STALE:
@@ commit-reach.c: static struct commit *nonstale_queue_get_dedup(struct nonstale_q
+
+ commit->object.flags &= ~ENQUEUED;
+
-+ if (!state->p1_count && !state->p2_count &&
-+ !state->pending_merge_bases)
++ if (!state->parent1_count && !state->parent2_count &&
++ !state->mb_candidate_count)
+ return NULL;
+
+ paint_count_update(state, commit->object.flags, -1);
6: e6181bf3c1 = 6: 4db485b48a commit-reach: remove unused nonstale_queue dedup wrappers
7: f3572a8a89 ! 7: 4506780649 commit-reach: terminate merge-base walk when one paint side is exhausted
@@ Commit message
commit-reach: terminate merge-base walk when one paint side is exhausted
Add an early termination check to paint_down_to_common() using the
- per-side counters introduced earlier. Once the walk enters 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.
@@ Commit message
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
+ which is not topologically reliable. The optimization only fires
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:
@@ Commit message
## Documentation/technical/paint-down-to-common.adoc ##
@@ Documentation/technical/paint-down-to-common.adoc: ends when one of the following conditions holds:
-
- 1. The queue is empty.
- 2. The queue contains only stale entries.
-+ 3. Side exhaustion: no pure PARENT1 or pure PARENT2 commits
+ 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.
@@ Documentation/technical/paint-down-to-common.adoc: existing candidates by provin
+commit-date ordering can violate this guarantee, so the check is
+skipped.
+
- Related documentation
- ---------------------
-
+ Generation cutoff
+ ~~~~~~~~~~~~~~~~~
+ Some callers (notably `remove_redundant()`) supply a `min_generation`
## commit-reach.c ##
@@ commit-reach.c: static void paint_queue_put(struct paint_state *state,
@@ 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 (!state->parent1_count && !state->parent2_count &&
+- !state->mb_candidate_count)
- return NULL;
-+ if (!state->pending_merge_bases) {
++ if (!state->mb_candidate_count) {
+ /* only stale entries remain */
-+ if (!state->p1_count && !state->p2_count)
++ if (!state->parent1_count && !state->parent2_count)
+ return NULL;
+
+ /* one side is exhausted */
-+ if ((!state->p1_count || !state->p2_count) &&
++ if ((!state->parent1_count || !state->parent2_count) &&
+ commit_graph_generation(commit) < GENERATION_NUMBER_INFINITY)
+ 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 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 'in_merge_bases_many:self' '
8: 4b9f192d98 ! 8: 8dd15d44e6 commit-reach: move min_generation check into paint_queue_get()
@@ Commit message
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. The loop body in paint_down_to_common()
- reads state.last_gen instead of recomputing the generation number.
+ monotonicity BUG assertion.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
- ## Documentation/technical/paint-down-to-common.adoc ##
-@@ Documentation/technical/paint-down-to-common.adoc: ends when one of the following conditions holds:
- 3. 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.
-+ 4. Generation cutoff: the dequeued commit's generation is below
-+ a caller-supplied `min_generation` threshold.
-
- Stale entry condition
- ~~~~~~~~~~~~~~~~~~~~~
-@@ Documentation/technical/paint-down-to-common.adoc: 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`
-+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.
-+
- Related documentation
- ---------------------
-
-
## commit-reach.c ##
@@ commit-reach.c: struct paint_state {
- int p1_count;
- int p2_count;
- int pending_merge_bases;
+ size_t parent1_count;
+ size_t parent2_count;
+ size_t mb_candidate_count;
+ timestamp_t min_generation;
+ timestamp_t last_gen;
};
@@ commit-reach.c: static void paint_queue_put(struct paint_state *state,
commit->object.flags &= ~ENQUEUED;
+ generation = commit_graph_generation(commit);
+
-+ if (generation > state->last_gen)
++ 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));
@@ commit-reach.c: static void paint_queue_put(struct paint_state *state,
+ if (generation < state->min_generation)
+ return NULL;
- if (!state->pending_merge_bases) {
+ if (!state->mb_candidate_count) {
/* only stale entries remain */
@@ commit-reach.c: static struct commit *paint_queue_get(struct paint_state *state)
/* one side is exhausted */
- if ((!state->p1_count || !state->p2_count) &&
+ if ((!state->parent1_count || !state->parent2_count) &&
- commit_graph_generation(commit) < GENERATION_NUMBER_INFINITY)
+ generation < GENERATION_NUMBER_INFINITY)
return NULL;
@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
- timestamp_t generation = commit_graph_generation(commit);
steps++;
-- if (generation > last_gen)
+- if (min_generation && generation > last_gen)
- BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
- generation, last_gen,
- oid_to_hex(&commit->object.oid));-- gitgitgadget