Bazaar

Merge lp:~abentley/bzr/preview-tree-changes-cache into lp:bzr/2.0

  1. preview-tree-changes-cache
  2. Merge into 2.0
Proposed by Aaron Bentley
Status: Merged
Approved by: John A Meinel
Approved revision: no longer in the source branch.
Merged at revision: not available
Proposed branch: lp:~abentley/bzr/preview-tree-changes-cache
Merge into: lp:bzr/2.0
Diff against target: 84 lines
3 files modified
NEWS (+3/-0)
bzrlib/tests/test_transform.py (+4/-2)
bzrlib/transform.py (+6/-9)
To merge this branch: bzr merge lp:~abentley/bzr/preview-tree-changes-cache
Reviewer Review Type Date Requested Status
John A Meinel Approve
Review via email: mp+12607@code.launchpad.net
To post a comment you must log in.
Revision history for this message
Aaron Bentley (abentley) wrote :

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi all,

This patch causes PreviewTree to memoize the iter_changes values for its
TreeTransform. It speeds up PreviewTree dramatically when there are
large numbers of changes. The current behaviour scales O(n^2), and this
changes it to O(n).

Best of three runs of "bzr merge --preview ../bzr.dev" in bzr.ab:

Before:
real 2m29.827s
user 2m24.669s
sys 0m2.816s

After:
real 0m6.725s
user 0m6.064s
sys 0m0.552s

This is ~ 22x faster, and the improvemnt will scale with the number of
changes involved. (this merge involved ~585 files) "merge --preview",

"merge --interactive" and unshelve would be the primary winners in bzr.
   Launchpad's code review diff generation would become faster and more
reliable. Launchpad's branch -> translation export might be somewhat
improved. bzr-pipeline's pump command would be faster.

Memoizing these values is acceptable because altering the TreeTransform
(or its base tree) after calling get_preview_tree() invalidates that
preview tree.

I'm submitting this to the 2.0 branch because it is a small change that
doesn't affect the API.

Aaron
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkrCUw4ACgkQ0F+nu1YWqI0dKACghtAubau4t9Xy+9ohpwcZD1H1
t/wAnjr/6D+HTLl/DXAccc3i6NXZ2UjG
=nIfK
-----END PGP SIGNATURE-----

Revision history for this message
John A Meinel (jameinel) wrote :

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Aaron Bentley wrote:
> Aaron Bentley has proposed merging lp:~abentley/bzr/preview-tree-changes-cache into lp:bzr/2.0.
>
> Requested reviews:
> bzr-core (bzr-core)
>
>
> Hi all,
>
> This patch causes PreviewTree to memoize the iter_changes values for its
> TreeTransform. It speeds up PreviewTree dramatically when there are
> large numbers of changes. The current behaviour scales O(n^2), and this
> changes it to O(n).
>
> Best of three runs of "bzr merge --preview ../bzr.dev" in bzr.ab:
>

 review: approve
 merge: approve

It would be nice if we could detect that the preview tree was
invalidated somehow, but I don't know that it needs to be done here.

Perhaps just a doc update to .get_preview_tree() which indicates that it
is considered a snapshot, and no further changes should be done without
requesting a new preview tree?

John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkrCZ9AACgkQJdeBCYSNAAORkACglmQVjwnJ2Bst7w14UPrKeaZF
1Z8AmwZwrLl89/nJcByi5UfH0rPzsDln
=AloF
-----END PGP SIGNATURE-----

review: Approve
Revision history for this message
Martin Pool (mbp) wrote :

Deserves a news mention.

Revision history for this message
Aaron Bentley (abentley) wrote :

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Martin Pool wrote:
> Deserves a news mention.

Sure, and I added one before landing it:

8 +* Retrieving file text or mtime from a _PreviewTree has good
performance when
9 + there are many changes. (Aaron Bentley)
10 +
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkrKutoACgkQ0F+nu1YWqI2WiQCghnAgBuw3E+4RDbifH4PZYfX2
wTcAnA75MFbgRaHsJmI3h9742XpKtp8m
=Ewpy
-----END PGP SIGNATURE-----

Preview Diff

[H/L] Next/Prev Comment, [J/K] Next/Prev File, [N/P] Next/Prev Hunk
1=== modified file 'NEWS'
2--- NEWS 2009-09-29 00:57:15 +0000
3+++ NEWS 2009-09-29 21:13:10 +0000
4@@ -52,6 +52,9 @@
5 object when doing a merge, and there is limbo, or pending-deletions
6 directory. (Gary van der Merwe, #427773)
7
8+* Retrieving file text or mtime from a _PreviewTree has good performance when
9+ there are many changes. (Aaron Bentley)
10+
11
12 bzr 2.0.0
13 #########
14
15=== modified file 'bzrlib/tests/test_transform.py'
16--- bzrlib/tests/test_transform.py 2009-08-13 01:33:15 +0000
17+++ bzrlib/tests/test_transform.py 2009-09-29 21:13:10 +0000
18@@ -2614,7 +2614,9 @@
19
20 def test_walkdirs(self):
21 preview = self.get_empty_preview()
22- preview.version_file('tree-root', preview.root)
23+ root = preview.new_directory('', ROOT_PARENT, 'tree-root')
24+ # FIXME: new_directory should mark root.
25+ preview.adjust_path('', ROOT_PARENT, root)
26 preview_tree = preview.get_preview_tree()
27 file_trans_id = preview.new_file('a', preview.root, 'contents',
28 'a-id')
29@@ -2651,11 +2653,11 @@
30 self.addCleanup(work_tree.unlock)
31 preview = TransformPreview(work_tree)
32 self.addCleanup(preview.finalize)
33- preview_tree = preview.get_preview_tree()
34 file_trans_id = preview.trans_id_file_id('file-id')
35 preview.delete_contents(file_trans_id)
36 preview.create_file('a\nb\n', file_trans_id)
37 pb = progress.DummyProgress()
38+ preview_tree = preview.get_preview_tree()
39 merger = Merger.from_revision_ids(pb, preview_tree,
40 child_tree.branch.last_revision(),
41 other_branch=child_tree.branch,
42
43=== modified file 'bzrlib/transform.py'
44--- bzrlib/transform.py 2009-08-26 05:38:16 +0000
45+++ bzrlib/transform.py 2009-09-29 21:13:10 +0000
46@@ -859,8 +859,8 @@
47 def get_preview_tree(self):
48 """Return a tree representing the result of the transform.
49
50- This tree only supports the subset of Tree functionality required
51- by show_diff_trees. It must only be compared to tt._tree.
52+ The tree is a snapshot, and altering the TreeTransform will invalidate
53+ it.
54 """
55 return _PreviewTree(self)
56
57@@ -1635,15 +1635,12 @@
58 self._all_children_cache = {}
59 self._path2trans_id_cache = {}
60 self._final_name_cache = {}
61-
62- def _changes(self, file_id):
63- for changes in self._transform.iter_changes():
64- if changes[0] == file_id:
65- return changes
66+ self._iter_changes_cache = dict((c[0], c) for c in
67+ self._transform.iter_changes())
68
69 def _content_change(self, file_id):
70 """Return True if the content of this file changed"""
71- changes = self._changes(file_id)
72+ changes = self._iter_changes_cache.get(file_id)
73 # changes[2] is true if the file content changed. See
74 # InterTree.iter_changes.
75 return (changes is not None and changes[2])
76@@ -1990,7 +1987,7 @@
77
78 def annotate_iter(self, file_id,
79 default_revision=_mod_revision.CURRENT_REVISION):
80- changes = self._changes(file_id)
81+ changes = self._iter_changes_cache.get(file_id)
82 if changes is None:
83 get_old = True
84 else:

Subscribers

People subscribed via source and target branches