Rev 4625: No need to pop one item off the stack after another. 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: 4625
revision-id: john at arbash-meinel.com-20090816163005-owo9jl07h6xlnip1
parent: john at arbash-meinel.com-20090816161425-x842fray6gf3peid
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.19-known-graph-sorted
timestamp: Sun 2009-08-16 11:30:05 -0500
message:
  No need to pop one item off the stack after another.
  We can just iterate over the group and append to the output.
  Use direct function calls, rather than ordered.append.
  
  Down to:
   #  103ms graph.KnownGraph().merge_sort()
   #   55ms kg.merge_sort()
-------------- next part --------------
=== modified file 'bzrlib/_known_graph_pyx.pyx'
--- a/bzrlib/_known_graph_pyx.pyx	2009-08-16 16:14:25 +0000
+++ b/bzrlib/_known_graph_pyx.pyx	2009-08-16 16:30:05 +0000
@@ -474,8 +474,8 @@
 
     # Current performance numbers for merge_sort(bzr_dev_parent_map):
     #  310ms tsort.merge_sort()
-    #  112ms graph.KnownGraph().merge_sort()
-    #   64ms kg.merge_sort()
+    #  103ms graph.KnownGraph().merge_sort()
+    #   55ms kg.merge_sort()
 
     cdef KnownGraph graph
     cdef object _depth_first_stack  # list
@@ -567,14 +567,17 @@
                 else:
                     base_revno = ms_node.left_ms_parent.revno_first
                 temp = PyDict_GetItem(self._revno_to_branch_count,
-                                           base_revno)
+                                      base_revno)
                 if temp == NULL:
                     branch_count = 1
                 else:
                     branch_count = (<object>temp) + 1
                 PyDict_SetItem(self._revno_to_branch_count, base_revno,
                                branch_count)
-                ms_node.revno_first = base_revno
+                if ms_node.left_ms_parent.revno_first == -1:
+                    ms_node.revno_first = ms_node.left_ms_parent.revno_last
+                else:
+                    ms_node.revno_first = ms_node.left_ms_parent.revno_first
                 ms_node.revno_second = branch_count
                 ms_node.revno_last = 1
         else:
@@ -653,6 +656,7 @@
     cdef topo_order(self):
         cdef _MergeSortNode ms_node, ms_last_node
         cdef _KnownGraphNode next_node
+        cdef Py_ssize_t pos
 
         # print
         self._schedule_stack()
@@ -662,14 +666,17 @@
         # output.
         sequence_number = 0
         ordered = []
-        while self._scheduled_nodes:
-            ms_node = self._scheduled_nodes.pop()
-            # TODO: stop_revision not supported
-            # if ms_node == stop_revision:
-            if len(self._scheduled_nodes) == 0:
+        pos = PyList_GET_SIZE(self._scheduled_nodes) - 1
+        if pos >= 0:
+            ms_last_node = _get_ms_node(self._scheduled_nodes, pos)
+        while pos >= 0:
+            ms_node = ms_last_node
+            pos = pos - 1
+            if pos == -1:
+                # Final node is always the end-of-chain
                 end_of_merge = True
             else:
-                ms_last_node = self._scheduled_nodes[-1]
+                ms_last_node = _get_ms_node(self._scheduled_nodes, pos)
                 if ms_last_node.merge_depth < ms_node.merge_depth:
                     # Next node is to our left, so this is the end of the right
                     # chain
@@ -687,7 +694,9 @@
             else:
                 revno = (ms_node.revno_first, ms_node.revno_second,
                          ms_node.revno_last)
-            ordered.append((sequence_number, ms_node.node.key,
-                            ms_node.merge_depth, revno, end_of_merge))
+            PyList_Append(ordered, (sequence_number, ms_node.node.key,
+                                    ms_node.merge_depth, revno, end_of_merge))
             sequence_number = sequence_number + 1
+        # Clear out the scheduled nodes
+        self._scheduled_nodes = []
         return ordered