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.