/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

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

  • Committer: Robert Collins
  • Date: 2009-08-26 03:20:32 UTC
  • mfrom: (4637 +trunk)
  • mto: (4634.6.2 2.0)
  • mto: This revision was merged to the branch mainline in revision 4660.
  • Revision ID: robertc@robertcollins.net-20090826032032-mx5kiog3eihaoy13
Merge and cherrypick outstanding 2.0 relevant patches from bzr.dev: Up to rev
4637, then 4639,4641,4643,4646,4649,4650,4651. (Robert Collins)

Log messages of the incorporated fixes:

revno: 4651 [merge]
  (robertc) Enable commit via record_iter_changes for specific file
        comments. (Robert Collins)

revno: 4650 [merge]
  Fix shelve on windows. (Robert Collins, #305006)

revno: 4649 [merge]
  (robertc) Make iter_changes produce output that is always safe to
        generate inventory deltas of in the same direction as the
        changes. (Robert Collins, #347649)

revno: 4646 [merge]
  (mbp) developer documentation about content filtering

revno: 4643 [merge]
  (mbp) small tweaks to release documentation

revno: 4641 [merge]
  (abentley) Shelve will not remove tree root.

revno: 4639 [merge]
  (andrew) Fix 'Revision ... not present' errors when upgrading stacked
        branches.

revno: 4637 [merge]
  Fix upgrade of branches in repositories.

revno: 4636 [merge]
  (mbp) fix crash formatting CannotBindAddress

revno: 4635 [merge]
  (robertc) Fix many locking errors on windows due to a small bug in
        merge.transform_tree. (Robert Collins)

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 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.