blob: ee25c611325aa3de8565af2e70d4b1a827cd9c31 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
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)
4. Find filesystem conflicts O(c)
5. Resolve filesystem conflicts O(g)
6. Apply changes O(c) + O(log(d))
7. Set pending merges O(1)
8. Print conflicts O(g)
9. 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.
|
