Rev 4433: Changing from a set of seen to a list to cleanup and a seen attribute. in http://bazaar.launchpad.net/~jameinel/bzr/jam-gdfo-heads

[John Arbash Meinel]

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

------------------------------------------------------------
revno: 4433
revision-id: john at arbash-meinel.com-20090619183653-m5k5roph4yc2rclw
parent: john at arbash-meinel.com-20090619183001-xy6dp466kh3cwd1j
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: jam-gdfo-heads
timestamp: Fri 2009-06-19 13:36:53 -0500
message:
  Changing from a set of seen to a list to cleanup and a seen attribute.
  Known: 1.682s
  Known (pyx): 0.440s
  ratio: 3.8:1 faster
  
  Breaks the 2x faster barrier.
-------------- next part --------------
=== modified file 'bzrlib/_known_graph_pyx.pyx'
--- a/bzrlib/_known_graph_pyx.pyx	2009-06-19 18:30:01 +0000
+++ b/bzrlib/_known_graph_pyx.pyx	2009-06-19 18:36:53 +0000
@@ -59,6 +59,7 @@
     cdef object parents
     cdef object children
     cdef public long gdfo
+    cdef int seen
 
     def __init__(self, key):
         cdef int i
@@ -69,6 +70,7 @@
         self.children = []
         # Greatest distance from origin
         self.gdfo = -1
+        self.seen = 0
 
     property child_keys:
         def __get__(self):
@@ -311,7 +313,7 @@
         if PyDict_Size(candidate_nodes) < 2:
             return heads_key
 
-        seen = set()
+        cleanup = []
         pending = []
         pending_pop = pending.pop
         # we know a gdfo cannot be longer than a linear chain of all nodes
@@ -329,11 +331,12 @@
         # Now do all the real work
         while PyList_GET_SIZE(pending) > 0:
             node = _get_list_node(pending, PyList_GET_SIZE(pending) - 1)
-            if PySet_Contains(seen, node.key):
+            if node.seen:
                 # node already appears in some ancestry
                 pending_pop()
                 continue
-            PySet_Add(seen, node.key)
+            PyList_Append(cleanup, node)
+            node.seen = 1
             if node.gdfo <= min_gdfo:
                 pending_pop()
                 continue
@@ -348,7 +351,16 @@
                         PyList_Append(pending, parent_node)
             else:
                 pending_pop()
-        heads = heads_key.difference(seen)
+        heads = []
+        pos = 0
+        while PyDict_Next(candidate_nodes, &pos, NULL, &temp_node):
+            node = <_KnownGraphNode>temp_node
+            if not node.seen:
+                PyList_Append(heads, node.key)
+        heads = PyFrozenSet_New(heads)
+        for pos from 0 <= pos < PyList_GET_SIZE(cleanup):
+            node = _get_list_node(cleanup, pos)
+            node.seen = 0
         if self.do_cache:
             PyDict_SetItem(self._known_heads, heads_key, heads)
         return heads