Rev 4442: Apply the same 'never pop' logic to the heads() code. in http://bazaar.launchpad.net/~jameinel/bzr/jam-gdfo-heads

[John Arbash Meinel]

At http://bazaar.launchpad.net/~jameinel/bzr/jam-gdfo-heads

------------------------------------------------------------
revno: 4442
revision-id: john at arbash-meinel.com-20090619203535-ddfmpm4c9ey1ijrp
parent: john at arbash-meinel.com-20090619201707-1zruedh20651c14q
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: jam-gdfo-heads
timestamp: Fri 2009-06-19 15:35:35 -0500
message:
  Apply the same 'never pop' logic to the heads() code.
  
  Turns out to be another big win, going from 409ms down to 362ms.
-------------- next part --------------
=== modified file 'bzrlib/_known_graph_pyx.pyx'
--- a/bzrlib/_known_graph_pyx.pyx	2009-06-19 20:17:07 +0000
+++ b/bzrlib/_known_graph_pyx.pyx	2009-06-19 20:35:35 +0000
@@ -264,7 +264,7 @@
         cdef PyObject *maybe_heads
         cdef PyObject *temp_node
         cdef _KnownGraphNode node
-        cdef Py_ssize_t pos
+        cdef Py_ssize_t pos, last_item
         cdef long min_gdfo
 
         heads_key = PyFrozenSet_New(keys)
@@ -291,7 +291,6 @@
 
         cleanup = []
         pending = []
-        pending_pop = pending.pop
         # we know a gdfo cannot be longer than a linear chain of all nodes
         min_gdfo = PyDict_Size(self._nodes) + 1
         # Build up nodes that need to be walked, note that starting nodes are
@@ -305,28 +304,26 @@
                 min_gdfo = node.gdfo
 
         # Now do all the real work
-        while PyList_GET_SIZE(pending) > 0:
-            node = _get_list_node(pending, PyList_GET_SIZE(pending) - 1)
+        last_item = PyList_GET_SIZE(pending) - 1
+        while last_item >= 0:
+            node = _get_list_node(pending, last_item)
+            last_item = last_item - 1
             if node.seen:
                 # node already appears in some ancestry
-                pending_pop()
                 continue
             PyList_Append(cleanup, node)
             node.seen = 1
             if node.gdfo <= min_gdfo:
-                pending_pop()
                 continue
             if node.parents is not None and PyTuple_GET_SIZE(node.parents) > 0:
                 for pos from 0 <= pos < PyTuple_GET_SIZE(node.parents):
                     parent_node = _get_parent(node.parents, pos)
-                    if pos == 0:
-                        Py_INCREF(parent_node)
-                        PyList_SetItem(pending, PyList_GET_SIZE(pending) - 1,
-                                        parent_node)
+                    last_item = last_item + 1
+                    if last_item < PyList_GET_SIZE(pending):
+                        Py_INCREF(parent_node) # SetItem steals a ref
+                        PyList_SetItem(pending, last_item, parent_node)
                     else:
                         PyList_Append(pending, parent_node)
-            else:
-                pending_pop()
         heads = []
         pos = 0
         while PyDict_Next(candidate_nodes, &pos, NULL, &temp_node):