Rev 4429: Big performance win, back to 650ms. in http://bazaar.launchpad.net/~jameinel/bzr/jam-gdfo-heads

[John Arbash Meinel]

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

------------------------------------------------------------
revno: 4429
revision-id: john at arbash-meinel.com-20090619173701-56p7yg3ionug2slb
parent: john at arbash-meinel.com-20090619173033-0opvbm5ubonl0jo2
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: jam-gdfo-heads
timestamp: Fri 2009-06-19 12:37:01 -0500
message:
  Big performance win, back to 650ms.
  
  Note that we don't need to grow known_parent_gdfos indefinitely.
  Once we have queued up a node to be walked, we should never walk
  it again, so we can remove the entry.
  We also can avoid ever *setting* the item if we resolve it in
  the first pass.
  
  Will update the python version as well.
-------------- next part --------------
=== modified file 'bzrlib/_known_graph_pyx.pyx'
--- a/bzrlib/_known_graph_pyx.pyx	2009-06-19 17:30:33 +0000
+++ b/bzrlib/_known_graph_pyx.pyx	2009-06-19 17:37:01 +0000
@@ -31,6 +31,7 @@
     PyObject * PyTuple_GET_ITEM(object t, Py_ssize_t o)
     Py_ssize_t PyTuple_GET_SIZE(object t)
     PyObject * PyDict_GetItem(object d, object k)
+    int PyDict_DelItem(object d, object k) except -1
     Py_ssize_t PyDict_Size(object d) except -1
     int PyDict_CheckExact(object d)
     int PyDict_Next(object d, Py_ssize_t *pos, PyObject **k, PyObject **v)
@@ -218,6 +219,7 @@
         cdef Py_ssize_t child_pos
         cdef int replace
         cdef Py_ssize_t pending_size
+        cdef long known_gdfo
 
         pending = []
         # Setting this as an attribute of _KnownGraphNode drops 774ms => 621ms,
@@ -243,7 +245,6 @@
                 else:
                     known_gdfo = <object>temp
                     known_gdfo = known_gdfo + 1
-                known_parent_gdfos[child.key] = known_gdfo
                 if child.gdfo is None or node.gdfo + 1 > child.gdfo:
                     child.gdfo = node.gdfo + 1
                 if known_gdfo == PyList_GET_SIZE(child.parents):
@@ -255,6 +256,14 @@
                     else:
                         PyList_Append(pending, child)
                         pending_size = pending_size + 1
+                    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)
             if replace:
                 # We didn't add any children, so pop off the last node
                 pending.pop()