Rev 4628: Expose KnownGraph off of VersionedFiles in http://bazaar.launchpad.net/~jameinel/bzr/1.19-known-graph-sorted

[John Arbash Meinel]

At http://bazaar.launchpad.net/~jameinel/bzr/1.19-known-graph-sorted

------------------------------------------------------------
revno: 4628
revision-id: john at arbash-meinel.com-20090816172208-2mh7z0uapy6y0gsv
parent: john at arbash-meinel.com-20090816165630-g94xm2dan6i03dvv
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.19-known-graph-sorted
timestamp: Sun 2009-08-16 12:22:08 -0500
message:
  Expose KnownGraph off of VersionedFiles
  handle ghosts (needs tests, doesn't seem to effect performance)
  list(tuple[1:]) is a couple ms slower than using my own loop.
  Net effect is:
    time bzr log -n0 -r -10..-1
    real    0m2.559s
  
    time wbzr log -n0 -r -10..-1
    real    0m1.170s
  
    time bzr log -n1 -r -10..-1
    real    0m0.453s
  
  So the overhead for the extra graph is down from 2.1s to 0.7s
-------------- next part --------------
=== modified file 'bzrlib/_known_graph_pyx.pyx'
--- a/bzrlib/_known_graph_pyx.pyx	2009-08-16 16:56:30 +0000
+++ b/bzrlib/_known_graph_pyx.pyx	2009-08-16 17:22:08 +0000
@@ -509,11 +509,12 @@
             ms_node.left_parent = parent_node
             ms_node.left_pending_parent = parent_node
         if PyTuple_GET_SIZE(node.parents) > 1:
-            ms_node.pending_parents = list(node.parents[1:])
-            # ms_node.pending_parents = []
-            # for pos from 1 <= pos < PyTuple_GET_SIZE(node.parents):
-            #     parent_node = _get_parent(node.parents, pos)
-            #     PyList_Append(ms_node.pending_parents, parent_node)
+            ms_node.pending_parents = []
+            for pos from 1 <= pos < PyTuple_GET_SIZE(node.parents):
+                parent_node = _get_parent(node.parents, pos)
+                if parent_node.parents is None: # ghost
+                    continue
+                PyList_Append(ms_node.pending_parents, parent_node)
 
         ms_node.is_first_child = 1
         if ms_node.left_parent is not None:

=== modified file 'bzrlib/branch.py'
--- a/bzrlib/branch.py	2009-08-13 20:10:26 +0000
+++ b/bzrlib/branch.py	2009-08-16 17:22:08 +0000
@@ -446,14 +446,12 @@
         # start_revision_id.
         if self._merge_sorted_revisions_cache is None:
             last_revision = self.last_revision()
-            graph = self.repository.get_graph()
-            parent_map = dict(((key, value) for key, value in
-                     graph.iter_ancestry([last_revision]) if value is not None))
-            revision_graph = repository._strip_NULL_ghosts(parent_map)
-            revs = tsort.merge_sort(revision_graph, last_revision, None,
-                generate_revno=True)
-            # Drop the sequence # before caching
-            self._merge_sorted_revisions_cache = [r[1:] for r in revs]
+            last_key = (last_revision,)
+            known_graph = self.repository.revisions.get_known_graph_ancestry(
+                [last_key])
+            revs = known_graph.merge_sort(last_key)
+            self._merge_sorted_revisions_cache = [(key[-1], d, rn, eom)
+                for sn, key, d, rn, eom in revs]
 
         filtered = self._filter_merge_sorted_revisions(
             self._merge_sorted_revisions_cache, start_revision_id,

=== modified file 'bzrlib/groupcompress.py'
--- a/bzrlib/groupcompress.py	2009-08-04 04:36:34 +0000
+++ b/bzrlib/groupcompress.py	2009-08-16 17:22:08 +0000
@@ -1099,6 +1099,13 @@
             self._check_lines_not_unicode(lines)
             self._check_lines_are_lines(lines)
 
+    def get_known_graph_ancestry(self, keys):
+        """Get a KnownGraph instance with the ancestry of keys."""
+        parent_map, missing_keys = self._index._graph_index.find_ancestry(keys,
+                                                                          0)
+        kg = _mod_graph.KnownGraph(parent_map)
+        return kg
+
     def get_parent_map(self, keys):
         """Get a map of the graph parents of keys.
 

=== modified file 'bzrlib/knit.py'
--- a/bzrlib/knit.py	2009-08-04 04:36:34 +0000
+++ b/bzrlib/knit.py	2009-08-16 17:22:08 +0000
@@ -1190,6 +1190,13 @@
         generator = _VFContentMapGenerator(self, [key])
         return generator._get_content(key)
 
+    def get_known_graph_ancestry(self, keys):
+        """Get a KnownGraph instance with the ancestry of keys."""
+        parent_map, missing_keys = self._index._graph_index.find_ancestry(keys,
+                                                                          0)
+        kg = _mod_graph.KnownGraph(parent_map)
+        return kg
+
     def get_parent_map(self, keys):
         """Get a map of the graph parents of keys.
 

=== modified file 'bzrlib/versionedfile.py'
--- a/bzrlib/versionedfile.py	2009-08-07 05:56:29 +0000
+++ b/bzrlib/versionedfile.py	2009-08-16 17:22:08 +0000
@@ -228,6 +228,10 @@
         """Copy this versioned file to name on transport."""
         raise NotImplementedError(self.copy_to)
 
+    def get_known_graph_ancestry(self, keys):
+        """Get a KnownGraph instance with the ancestry of keys."""
+        raise NotImplementedError(self.get_known_graph_ancestry)
+
     def get_record_stream(self, versions, ordering, include_delta_closure):
         """Get a stream of records for versions.