Kristofer Karlsson
43157175b5
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 inside rev-list, selected by the
internal --connectivity-check option. 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.
A new transfer.connectivityCheck value "incremental" selects the
new mode, 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.
Clones and pushes into an empty repository also use the full
check. Without negative revisions there is no trusted boundary,
and the incremental check would have to verify all of history
from scratch like the full check does, with extra per-commit
overhead on top. On git.git, checking 70K commits without a
boundary takes 5.3s with the full check and 9.2s with the
incremental one.
p5413 results (best 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.13s 0.01s 13.0x
800K 0.54s 0.03s 18.0x
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.13s 0.01s 13.0x
10 0.13s 0.01s 13.0x
100 0.16s 0.06s 2.7x
500 0.29s 0.25s 1.2x
3000 1.14s 1.44s 0.8x
5000 1.87s 2.39s 0.8x
10000 3.45s 5.13s 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.13s 0.01s 13.0x
10 0.13s 0.01s 13.0x
100 0.15s 0.03s 5.0x
500 0.23s 0.13s 1.8x
1000 0.34s 0.27s 1.3x
2000 0.65s 0.56s 1.2x
The advantage shrinks as more files change per commit, but
incremental stays slightly faster even at 2000 files/commit,
where every directory is touched.
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 less memory when it can prune enough 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: a commit's tree is read as a candidate when the
commit is verified, and again as a trusted parent tree when its
children are verified.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
16 lines
382 B
C
16 lines
382 B
C
#ifndef TREE_VERIFY_H
|
|
#define TREE_VERIFY_H
|
|
|
|
struct commit_list;
|
|
struct repository;
|
|
|
|
/*
|
|
* Verify trees of commits incrementally against their parents.
|
|
* Returns 0 on success, or reports an error and returns -1.
|
|
*/
|
|
int verify_commits_incremental(struct repository *repo,
|
|
struct commit_list **commits,
|
|
int exclude_promisor_objects);
|
|
|
|
#endif /* TREE_VERIFY_H */
|