The full connectivity check uses rev-list to find commits
reachable from the incoming tips but not from the
already-connected side, then walks their object closure. Commit
traversal stops at the connectivity boundary, but trees and blobs
reachable from that boundary still need to be walked so they can
be marked uninteresting, allocating a struct object for each one.
On repositories where the boundary commits have large trees, the
connectivity check for small incoming changes visits and tracks
more objects than needed.
Add an alternative connectivity check that verifies incoming
commits incrementally against their parents.
The verifier processes incoming commits with ancestors first and
compares each new tree against its trusted parent trees. Entries
already seen on the trusted side are skipped by OID, so unchanged
subtrees need not remain at the same path to be recognized.
Changed subtrees are recursively compared against same-path parent
subtrees, and new subtrees without a comparison base are verified
from scratch.
See Documentation/technical/connectivity-check.adoc for the trust
invariants and detailed algorithm.
The incremental check runs as an internal
--verify-trees-incremental mode in rev-list. After the normal
revision walk identifies the incoming commits, the verifier
consumes them before the usual object traversal; any pending
non-commit tips are still handled by the existing traversal.
Partial-clone semantics are preserved: objects promised by a
promisor remote are accepted as connected, and on-demand fetching
is prevented by excluding promisor objects from traversal. The
new mode is selected by transfer.connectivityCheck=incremental,
with full remaining the default. Deepening fetches fall back to
the full check because they do not have the normal
existing-reference boundary, and traversal instead follows the
effective shallow boundary.
p5413 results (median of 3), scaling one dimension at a time.
Each fixture is a repository with a flat tree of many
directories containing 100 files each. The incoming set is a
chain of commits on top of the existing history, with each
commit changing files in different directories round-robin.
The three axes vary the total repository tree size, the number
of incoming commits, and the number of files changed per
incoming commit.
Scaling tree size (10 incoming commits, 10 files/commit):
files full incr. full/incr
5K 0.01s 0.01s 1.0x
50K 0.04s 0.01s 4.0x
200K 0.15s 0.01s 15.0x
800K 0.61s 0.03s 20.3x
The full mode must walk the trees of boundary commits, which
grows with overall tree size. Incremental still scans the
root trees, but avoids descending into unchanged subtrees,
so it grows much more slowly with repository size.
Scaling incoming commit count (200K files, 10 files/commit):
commits full incr. full/incr
1 0.14s 0.01s 14.0x
10 0.15s 0.01s 15.0x
100 0.19s 0.05s 3.8x
500 0.32s 0.27s 1.2x
3000 1.23s 1.52s 0.8x
5000 1.88s 2.43s 0.8x
10000 3.72s 5.36s 0.7x
With many commits the per-commit overhead of scanning both
the new and parent root trees accumulates and incremental
becomes slower. Breakeven is between 500 and 3000 commits
and the ratio stabilizes near 0.7x for this fixture.
Scaling files per incoming commit (200K files, 10 commits):
files/commit full incr. full/incr
1 0.14s 0.01s 14.0x
10 0.15s 0.01s 15.0x
100 0.16s 0.04s 4.0x
500 0.23s 0.14s 1.6x
1000 0.34s 0.28s 1.2x
2000 0.70s 0.63s 1.1x
Breakeven is around 1000 files/commit. At 2000 files/commit
(every directory touched), incremental remains slightly faster;
bypassing the object cache for tree reads likely helps here.
For small repositories both modes are fast enough that the
difference is difficult to measure reliably.
Selected peak RSS measurements from the same fixtures:
case full incr. ratio
200K files, 10 commits 31 MB 12 MB 0.4x
800K files, 10 commits 110 MB 26 MB 0.2x
200K files, 5000 commits 155 MB 151 MB 1.0x
Incremental uses substantially less memory when it can prune
most of the boundary tree walk. In the long-history case the
two modes visit similar object sets and memory converges.
The regression cases in the CPU benchmarks are in wall-clock
time rather than memory, primarily from scanning some trees
more than once.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Kristofer Karlsson