← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to doc/developers/merge-scaling.txt

  • Committer: abentley
  • Date: 2005-10-14 03:50:50 UTC
  • mto: (1185.25.1)
  • mto: This revision was merged to the branch mainline in revision 1460.
  • Revision ID: abentley@lappy-20051014035050-d779472ccb599a51
semi-broke merge

Show diffs side-by-side

added added

removed removed

Lines of Context:
doc/developers/merge-scaling.txt
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
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
26
 
 
27
 
Needs
28
 
-----
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
32
 
 
33
 
Notes
34
 
-----
35
 
Multiparent deltas may offer some nice properties for performance of annotation based merging.