Merge lp:~vila/bzr/857335-tags-revs-slow into lp:bzr

[Vincent Ladeuil]

Stop reloading all ancestry for each tag when searching tags in a revision range

bzr tags was doing a costly ancestry check when the -rX..Y parameter was
specified.

In the worst case scenario (-r1..), this gave:

bzr: 23 secs
emacs: 19 mins
gcc: 74 mins

With this patch, we're down to:

bzr: 1.3 secs
emacs: 9.8 secs
gcc: 7.6 secs

I had to add a check for the case where X > Y in -rX..Y to comply with the
test suite which roughly says: if the range is invalid, don't output
anything. The timings mentioned in the bug report was without this check.

Using a range is still slower than no using a range which is... unfortunate
but seems out of scope as it would require unifying the various graphs
cached in the branch and the repo in various forms.

[Jelmer Vernooij (jelmer)]

s/ouput/output/

It might be nice to split the bit of code that determines the tags for a range out into a separate method. Other than that, this seems reasonable.

review: Approve

[Vincent Ladeuil (vila)]

sent to pqm by email

=== modified file 'bzrlib/builtins.py'
--- bzrlib/builtins.py	2011-09-22 19:51:18 +0000
+++ bzrlib/builtins.py	2011-09-24 03:27:24 +0000
@@ -2620,7 +2620,7 @@
             match_dict['author'] = match_author
         if match_bugs:
             match_dict['bugs'] = match_bugs
-            
+
         # Build the LogRequest and execute it
         if len(file_ids) == 0:
             file_ids = None
@@ -5752,12 +5752,8 @@
 
         self.add_cleanup(branch.lock_read().unlock)
         if revision:
-            graph = branch.repository.get_graph()
-            rev1, rev2 = _get_revision_range(revision, branch, self.name())
-            revid1, revid2 = rev1.rev_id, rev2.rev_id
-            # only show revisions between revid1 and revid2 (inclusive)
-            tags = [(tag, revid) for tag, revid in tags if
-                graph.is_between(revid, revid1, revid2)]
+            # Restrict to the specified range
+            tags = self._tags_for_range(branch, revision)
         if sort is None:
             sort = tag_sort_methods.get()
         sort(branch, tags)
@@ -5768,7 +5764,8 @@
                     revno = branch.revision_id_to_dotted_revno(revid)
                     if isinstance(revno, tuple):
                         revno = '.'.join(map(str, revno))
-                except (errors.NoSuchRevision, errors.GhostRevisionsHaveNoRevno):
+                except (errors.NoSuchRevision,
+                        errors.GhostRevisionsHaveNoRevno):
                     # Bad tag data/merges can lead to tagged revisions
                     # which are not in this branch. Fail gracefully ...
                     revno = '?'
@@ -5777,6 +5774,32 @@
         for tag, revspec in tags:
             self.outf.write('%-20s %s\n' % (tag, revspec))
 
+    def _tags_for_range(self, branch, revision):
+        range_valid = True
+        rev1, rev2 = _get_revision_range(revision, branch, self.name())
+        revid1, revid2 = rev1.rev_id, rev2.rev_id
+        # _get_revision_range will always set revid2 if it's not specified.
+        # If revid1 is None, it means we want to start from the branch
+        # origin which is always a valid ancestor. If revid1 == revid2, the
+        # ancestry check is useless.
+        if revid1 and revid1 != revid2:
+            # FIXME: We really want to use the same graph than
+            # branch.iter_merge_sorted_revisions below, but this is not
+            # easily available -- vila 2011-09-23
+            if branch.repository.get_graph().is_ancestor(revid2, revid1):
+                # We don't want to output anything in this case...
+                return []
+        # only show revisions between revid1 and revid2 (inclusive)
+        tagged_revids = branch.tags.get_reverse_tag_dict()
+        found = []
+        for r in branch.iter_merge_sorted_revisions(
+            start_revision_id=revid2, stop_revision_id=revid1,
+            stop_rule='include'):
+            revid_tags = tagged_revids.get(r[0], None)
+            if revid_tags:
+                found.extend([(tag, r[0]) for tag in revid_tags])
+        return found
+
 
 class cmd_reconfigure(Command):
     __doc__ = """Reconfigure the type of a bzr directory.
 
=== modified file 'doc/en/release-notes/bzr-2.5.txt'
--- doc/en/release-notes/bzr-2.5.txt	2011-09-23 07:51:28 +0000
+++ doc/en/release-notes/bzr-2.5.txt	2011-09-24 03:27:24 +0000
@@ -26,6 +26,9 @@
 .. Improvements to existing commands, especially improved performance 
    or memory usage, or better results.
 
+* Stop reloading all ancestry for each tag when searching tags in a revision
+  range. (Vincent Ladeuil, #857335)
+
 Bug Fixes
 *********