1
Scaling analysys of Merge
2
=========================
4
1. Fetch revisions O(a)
5
2. Common Ancestor [O(b)] **O(h)**
6
3. Calculate tree merge O(c) [+ O(b) + O(d)] **+ O(i)**
8
- text merge O(e * e * f) + O(b)
10
4. Find filesystem conflicts O(c)
11
5. Resolve filesystem conflicts O(g)
12
6. Apply changes O(c) + O(log(d))
13
7. Set pending merges O(1)
14
8. Print conflicts O(g)
17
:a: revisions missing from repo:
18
:b: nodes in the revision graph:
19
:c: files that differ between base and other:
20
:d: number of files in the tree
21
:e: number of lines in the text
22
:f: number number of files requiring text merge
23
:g: number of conflicts (g <= c)
24
:h: humber of uncommon ancestors
25
:i: number of revisions between base and other
29
- Access to revision graph proportional to number of revisions read
30
- Access to changed file metadata proportional to number of changes and number of intervening revisions.
31
- O(1) access to fulltexts
added
removed
doc/developers/merge-scaling.rst
