Scaling analysys of Merge¶
- Fetch revisions O(a)
- Common Ancestor [O(b)] O(h)
- Calculate tree merge O(c) [+ O(b) + O(d)] + O(i)
- text merge O(e * e * f) + O(b)
- Find filesystem conflicts O(c)
- Resolve filesystem conflicts O(g)
- Apply changes O(c) + O(log(d))
- Set pending merges O(1)
- Print conflicts O(g)
- Print changes O(c)
a: | revisions missing from repo: |
---|---|
b: | nodes in the revision graph: |
c: | files that differ between base and other: |
d: | number of files in the tree |
e: | number of lines in the text |
f: | number of files requiring text merge |
g: | number of conflicts (g <= c) |
h: | humber of uncommon ancestors |
i: | number of revisions between base and other |
Needs¶
- Access to revision graph proportional to number of revisions read
- Access to changed file metadata proportional to number of changes and number of intervening revisions.
- O(1) access to fulltexts
Notes¶
Multiparent deltas may offer some nice properties for performance of annotation based merging.