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)

  • text merge O(e * e * f) + O(b)

  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 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.