mirror of
https://github.com/git/git.git
synced 2026-10-25 15:15:20 +01:00
Kristofer Karlsson
56c9056e30
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.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
156 lines
6.2 KiB
Plaintext
156 lines
6.2 KiB
Plaintext
Merge-Base Computation and paint_down_to_common()
|
|
==================================================
|
|
|
|
The function `paint_down_to_common()` in `commit-reach.c` computes merge
|
|
bases by walking the commit graph backwards from two sets of tips and
|
|
finding where their ancestry meets.
|
|
|
|
Use cases
|
|
---------
|
|
|
|
Computing merge bases is used in two different ways:
|
|
|
|
1. *Finding all merge bases* (`merge-base --all`, `merge-tree`,
|
|
`merge`, `rebase`). A merge base is a common ancestor that is
|
|
not itself an ancestor of another common ancestor.
|
|
|
|
2. *Ancestry checks* (`in_merge_bases`, used by `merge-base
|
|
--is-ancestor`, `branch -d`, `fetch`). These ask: "is commit A
|
|
an ancestor of commit B?" If a common ancestor equals one of the
|
|
inputs, that input is necessarily the only merge base -- no other
|
|
common ancestor can be both as recent and not an ancestor of it.
|
|
|
|
Both use cases share the same algorithm and implementation.
|
|
|
|
Algorithm
|
|
---------
|
|
|
|
Given a commit `one` and a set of commits `twos[]`, the walk paints
|
|
commits with two colors:
|
|
|
|
- PARENT1: reachable from `one`
|
|
- PARENT2: reachable from any commit in `twos[]`
|
|
|
|
The walk uses a priority queue ordered by generation number
|
|
(highest first), breaking ties by commit date. Each step dequeues
|
|
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]]
|
|
Topologically ordered and unordered generation regions
|
|
------------------------------------------------------
|
|
|
|
Commits fall into two regions based on whether their generation
|
|
numbers provide a topological ordering guarantee:
|
|
|
|
....
|
|
+------------------------------------------+
|
|
| Unordered region |
|
|
| generation = INFINITY or V1_MAX |
|
|
| queue order: heuristic (commit date) |
|
|
+------------------------------------------+
|
|
|
|
|
v
|
|
+------------------------------------------+
|
|
| Ordered region |
|
|
| generation = finite, unsaturated |
|
|
| queue order: topological |
|
|
+------------------------------------------+
|
|
....
|
|
|
|
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. 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
|
|
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
|
|
-----------
|
|
|
|
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. 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
|
|
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
|
|
~~~~~~~~~~~~~~~~~~~~~
|
|
Once all queued entries are stale, no new merge-base candidates can
|
|
be discovered -- that requires at least one non-stale commit from
|
|
each side meeting. Continuing the walk could still invalidate
|
|
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`
|
|
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
|
|
~~~~~~~~~~~~~
|
|
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.
|
|
|
|
Related documentation
|
|
---------------------
|
|
|
|
- `Documentation/technical/commit-graph.adoc` -- generation numbers
|
|
and the reachability closure property.
|