Rev 4426: Using a dict drops us to 767ms in http://bazaar.launchpad.net/~jameinel/bzr/jam-gdfo-heads

[John Arbash Meinel]

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

------------------------------------------------------------
revno: 4426
revision-id: john at arbash-meinel.com-20090619170818-9yi5nqmgo0x09983
parent: john at arbash-meinel.com-20090619170356-wfb1l9smtoafxxsy
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: jam-gdfo-heads
timestamp: Fri 2009-06-19 12:08:18 -0500
message:
  Using a dict drops us to 767ms
  Slower than we could be, but still 'fast enough' and still 2x faster than
  the unoptimized form.
  Will look into a little bit of tuning.
-------------- next part --------------
=== modified file 'bzrlib/_known_graph_pyx.pyx'
--- a/bzrlib/_known_graph_pyx.pyx	2009-06-19 17:03:56 +0000
+++ b/bzrlib/_known_graph_pyx.pyx	2009-06-19 17:08:18 +0000
@@ -51,7 +51,6 @@
     cdef object key
     cdef object parents
     cdef object children
-    cdef long known_parent_gdfos
     cdef public long gdfo
 
     def __init__(self, key):
@@ -63,7 +62,6 @@
         self.children = []
         # Greatest distance from origin
         self.gdfo = -1
-        self.known_parent_gdfos = 0
 
     property child_keys:
         def __get__(self):
@@ -222,6 +220,7 @@
         cdef Py_ssize_t pending_size
 
         pending = []
+        known_parent_gdfos = {}
 
         for node in self._tails:
             node.gdfo = 1
@@ -234,10 +233,16 @@
             replace = 1
             for child_pos from 0 <= child_pos < PyList_GET_SIZE(node.children):
                 child = _get_list_node(node.children, child_pos)
-                child.known_parent_gdfos = child.known_parent_gdfos + 1
+                temp = PyDict_GetItem(known_parent_gdfos, child.key)
+                if temp == NULL:
+                    known_gdfo = 1
+                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 child.known_parent_gdfos == PyList_GET_SIZE(child.parents):
+                if known_gdfo == PyList_GET_SIZE(child.parents):
                     # We are the last parent updating that node, we can
                     # continue from there
                     if replace: