Rev 4438: Re-use the child.seen attribute for tracking num parents. in http://bazaar.launchpad.net/~jameinel/bzr/jam-gdfo-heads

[John Arbash Meinel]

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

------------------------------------------------------------
revno: 4438
revision-id: john at arbash-meinel.com-20090619194927-re2ony3ebgp2a1lg
parent: john at arbash-meinel.com-20090619194226-kjutz0x3s29mzwc5
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: jam-gdfo-heads
timestamp: Fri 2009-06-19 14:49:27 -0500
message:
  Re-use the child.seen attribute for tracking num parents.
  Down to 49.8ms and 618ms for bzr and OO.
-------------- next part --------------
=== modified file 'bzrlib/_known_graph_pyx.pyx'
--- a/bzrlib/_known_graph_pyx.pyx	2009-06-19 19:42:26 +0000
+++ b/bzrlib/_known_graph_pyx.pyx	2009-06-19 19:49:27 +0000
@@ -220,14 +220,9 @@
         cdef Py_ssize_t child_pos
         cdef int replace
         cdef Py_ssize_t last_item
-        cdef long known_gdfo
         cdef long next_gdfo
 
         pending = []
-        # Setting this as an attribute of _KnownGraphNode drops 774ms => 621ms,
-        # but adds a field that we won't use again. It avoids a dict lookup,
-        # and using PyInt rather than plain 'long'.
-        known_parent_gdfos = {}
 
         for node in self._tails:
             node.gdfo = 1
@@ -242,15 +237,10 @@
             next_gdfo = node.gdfo + 1
             for child_pos from 0 <= child_pos < PyList_GET_SIZE(node.children):
                 child = _get_list_node(node.children, child_pos)
-                temp = PyDict_GetItem(known_parent_gdfos, child.key)
-                if temp == NULL:
-                    known_gdfo = 1
-                else:
-                    known_gdfo = <object>temp
-                    known_gdfo = known_gdfo + 1
                 if next_gdfo > child.gdfo:
                     child.gdfo = next_gdfo
-                if known_gdfo == PyTuple_GET_SIZE(child.parents):
+                child.seen = child.seen + 1
+                if child.seen == PyTuple_GET_SIZE(child.parents):
                     # This child is populated, queue it to be walked
                     last_item = last_item + 1
                     if last_item < PyList_GET_SIZE(pending):
@@ -258,14 +248,9 @@
                         PyList_SetItem(pending, last_item, child)
                     else:
                         PyList_Append(pending, child)
-                    if temp != NULL:
-                        # We are done with this node, remove it from
-                        # known_parent_gdfos
-                        PyDict_DelItem(known_parent_gdfos, child.key)
-                else:
-                    # Not done with this child, so make sure to track the
-                    # number of known parents
-                    PyDict_SetItem(known_parent_gdfos, child.key, known_gdfo)
+                    # We have queued this node, we don't need to track it
+                    # anymore
+                    child.seen = 0
 
     def heads(self, keys):
         """Return the heads from amongst keys.