Scaling analysys of Merge

  1. Fetch revisions O(a)
  2. Common Ancestor [O(b)] O(h)
  3. Calculate tree merge O(c) [+ O(b) + O(d)] + O(i)
  1. Find filesystem conflicts O(c)
  2. Resolve filesystem conflicts O(g)
  3. Apply changes O(c) + O(log(d))
  4. Set pending merges O(1)
  5. Print conflicts O(g)
  6. 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 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

Notes

Multiparent deltas may offer some nice properties for performance of annotation based merging.