~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

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

• browse files at revision 3815
• compare with another revision
• download diff
• download tarball
• view history from revision 3815

• reverse the comparison (3815 to 408)
• stop comparing with revision 408

Show diffs side-by-side

added

removed

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.

• Older »

Loggerhead is a web-based interface for Breezy
Version: 2.0.1