|
2495.2.1
by Aaron Bentley
Add bundle creation and merge scaling analysis |
1 |
Scaling analysys of Merge |
2 |
========================= |
|
3 |
||
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)** |
|
7 |
||
8 |
- text merge O(e * e * f) + O(b) |
|
9 |
||
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) |
|
15 |
9. Print changes O(c) |
|
16 |
||
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 |
|
|
4031.3.1
by Frank Aspell
Fixing various typos |
22 |
:f: number of files requiring text merge |
|
2495.2.1
by Aaron Bentley
Add bundle creation and merge scaling analysis |
23 |
:g: number of conflicts (g <= c) |
24 |
:h: humber of uncommon ancestors |
|
25 |
:i: number of revisions between base and other |
|
26 |
||
27 |
Needs |
|
|
2506.1.1
by Alexander Belchenko
sanitize developers docs |
28 |
----- |
|
2495.2.1
by Aaron Bentley
Add bundle creation and merge scaling analysis |
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 |
|
|
2485.4.8
by Robert Collins
Note that multiparent deltas affect merge to, from the mailing list review discussion. |
32 |
|
33 |
Notes |
|
|
2506.1.1
by Alexander Belchenko
sanitize developers docs |
34 |
----- |
|
2485.4.8
by Robert Collins
Note that multiparent deltas affect merge to, from the mailing list review discussion. |
35 |
Multiparent deltas may offer some nice properties for performance of annotation based merging. |