/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: Vincent Ladeuil
  • Date: 2009-04-11 16:06:53 UTC
  • mto: (4286.1.1 integration)
  • mto: This revision was merged to the branch mainline in revision 4287.
  • Revision ID: v.ladeuil+lp@free.fr-20090411160653-eq1gfn41q3lzhmss
Cleanup test imports and use features to better track skipped tests.

* bzrlib/tests/workingtree_implementations/__init__.py: 
Fix imports. Delete obsolete comment.

* bzrlib/tests/tree_implementations/test_walkdirs.py:
(TestWalkdirs.get_all_subdirs_expected): Reduce duplication.

* bzrlib/tests/tree_implementations/test_test_trees.py: 
Fix import.

* bzrlib/tests/tree_implementations/test_path_content_summary.py: 
Fix imports.

(TestPathContentSummary.test_unicode_symlink_content_summary,
TestPathContentSummary.test_unicode_symlink_target_summary):Use
UnicodeFilenameFeature instead of try/except UnicodeError.

* bzrlib/tests/tree_implementations/test_inv.py: 
Fix imports.
(TestInventoryWithSymlinks): Factor out test that requires
symlinks and use _test_needs_features.
(TestInventory.test_canonical_path,
TestInventory.test_canonical_path_dir,
TestInventory.test_canonical_path_root,
TestInventory.test_canonical_path_invalid_all,
TestInventory.test_canonical_invalid_child): Use assert(expected,
actual)

* bzrlib/tests/tree_implementations/test_get_symlink_target.py: 
Fix imports.
(TestGetSymlinkTarget.test_get_unicode_symlink_target): Use
UnicodeFilenameFeature instead of try/except UnicodeError.

* bzrlib/tests/tree_implementations/__init__.py: 
Fix imports.

(TestCaseWithTree.get_tree_with_subdirs_and_all_supported_content_types,
TestCaseWithTree._create_tree_with_utf8): Use
UnicodeFilenameFeature instead of try/except UnicodeError.

* bzrlib/tests/test_workingtree_4.py:
Fix too long lines.

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.