Merge lp:~jameinel/bzr/jam-gdfo-heads into lp:~bzr/bzr/trunk-old

[John A Meinel]

[John A Meinel (jameinel)]

So this is my followup to Vincent's new algorithm for KnownGraph.heads() The only real changes are to tweak the Pyrex code to use direct access.

There are some wins by changing to using direct access to members, and the big win is to change the algorithm to avoid calling list.pop(). Instead we just track what item we are on and insert an item there. If we find we need more space then we append. (Note there is a specific edge case when you are popping short lists as it reallocs() whenever the size shrinks to 1/2 the max size. However if you only have 2 items, that is *every* pop, and then every append following it will trigger another realloc.)

Also, this changes away from using a 'seen' dictionary to using a .seen attribute.

Here are my times:

            annotate NEWS time_graph (all 7k)
bzr.dev 11.6s 71.4s
vila pyx 11.5s 1.102s
jam pyx 9.7s 0.362s

So while Vincent's update is godlike for whole-ancestry heads() calls, it doesn't show much of an effect for NEWS. I'm pretty happy to find that with a bit of tweaking the new algorithm still gives another 10% of total annotate performance (note that 'resolve right' is only 8.6s, so we are only spending ~1s resolving something like 200k heads now.)

The main diff between my old heads() and Vincent's, is that I was effectively doing a 'find_unique_ancestors' walk, while he realized that you don't have to walk any ancestors of the lowest node.

One other bit of interest for the new code. We track how many nodes we have to walk in order to compute heads() (used to be in cleanup, then in seen, and now in cleanup again.)
The bzr entry walking the most nodes is:
    <email address hidden>
    <email address hidden>

(landing the groupcompress code into brisbane-core, IIRC)
We walk 22k revisions (out of 25.4k total...) because the plugin gdfo is 182, while the bzr gdfo is 7150. So something very close to null versus something about as far away as we can get in bzr. The time to compute heads() between the two... 5ms. Yes, that is 0.005s to walk 22k revisions after computing gdfo and other such bits and determine that the two revisions are not ancestors.

I did end up spending some time to tweak the _find_gdfo() code as well. Once you are around 400ms for doing heads() for every merge revision, suddenly the 100ms or so spent in _find_gdfo starts to be a factor :).
I found that computing the tails 'for free' using a set was *not* free, and was, in fact, a lot slower than walking the dict after the fact. The issue is that parent_map is purely random walking, so you end up pushing a lot of nodes into the set that you just remove. In contrast it takes only 40ms to walk 200k nodes in the OOo dict, and find the small handful of tails we will care about.

_find_gdfo is down around 9ms time for bzr.dev. The bulk of the time in __init__ is now in _initialize_nodes which is doing mallocs for all the objects. Removing _find_gdfo is 35.5ms bzr.dev, 407ms OOo, versus 44.4ms, 563ms w/.

[Vincent Ladeuil (vila)]

>>>>> "jam" == John A Meinel <email address hidden> writes:

    jam> John A Meinel has proposed merging
    jam> lp:~jameinel/bzr/jam-gdfo-heads into lp:bzr.

 review approve

    jam> Requested reviews:
    jam> bzr-core (bzr-core)

    jam> So this is my followup to Vincent's new algorithm for
    jam> KnownGraph.heads() The only real changes are to tweak the Pyrex
    jam> code to use direct access.

    jam> There are some wins by changing to using direct access to
    jam> members, and the big win is to change the algorithm to avoid
    jam> calling list.pop(). Instead we just track what item we are on and
    jam> insert an item there. If we find we need more space then we
    jam> append. (Note there is a specific edge case when you are popping
    jam> short lists as it reallocs() whenever the size shrinks to 1/2 the
    jam> max size. However if you only have 2 items, that is *every* pop,
    jam> and then every append following it will trigger another realloc.)

    jam> Also, this changes away from using a 'seen' dictionary to using a
    jam> .seen attribute.

    jam> Here are my times:

    jam> annotate NEWS time_graph (all 7k)
    jam> bzr.dev 11.6s 71.4s
    jam> vila pyx 11.5s 1.102s
    jam> jam pyx 9.7s 0.362s

Blam :) Well done !

But while I can reproduce the time_graph times (taking into
account that my test config is faster than yours), I can't
repoduce the NEWS ones, are you sure you compile the extensions
before measuring these times ? Here are the ones I can reproduce:

            annotate NEWS time_graph (all 7k)
bzr.dev pyx 6.62s 45.390s
vila pyx 5.92s 0.510s
jam pyx 5.45s 0.180s

If we can't reliably reproduce other's experiment, I think it's
worth investigating why... I used bzr.dev@4459, what about yours
for example ? Could it be that using an SSD introduce such a
distortion (worth isolating IO related penalties, but I can't see
where in the code concerned by this patch) ? By the way, I
measure annotate with --show-ids and >/dev/null, I'm pretty sure
you do the same, but just in case.

    jam> So while Vincent's update is godlike for whole-ancestry heads()
    jam> calls, it doesn't show much of an effect for NEWS.

And for mysql:

            annotate sql/mysqld.cc time_graph (all 34k)
bzr.dev pyx 18.87s 1751.760s
vila pyx 18.42s 17.190s
jam pyx 18.43s 4.030s

Note that I made a lot of measures here to break the tie, so the
difference is a bit less obvious than for NEWS. Your version *is*
better on average, mine did the best score, but obviously the
variation is high and I don't have a good explanation for that
(except that the time spent in heads is now so low we don't
measure it properly in that case).

<snip/>

    jam> (note that resolve right' is only 8.6s, so we are only
    jam> spending ~1s resolving something like 200k heads now.)

And being qualitatively better !

<snip/>

    jam> I did end up spending some time to tweak the _find_gdfo() code as
    jam> well. Once you are around 400ms for doing heads() for e...

review: Approve

=== modified file 'bzrlib/_known_graph_py.py'
--- bzrlib/_known_graph_py.py	2009-06-16 15:35:14 +0000
+++ bzrlib/_known_graph_py.py	2009-06-20 08:35:13 +0000
@@ -17,8 +17,6 @@
 """Implementation of Graph algorithms when we have already loaded everything.
 """
 
-import heapq
-
 from bzrlib import (
     revision,
     )
@@ -27,27 +25,19 @@
 class _KnownGraphNode(object):
     """Represents a single object in the known graph."""
 
-    __slots__ = ('key', 'parent_keys', 'child_keys', 'linear_dominator',
-                 'gdfo', 'ancestor_of')
+    __slots__ = ('key', 'parent_keys', 'child_keys', 'gdfo')
 
     def __init__(self, key, parent_keys):
         self.key = key
         self.parent_keys = parent_keys
         self.child_keys = []
-        # oldest ancestor, such that no parents between here and there have >1
-        # child or >1 parent.
-        self.linear_dominator = None
         # Greatest distance from origin
         self.gdfo = None
-        # This will become a tuple of known heads that have this node as an
-        # ancestor
-        self.ancestor_of = None
 
     def __repr__(self):
-        return '%s(%s  gdfo:%s par:%s child:%s %s)' % (
+        return '%s(%s  gdfo:%s par:%s child:%s)' % (
             self.__class__.__name__, self.key, self.gdfo,
-            self.parent_keys, self.child_keys,
-            self.linear_dominator)
+            self.parent_keys, self.child_keys)
 
 
 class KnownGraph(object):
@@ -63,21 +53,28 @@
         self._known_heads = {}
         self.do_cache = do_cache
         self._initialize_nodes(parent_map)
-        self._find_linear_dominators()
         self._find_gdfo()
 
     def _initialize_nodes(self, parent_map):
         """Populate self._nodes.
 
-        After this has finished, self._nodes will have an entry for every entry
-        in parent_map. Ghosts will have a parent_keys = None, all nodes found
-        will also have .child_keys populated with all known child_keys.
+        After this has finished:
+        - self._nodes will have an entry for every entry in parent_map.
+        - ghosts will have a parent_keys = None,
+        - all nodes found will also have .child_keys populated with all known
+          child_keys,
+        - self._tails will list all the nodes without parents.
         """
+        tails = self._tails = set()
         nodes = self._nodes
         for key, parent_keys in parent_map.iteritems():
             if key in nodes:
                 node = nodes[key]
                 node.parent_keys = parent_keys
+                if parent_keys:
+                    # This node has been added before being seen in parent_map
+                    # (see below)
+                    tails.remove(node)
             else:
                 node = _KnownGraphNode(key, parent_keys)
                 nodes[key] = node
@@ -87,129 +84,41 @@
                 except KeyError:
                     parent_node = _KnownGraphNode(parent_key, None)
                     nodes[parent_key] = parent_node
+                    # Potentially a tail, if we're wrong we'll remove it later
+                    # (see above)
+                    tails.add(parent_node)
                 parent_node.child_keys.append(key)
 
-    def _find_linear_dominators(self):
-        """For each node in the set, find any linear dominators.
-
-        For any given node, the 'linear dominator' is an ancestor, such that
-        all parents between this node and that one have a single parent, and a
-        single child. So if A->B->C->D then B,C,D all have a linear dominator
-        of A.
-
-        There are two main benefits:
-        1) When walking the graph, we can jump to the nearest linear dominator,
-           rather than walking all of the nodes inbetween.
-        2) When caching heads() results, dominators give the "same" results as
-           their children. (If the dominator is a head, then the descendant is
-           a head, if the dominator is not a head, then the child isn't
-           either.)
-        """
-        def check_node(node):
-            if node.parent_keys is None or len(node.parent_keys) != 1:
-                # This node is either a ghost, a tail, or has multiple parents
-                # It its own dominator
-                node.linear_dominator = node.key
-                return None
-            parent_node = self._nodes[node.parent_keys[0]]
-            if len(parent_node.child_keys) > 1:
-                # The parent has multiple children, so *this* node is the
-                # dominator
-                node.linear_dominator = node.key
-                return None
-            # The parent is already filled in, so add and continue
-            if parent_node.linear_dominator is not None:
-                node.linear_dominator = parent_node.linear_dominator
-                return None
-            # We don't know this node, or its parent node, so start walking to
-            # next
-            return parent_node
-
-        for node in self._nodes.itervalues():
-            # The parent is not filled in, so walk until we get somewhere
-            if node.linear_dominator is not None: #already done
-                continue
-            next_node = check_node(node)
-            if next_node is None:
-                # Nothing more needs to be done
-                continue
-            stack = []
-            while next_node is not None:
-                stack.append(node)
-                node = next_node
-                next_node = check_node(node)
-            # The stack now contains the linear chain, and 'node' should have
-            # been labeled
-            dominator = node.linear_dominator
-            while stack:
-                next_node = stack.pop()
-                next_node.linear_dominator = dominator
-                node = next_node
-
     def _find_gdfo(self):
-        def find_tails():
-            return [node for node in self._nodes.itervalues()
-                       if not node.parent_keys]
-        tails = find_tails()
-        todo = []
-        heappush = heapq.heappush
-        heappop = heapq.heappop
         nodes = self._nodes
-        for node in tails:
+        known_parent_gdfos = {}
+        pending = []
+
+        for node in self._tails:
             node.gdfo = 1
-            heappush(todo, (1, node))
-        processed = 0
-        while todo:
-            gdfo, next = heappop(todo)
-            processed += 1
-            if next.gdfo is not None and gdfo < next.gdfo:
-                # This node was reached from a longer path, we assume it was
-                # enqued correctly with the longer gdfo, so don't continue
-                # processing now
-                continue
-            next_gdfo = gdfo + 1
-            for child_key in next.child_keys:
-                child_node = nodes[child_key]
-                if child_node.gdfo is None or child_node.gdfo < next_gdfo:
-                    # Only enque children when all of their parents have been
-                    # resolved
-                    for parent_key in child_node.parent_keys:
-                        # We know that 'this' parent is counted
-                        if parent_key != next.key:
-                            parent_node = nodes[parent_key]
-                            if parent_node.gdfo is None:
-                                break
-                    else:
-                        child_node.gdfo = next_gdfo
-                        heappush(todo, (next_gdfo, child_node))
-
-    def _get_dominators_to_nodes(self, candidate_nodes):
-        """Get the reverse mapping from dominator_key => candidate_nodes.
-
-        As a side effect, this can also remove potential candidate nodes if we
-        determine that they share a dominator.
-        """
-        dom_to_node = {}
-        keys_to_remove = []
-        for node in candidate_nodes.values():
-            if node.linear_dominator in dom_to_node:
-                # This node already exists, resolve which node supersedes the
-                # other
-                other_node = dom_to_node[node.linear_dominator]
-                # There should be no way that nodes sharing a dominator could
-                # 'tie' for gdfo
-                if other_node.gdfo > node.gdfo:
-                    # The other node has this node as an ancestor
-                    keys_to_remove.append(node.key)
-                else:
-                    # Replace the other node, and set this as the new key
-                    keys_to_remove.append(other_node.key)
-                    dom_to_node[node.linear_dominator] = node
-            else:
-                dom_to_node[node.linear_dominator] = node
-        for key in keys_to_remove:
-            candidate_nodes.pop(key)
-        return dom_to_node
+            pending.append(node)
+
+        while pending:
+            node = pending.pop()
+            for child_key in node.child_keys:
+                child = nodes[child_key]
+                if child_key in known_parent_gdfos:
+                    known_gdfo = known_parent_gdfos[child_key] + 1
+                    present = True
+                else:
+                    known_gdfo = 1
+                    present = False
+                if child.gdfo is None or node.gdfo + 1 > child.gdfo:
+                    child.gdfo = node.gdfo + 1
+                if known_gdfo == len(child.parent_keys):
+                    # We are the last parent updating that node, we can
+                    # continue from there
+                    pending.append(child)
+                    if present:
+                        del known_parent_gdfos[child_key]
+                else:
+                    # Update known_parent_gdfos for a key we couldn't process
+                    known_parent_gdfos[child_key] = known_gdfo
 
     def heads(self, keys):
         """Return the heads from amongst keys.
@@ -217,9 +126,8 @@
         This is done by searching the ancestries of each key.  Any key that is
         reachable from another key is not returned; all the others are.
 
-        This operation scales with the relative depth between any two keys. If
-        any two keys are completely disconnected all ancestry of both sides
-        will be retrieved.
+        This operation scales with the relative depth between any two keys. It
+        uses gdfo to avoid walking all ancestry.
 
         :param keys: An iterable of keys.
         :return: A set of the heads. Note that as a set there is no ordering
@@ -231,114 +139,43 @@
             # NULL_REVISION is only a head if it is the only entry
             candidate_nodes.pop(revision.NULL_REVISION)
             if not candidate_nodes:
-                return set([revision.NULL_REVISION])
+                return frozenset([revision.NULL_REVISION])
         if len(candidate_nodes) < 2:
+            # No or only one candidate
             return frozenset(candidate_nodes)
         heads_key = frozenset(candidate_nodes)
         if heads_key != frozenset(keys):
+            # Mention duplicates
             note('%s != %s', heads_key, frozenset(keys))
+        # Do we have a cached result ?
         try:
             heads = self._known_heads[heads_key]
             return heads
         except KeyError:
-            pass # compute it ourselves
-        dom_to_node = self._get_dominators_to_nodes(candidate_nodes)
-        if len(candidate_nodes) < 2:
-            # We shrunk candidate_nodes and determined a new head
-            return frozenset(candidate_nodes)
-        dom_heads_key = None
-        # Check the linear dominators of these keys, to see if we already
-        # know the heads answer
-        dom_heads_key = frozenset([node.linear_dominator
-                                   for node in candidate_nodes.itervalues()])
-        if dom_heads_key in self._known_heads:
-            # map back into the original keys
-            heads = self._known_heads[dom_heads_key]
-            heads = frozenset([dom_to_node[key].key for key in heads])
-            return heads
-        heads = self._heads_from_candidate_nodes(candidate_nodes, dom_to_node)
+            pass
+        # Let's compute the heads
+        seen = set()
+        pending = []
+        min_gdfo = None
+        for node in candidate_nodes.values():
+            if node.parent_keys:
+                pending.extend(node.parent_keys)
+            if min_gdfo is None or node.gdfo < min_gdfo:
+                min_gdfo = node.gdfo
+        nodes = self._nodes
+        while pending:
+            node_key = pending.pop()
+            if node_key in seen:
+                # node already appears in some ancestry
+                continue
+            seen.add(node_key)
+            node = nodes[node_key]
+            if node.gdfo <= min_gdfo:
+                continue
+            if node.parent_keys:
+                pending.extend(node.parent_keys)
+        heads = heads_key.difference(seen)
         if self.do_cache:
             self._known_heads[heads_key] = heads
-            # Cache the dominator heads
-            if dom_heads_key is not None:
-                dom_heads = frozenset([candidate_nodes[key].linear_dominator
-                                       for key in heads])
-                self._known_heads[dom_heads_key] = dom_heads
         return heads
 
-    def _heads_from_candidate_nodes(self, candidate_nodes, dom_to_node):
-        queue = []
-        to_cleanup = []
-        to_cleanup_append = to_cleanup.append
-        for node in candidate_nodes.itervalues():
-            node.ancestor_of = (node.key,)
-            queue.append((-node.gdfo, node))
-            to_cleanup_append(node)
-        heapq.heapify(queue)
-        # These are nodes that we determined are 'common' that we are no longer
-        # walking
-        # Now we walk nodes until all nodes that are being walked are 'common'
-        num_candidates = len(candidate_nodes)
-        nodes = self._nodes
-        heappop = heapq.heappop
-        heappush = heapq.heappush
-        while queue and len(candidate_nodes) > 1:
-            _, node = heappop(queue)
-            next_ancestor_of = node.ancestor_of
-            if len(next_ancestor_of) == num_candidates:
-                # This node is now considered 'common'
-                # Make sure all parent nodes are marked as such
-                for parent_key in node.parent_keys:
-                    parent_node = nodes[parent_key]
-                    if parent_node.ancestor_of is not None:
-                        parent_node.ancestor_of = next_ancestor_of
-                if node.linear_dominator != node.key:
-                    parent_node = nodes[node.linear_dominator]
-                    if parent_node.ancestor_of is not None:
-                        parent_node.ancestor_of = next_ancestor_of
-                continue
-            if node.parent_keys is None:
-                # This is a ghost
-                continue
-            # Now project the current nodes ancestor list to the parent nodes,
-            # and queue them up to be walked
-            # Note: using linear_dominator speeds things up quite a bit
-            #       enough that we actually start to be slightly faster
-            #       than the default heads() implementation
-            if node.linear_dominator != node.key:
-                # We are at the tip of a long linear region
-                # We know that there is nothing between here and the tail
-                # that is interesting, so skip to the end
-                parent_keys = [node.linear_dominator]
-            else:
-                parent_keys = node.parent_keys
-            for parent_key in parent_keys:
-                if parent_key in candidate_nodes:
-                    candidate_nodes.pop(parent_key)
-                    if len(candidate_nodes) <= 1:
-                        break
-                elif parent_key in dom_to_node:
-                    orig_node = dom_to_node[parent_key]
-                    if orig_node is not node:
-                        if orig_node.key in candidate_nodes:
-                            candidate_nodes.pop(orig_node.key)
-                            if len(candidate_nodes) <= 1:
-                                break
-                parent_node = nodes[parent_key]
-                ancestor_of = parent_node.ancestor_of
-                if ancestor_of is None:
-                    # This node hasn't been walked yet
-                    parent_node.ancestor_of = next_ancestor_of
-                    # Enqueue this node
-                    heappush(queue, (-parent_node.gdfo, parent_node))
-                    to_cleanup_append(parent_node)
-                elif ancestor_of != next_ancestor_of:
-                    # Combine to get the full set of parents
-                    all_ancestors = set(ancestor_of)
-                    all_ancestors.update(next_ancestor_of)
-                    parent_node.ancestor_of = tuple(sorted(all_ancestors))
-        def cleanup():
-            for node in to_cleanup:
-                node.ancestor_of = None
-        cleanup()
-        return frozenset(candidate_nodes)

=== modified file 'bzrlib/_known_graph_pyx.pyx'
--- bzrlib/_known_graph_pyx.pyx	2009-06-16 15:35:14 +0000
+++ bzrlib/_known_graph_pyx.pyx	2009-06-20 08:35:13 +0000
@@ -26,32 +26,31 @@
         pass
 
     object PyFrozenSet_New(object)
+
     object PyTuple_New(Py_ssize_t n)
+    Py_ssize_t PyTuple_GET_SIZE(object t)
+    PyObject * PyTuple_GET_ITEM(object t, Py_ssize_t o)
     void PyTuple_SET_ITEM(object t, Py_ssize_t o, object v)
-    PyObject * PyTuple_GET_ITEM(object t, Py_ssize_t o)
-    Py_ssize_t PyTuple_GET_SIZE(object t)
+
+    Py_ssize_t PyList_GET_SIZE(object l)
+    PyObject * PyList_GET_ITEM(object l, Py_ssize_t o)
+    int PyList_SetItem(object l, Py_ssize_t o, object l) except -1
+    int PyList_Append(object l, object v) except -1
+
+    int PyDict_CheckExact(object d)
+    Py_ssize_t PyDict_Size(object d) except -1
     PyObject * PyDict_GetItem(object d, object k)
-    Py_ssize_t PyDict_Size(object d) except -1
-    int PyDict_CheckExact(object d)
+    int PyDict_SetItem(object d, object k, object v) except -1
+    int PyDict_DelItem(object d, object k) except -1
     int PyDict_Next(object d, Py_ssize_t *pos, PyObject **k, PyObject **v)
-    int PyList_Append(object l, object v) except -1
-    PyObject * PyList_GET_ITEM(object l, Py_ssize_t o)
-    Py_ssize_t PyList_GET_SIZE(object l)
-    int PyDict_SetItem(object d, object k, object v) except -1
-    int PySet_Add(object s, object k) except -1
+
     void Py_INCREF(object)
 
 
-import heapq
-
 from bzrlib import revision
 
-# Define these as cdef objects, so we don't have to getattr them later
-cdef object heappush, heappop, heapify, heapreplace
-heappush = heapq.heappush
-heappop = heapq.heappop
-heapify = heapq.heapify
-heapreplace = heapq.heapreplace
+cdef object NULL_REVISION
+NULL_REVISION = revision.NULL_REVISION
 
 
 cdef class _KnownGraphNode:
@@ -60,10 +59,8 @@
     cdef object key
     cdef object parents
     cdef object children
-    cdef _KnownGraphNode linear_dominator_node
-    cdef public object gdfo # Int
-    # This could also be simplified
-    cdef object ancestor_of
+    cdef public long gdfo
+    cdef int seen
 
     def __init__(self, key):
         cdef int i
@@ -72,14 +69,9 @@
         self.parents = None
 
         self.children = []
-        # oldest ancestor, such that no parents between here and there have >1
-        # child or >1 parent.
-        self.linear_dominator_node = None
         # Greatest distance from origin
         self.gdfo = -1
-        # This will become a tuple of known heads that have this node as an
-        # ancestor
-        self.ancestor_of = None
+        self.seen = 0
 
     property child_keys:
         def __get__(self):
@@ -90,17 +82,9 @@
                 PyList_Append(keys, child.key)
             return keys
 
-    property linear_dominator:
-        def __get__(self):
-            if self.linear_dominator_node is None:
-                return None
-            else:
-                return self.linear_dominator_node.key
-
     cdef clear_references(self):
         self.parents = None
         self.children = None
-        self.linear_dominator_node = None
 
     def __repr__(self):
         cdef _KnownGraphNode node
@@ -113,10 +97,9 @@
         if self.children is not None:
             for node in self.children:
                 child_keys.append(node.key)
-        return '%s(%s  gdfo:%s par:%s child:%s %s)' % (
+        return '%s(%s  gdfo:%s par:%s child:%s)' % (
             self.__class__.__name__, self.key, self.gdfo,
-            parent_keys, child_keys,
-            self.linear_dominator)
+            parent_keys, child_keys)
 
 
 cdef _KnownGraphNode _get_list_node(lst, Py_ssize_t pos):
@@ -134,14 +117,6 @@
     return <_KnownGraphNode>temp_node
 
 
-cdef _KnownGraphNode _peek_node(queue):
-    cdef PyObject *temp_node
-    cdef _KnownGraphNode node
-
-    temp_node = PyTuple_GET_ITEM(<object>PyList_GET_ITEM(queue, 0), 1)
-    node = <_KnownGraphNode>temp_node
-    return node
-
 # TODO: slab allocate all _KnownGraphNode objects.
 #       We already know how many we are going to need, except for a couple of
 #       ghosts that could be allocated on demand.
@@ -152,22 +127,18 @@
     cdef public object _nodes
     cdef object _known_heads
     cdef public int do_cache
-    # Nodes we've touched that we'll need to reset their info when heads() is
-    # done
-    cdef object _to_cleanup
 
     def __init__(self, parent_map, do_cache=True):
         """Create a new KnownGraph instance.
 
         :param parent_map: A dictionary mapping key => parent_keys
         """
+        # tests at pre-allocating the node dict actually slowed things down
         self._nodes = {}
         # Maps {sorted(revision_id, revision_id): heads}
         self._known_heads = {}
-        self._to_cleanup = []
         self.do_cache = int(do_cache)
         self._initialize_nodes(parent_map)
-        self._find_linear_dominators()
         self._find_gdfo()
 
     def __dealloc__(self):
@@ -194,17 +165,17 @@
     def _initialize_nodes(self, parent_map):
         """Populate self._nodes.
 
-        After this has finished, self._nodes will have an entry for every entry
-        in parent_map. Ghosts will have a parent_keys = None, all nodes found
-        will also have .child_keys populated with all known child_keys.
+        After this has finished:
+        - self._nodes will have an entry for every entry in parent_map.
+        - ghosts will have a parent_keys = None,
+        - all nodes found will also have child_keys populated with all known
+          child keys,
         """
         cdef PyObject *temp_key, *temp_parent_keys, *temp_node
         cdef Py_ssize_t pos, pos2, num_parent_keys
         cdef _KnownGraphNode node
         cdef _KnownGraphNode parent_node
 
-        nodes = self._nodes
-
         if not PyDict_CheckExact(parent_map):
             raise TypeError('parent_map should be a dict of {key:parent_keys}')
         # for key, parent_keys in parent_map.iteritems():
@@ -212,14 +183,13 @@
         while PyDict_Next(parent_map, &pos, &temp_key, &temp_parent_keys):
             key = <object>temp_key
             parent_keys = <object>temp_parent_keys
+            num_parent_keys = len(parent_keys)
             node = self._get_or_create_node(key)
             # We know how many parents, so we could pre allocate an exact sized
             # tuple here
-            num_parent_keys = len(parent_keys)
             parent_nodes = PyTuple_New(num_parent_keys)
             # We use iter here, because parent_keys maybe be a list or tuple
             for pos2 from 0 <= pos2 < num_parent_keys:
-                parent_key = parent_keys[pos2]
                 parent_node = self._get_or_create_node(parent_keys[pos2])
                 # PyTuple_SET_ITEM will steal a reference, so INCREF first
                 Py_INCREF(parent_node)
@@ -227,136 +197,54 @@
                 PyList_Append(parent_node.children, node)
             node.parents = parent_nodes
 
-    cdef _KnownGraphNode _check_is_linear(self, _KnownGraphNode node):
-        """Check to see if a given node is part of a linear chain."""
-        cdef _KnownGraphNode parent_node
-        if node.parents is None or PyTuple_GET_SIZE(node.parents) != 1:
-            # This node is either a ghost, a tail, or has multiple parents
-            # It its own dominator
-            node.linear_dominator_node = node
-            return None
-        parent_node = _get_parent(node.parents, 0)
-        if PyList_GET_SIZE(parent_node.children) > 1:
-            # The parent has multiple children, so *this* node is the
-            # dominator
-            node.linear_dominator_node = node
-            return None
-        # The parent is already filled in, so add and continue
-        if parent_node.linear_dominator_node is not None:
-            node.linear_dominator_node = parent_node.linear_dominator_node
-            return None
-        # We don't know this node, or its parent node, so start walking to
-        # next
-        return parent_node
-
-    def _find_linear_dominators(self):
-        """
-        For any given node, the 'linear dominator' is an ancestor, such that
-        all parents between this node and that one have a single parent, and a
-        single child. So if A->B->C->D then B,C,D all have a linear dominator
-        of A.
-
-        There are two main benefits:
-        1) When walking the graph, we can jump to the nearest linear dominator,
-           rather than walking all of the nodes inbetween.
-        2) When caching heads() results, dominators give the "same" results as
-           their children. (If the dominator is a head, then the descendant is
-           a head, if the dominator is not a head, then the child isn't
-           either.)
-        """
-        cdef PyObject *temp_node
-        cdef Py_ssize_t pos
-        cdef _KnownGraphNode node
-        cdef _KnownGraphNode next_node
-        cdef _KnownGraphNode dominator
-        cdef int i, num_elements
-
-        pos = 0
-        while PyDict_Next(self._nodes, &pos, NULL, &temp_node):
-            node = <_KnownGraphNode>temp_node
-            # The parent is not filled in, so walk until we get somewhere
-            if node.linear_dominator_node is not None: #already done
-                continue
-            next_node = self._check_is_linear(node)
-            if next_node is None:
-                # Nothing more needs to be done
-                continue
-            stack = []
-            while next_node is not None:
-                PyList_Append(stack, node)
-                node = next_node
-                next_node = self._check_is_linear(node)
-            # The stack now contains the linear chain, and 'node' should have
-            # been labeled
-            dominator = node.linear_dominator_node
-            num_elements = len(stack)
-            for i from num_elements > i >= 0:
-                next_node = _get_list_node(stack, i)
-                next_node.linear_dominator_node = dominator
-                node = next_node
-
-    cdef object _find_tails(self):
-        cdef object tails
-        cdef PyObject *temp_node
-        cdef Py_ssize_t pos
-        cdef _KnownGraphNode node
+    def _find_tails(self):
+        cdef PyObject *temp_node
+        cdef _KnownGraphNode node
+        cdef Py_ssize_t pos
 
         tails = []
         pos = 0
         while PyDict_Next(self._nodes, &pos, NULL, &temp_node):
             node = <_KnownGraphNode>temp_node
             if node.parents is None or PyTuple_GET_SIZE(node.parents) == 0:
+                node.gdfo = 1
                 PyList_Append(tails, node)
         return tails
 
     def _find_gdfo(self):
-        cdef Py_ssize_t pos, pos2
         cdef _KnownGraphNode node
-        cdef _KnownGraphNode child_node
-        cdef _KnownGraphNode parent_node
-        cdef int replace_node, missing_parent
-
-        tails = self._find_tails()
-        todo = []
-        for pos from 0 <= pos < PyList_GET_SIZE(tails):
-            node = _get_list_node(tails, pos)
-            node.gdfo = 1
-            PyList_Append(todo, (1, node))
-        # No need to heapify, because all tails have priority=1
-        while PyList_GET_SIZE(todo) > 0:
-            node = _peek_node(todo)
+        cdef _KnownGraphNode child
+        cdef PyObject *temp
+        cdef Py_ssize_t pos
+        cdef int replace
+        cdef Py_ssize_t last_item
+        cdef long next_gdfo
+
+        pending = self._find_tails()
+
+        last_item = PyList_GET_SIZE(pending) - 1
+        while last_item >= 0:
+            # Avoid pop followed by push, instead, peek, and replace
+            # timing shows this is 930ms => 770ms for OOo
+            node = _get_list_node(pending, last_item)
+            last_item = last_item - 1
             next_gdfo = node.gdfo + 1
-            replace_node = 1
             for pos from 0 <= pos < PyList_GET_SIZE(node.children):
-                child_node = _get_list_node(node.children, pos)
-                # We should never have numbered children before we numbered
-                # a parent
-                if child_node.gdfo != -1:
-                    continue
-                # Only enque children when all of their parents have been
-                # resolved. With a single parent, we can just take 'this' value
-                child_gdfo = next_gdfo
-                if PyTuple_GET_SIZE(child_node.parents) > 1:
-                    missing_parent = 0
-                    for pos2 from 0 <= pos2 < PyTuple_GET_SIZE(child_node.parents):
-                        parent_node = _get_parent(child_node.parents, pos2)
-                        if parent_node.gdfo == -1:
-                            missing_parent = 1
-                            break
-                        if parent_node.gdfo >= child_gdfo:
-                            child_gdfo = parent_node.gdfo + 1
-                    if missing_parent:
-                        # One of the parents is not numbered, so wait until we get
-                        # back here
-                        continue
-                child_node.gdfo = child_gdfo
-                if replace_node:
-                    heapreplace(todo, (child_gdfo, child_node))
-                    replace_node = 0
-                else:
-                    heappush(todo, (child_gdfo, child_node))
-            if replace_node:
-                heappop(todo)
+                child = _get_list_node(node.children, pos)
+                if next_gdfo > child.gdfo:
+                    child.gdfo = next_gdfo
+                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):
+                        Py_INCREF(child) # SetItem steals a ref
+                        PyList_SetItem(pending, last_item, child)
+                    else:
+                        PyList_Append(pending, child)
+                    # 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.
@@ -364,9 +252,8 @@
         This is done by searching the ancestries of each key.  Any key that is
         reachable from another key is not returned; all the others are.
 
-        This operation scales with the relative depth between any two keys. If
-        any two keys are completely disconnected all ancestry of both sides
-        will be retrieved.
+        This operation scales with the relative depth between any two keys. It
+        uses gdfo to avoid walking all ancestry.
 
         :param keys: An iterable of keys.
         :return: A set of the heads. Note that as a set there is no ordering
@@ -375,231 +262,78 @@
         """
         cdef PyObject *maybe_node
         cdef PyObject *maybe_heads
+        cdef PyObject *temp_node
+        cdef _KnownGraphNode node
+        cdef Py_ssize_t pos, last_item
+        cdef long min_gdfo
 
         heads_key = PyFrozenSet_New(keys)
         maybe_heads = PyDict_GetItem(self._known_heads, heads_key)
         if maybe_heads != NULL:
             return <object>maybe_heads
-
         # Not cached, compute it ourselves
         candidate_nodes = {}
-        nodes = self._nodes
         for key in keys:
-            maybe_node = PyDict_GetItem(nodes, key)
+            maybe_node = PyDict_GetItem(self._nodes, key)
             if maybe_node == NULL:
                 raise KeyError('key %s not in nodes' % (key,))
             PyDict_SetItem(candidate_nodes, key, <object>maybe_node)
-        if revision.NULL_REVISION in candidate_nodes:
+        maybe_node = PyDict_GetItem(candidate_nodes, NULL_REVISION)
+        if maybe_node != NULL:
             # NULL_REVISION is only a head if it is the only entry
-            candidate_nodes.pop(revision.NULL_REVISION)
+            candidate_nodes.pop(NULL_REVISION)
             if not candidate_nodes:
-                return set([revision.NULL_REVISION])
+                return frozenset([NULL_REVISION])
             # The keys changed, so recalculate heads_key
             heads_key = PyFrozenSet_New(candidate_nodes)
-        if len(candidate_nodes) < 2:
+        if PyDict_Size(candidate_nodes) < 2:
             return heads_key
-        dom_to_node = self._get_dominators_to_nodes(candidate_nodes)
-        if PyDict_Size(candidate_nodes) < 2:
-            return frozenset(candidate_nodes)
-        dom_lookup_key, heads = self._heads_from_dominators(candidate_nodes,
-                                                            dom_to_node)
-        if heads is not None:
-            if self.do_cache:
-                # This heads was not in the cache, or it would have been caught
-                # earlier, but the dom head *was*, so do the simple cache
-                PyDict_SetItem(self._known_heads, heads_key, heads)
-            return heads
-        heads = self._heads_from_candidate_nodes(candidate_nodes, dom_to_node)
+
+        cleanup = []
+        pending = []
+        # 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
+        # not added to seen()
+        pos = 0
+        while PyDict_Next(candidate_nodes, &pos, NULL, &temp_node):
+            node = <_KnownGraphNode>temp_node
+            if node.parents is not None:
+                pending.extend(node.parents)
+            if node.gdfo < min_gdfo:
+                min_gdfo = node.gdfo
+
+        # Now do all the real work
+        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
+                continue
+            PyList_Append(cleanup, node)
+            node.seen = 1
+            if node.gdfo <= min_gdfo:
+                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)
+                    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)
+        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:
-            self._cache_heads(heads, heads_key, dom_lookup_key, candidate_nodes)
+            PyDict_SetItem(self._known_heads, heads_key, heads)
         return heads
-
-    cdef object _cache_heads(self, heads, heads_key, dom_lookup_key,
-                             candidate_nodes):
-        cdef PyObject *maybe_node
-        cdef _KnownGraphNode node
-
-        PyDict_SetItem(self._known_heads, heads_key, heads)
-        dom_heads = []
-        for key in heads:
-            maybe_node = PyDict_GetItem(candidate_nodes, key)
-            if maybe_node == NULL:
-                raise KeyError
-            node = <_KnownGraphNode>maybe_node
-            PyList_Append(dom_heads, node.linear_dominator_node.key)
-        PyDict_SetItem(self._known_heads, dom_lookup_key,
-                       PyFrozenSet_New(dom_heads))
-
-    cdef _get_dominators_to_nodes(self, candidate_nodes):
-        """Get the reverse mapping from dominator_key => candidate_nodes.
-
-        As a side effect, this can also remove potential candidate nodes if we
-        determine that they share a dominator.
-        """
-        cdef Py_ssize_t pos
-        cdef _KnownGraphNode node, other_node
-        cdef PyObject *temp_node
-        cdef PyObject *maybe_node
-
-        dom_to_node = {}
-        keys_to_remove = []
-        pos = 0
-        while PyDict_Next(candidate_nodes, &pos, NULL, &temp_node):
-            node = <_KnownGraphNode>temp_node
-            dom_key = node.linear_dominator_node.key
-            maybe_node = PyDict_GetItem(dom_to_node, dom_key)
-            if maybe_node == NULL:
-                PyDict_SetItem(dom_to_node, dom_key, node)
-            else:
-                other_node = <_KnownGraphNode>maybe_node
-                # These nodes share a dominator, one of them obviously
-                # supersedes the other, figure out which
-                if other_node.gdfo > node.gdfo:
-                    PyList_Append(keys_to_remove, node.key)
-                else:
-                    # This wins, replace the other
-                    PyList_Append(keys_to_remove, other_node.key)
-                    PyDict_SetItem(dom_to_node, dom_key, node)
-        for pos from 0 <= pos < PyList_GET_SIZE(keys_to_remove):
-            key = <object>PyList_GET_ITEM(keys_to_remove, pos)
-            candidate_nodes.pop(key)
-        return dom_to_node
-
-    cdef object _heads_from_dominators(self, candidate_nodes, dom_to_node):
-        cdef PyObject *maybe_heads
-        cdef PyObject *maybe_node
-        cdef _KnownGraphNode node
-        cdef Py_ssize_t pos
-        cdef PyObject *temp_node
-
-        dom_list_key = []
-        pos = 0
-        while PyDict_Next(candidate_nodes, &pos, NULL, &temp_node):
-            node = <_KnownGraphNode>temp_node
-            PyList_Append(dom_list_key, node.linear_dominator_node.key)
-        dom_lookup_key = PyFrozenSet_New(dom_list_key)
-        maybe_heads = PyDict_GetItem(self._known_heads, dom_lookup_key)
-        if maybe_heads == NULL:
-            return dom_lookup_key, None
-        # We need to map back from the dominator head to the original keys
-        dom_heads = <object>maybe_heads
-        heads = []
-        for dom_key in dom_heads:
-            maybe_node = PyDict_GetItem(dom_to_node, dom_key)
-            if maybe_node == NULL:
-                # Should never happen
-                raise KeyError
-            node = <_KnownGraphNode>maybe_node
-            PyList_Append(heads, node.key)
-        return dom_lookup_key, PyFrozenSet_New(heads)
-
-    cdef int _process_parent(self, _KnownGraphNode node,
-                             _KnownGraphNode parent_node,
-                             candidate_nodes, dom_to_node,
-                             queue, int *replace_item) except -1:
-        """Process the parent of a node, seeing if we need to walk it."""
-        cdef PyObject *maybe_candidate
-        cdef PyObject *maybe_node
-        cdef _KnownGraphNode dom_child_node
-        maybe_candidate = PyDict_GetItem(candidate_nodes, parent_node.key)
-        if maybe_candidate != NULL:
-            candidate_nodes.pop(parent_node.key)
-            # We could pass up a flag that tells the caller to stop processing,
-            # but it doesn't help much, and makes the code uglier
-            return 0
-        maybe_node = PyDict_GetItem(dom_to_node, parent_node.key)
-        if maybe_node != NULL:
-            # This is a dominator of a node
-            dom_child_node = <_KnownGraphNode>maybe_node
-            if dom_child_node is not node:
-                # It isn't a dominator of a node we are searching, so we should
-                # remove it from the search
-                maybe_candidate = PyDict_GetItem(candidate_nodes, dom_child_node.key)
-                if maybe_candidate != NULL:
-                    candidate_nodes.pop(dom_child_node.key)
-                    return 0
-        if parent_node.ancestor_of is None:
-            # This node hasn't been walked yet, so just project node's ancestor
-            # info directly to parent_node, and enqueue it for later processing
-            parent_node.ancestor_of = node.ancestor_of
-            if replace_item[0]:
-                heapreplace(queue, (-parent_node.gdfo, parent_node))
-                replace_item[0] = 0
-            else:
-                heappush(queue, (-parent_node.gdfo, parent_node))
-            PyList_Append(self._to_cleanup, parent_node)
-        elif parent_node.ancestor_of != node.ancestor_of:
-            # Combine to get the full set of parents
-            # Rewrite using PySet_* functions, unfortunately you have to use
-            # PySet_Add since there is no PySet_Update... :(
-            all_ancestors = set(parent_node.ancestor_of)
-            for k in node.ancestor_of:
-                PySet_Add(all_ancestors, k)
-            parent_node.ancestor_of = tuple(sorted(all_ancestors))
-        return 0
-
-    cdef object _heads_from_candidate_nodes(self, candidate_nodes, dom_to_node):
-        cdef _KnownGraphNode node
-        cdef _KnownGraphNode parent_node
-        cdef Py_ssize_t num_candidates
-        cdef int num_parents, replace_item
-        cdef Py_ssize_t pos
-        cdef PyObject *temp_node
-
-        queue = []
-        pos = 0
-        while PyDict_Next(candidate_nodes, &pos, NULL, &temp_node):
-            node = <_KnownGraphNode>temp_node
-            node.ancestor_of = (node.key,)
-            PyList_Append(queue, (-node.gdfo, node))
-            PyList_Append(self._to_cleanup, node)
-        heapify(queue)
-        # These are nodes that we determined are 'common' that we are no longer
-        # walking
-        # Now we walk nodes until all nodes that are being walked are 'common'
-        num_candidates = len(candidate_nodes)
-        replace_item = 0
-        while PyList_GET_SIZE(queue) > 0 and PyDict_Size(candidate_nodes) > 1:
-            if replace_item:
-                # We still need to pop the smallest member out of the queue
-                # before we peek again
-                heappop(queue)
-                if PyList_GET_SIZE(queue) == 0:
-                    break
-            # peek at the smallest item. We don't pop, because we expect we'll
-            # need to push more things into the queue anyway
-            node = _peek_node(queue)
-            replace_item = 1
-            if PyTuple_GET_SIZE(node.ancestor_of) == num_candidates:
-                # This node is now considered 'common'
-                # Make sure all parent nodes are marked as such
-                for pos from 0 <= pos < PyTuple_GET_SIZE(node.parents):
-                    parent_node = _get_parent(node.parents, pos)
-                    if parent_node.ancestor_of is not None:
-                        parent_node.ancestor_of = node.ancestor_of
-                if node.linear_dominator_node is not node:
-                    parent_node = node.linear_dominator_node
-                    if parent_node.ancestor_of is not None:
-                        parent_node.ancestor_of = node.ancestor_of
-                continue
-            if node.parents is None:
-                # This is a ghost
-                continue
-            # Now project the current nodes ancestor list to the parent nodes,
-            # and queue them up to be walked
-            if node.linear_dominator_node is not node:
-                # We are at the tip of a long linear region
-                # We know that there is nothing between here and the tail
-                # that is interesting, so skip to the end
-                self._process_parent(node, node.linear_dominator_node,
-                                     candidate_nodes, dom_to_node, queue, &replace_item)
-            else:
-                for pos from 0 <= pos < PyTuple_GET_SIZE(node.parents):
-                    parent_node = _get_parent(node.parents, pos)
-                    self._process_parent(node, parent_node, candidate_nodes,
-                                         dom_to_node, queue, &replace_item)
-        for pos from 0 <= pos < PyList_GET_SIZE(self._to_cleanup):
-            node = _get_list_node(self._to_cleanup, pos)
-            node.ancestor_of = None
-        self._to_cleanup = []
-        return PyFrozenSet_New(candidate_nodes)

=== modified file 'bzrlib/tests/test__known_graph.py'
--- bzrlib/tests/test__known_graph.py	2009-06-16 15:35:14 +0000
+++ bzrlib/tests/test__known_graph.py	2009-06-20 08:35:13 +0000
@@ -71,10 +71,6 @@
     def make_known_graph(self, ancestry):
         return self.module.KnownGraph(ancestry, do_cache=self.do_cache)
 
-    def assertDominator(self, graph, rev, dominator):
-        node = graph._nodes[rev]
-        self.assertEqual(dominator, node.linear_dominator)
-
     def assertGDFO(self, graph, rev, gdfo):
         node = graph._nodes[rev]
         self.assertEqual(gdfo, node.gdfo)
@@ -88,29 +84,6 @@
         self.assertEqual(['rev4'], sorted(graph._nodes['rev3'].child_keys))
         self.assertEqual(['rev4'], sorted(graph._nodes['rev2b'].child_keys))
 
-    def test_dominators_ancestry_1(self):
-        graph = self.make_known_graph(test_graph.ancestry_1)
-        self.assertDominator(graph, 'rev1', NULL_REVISION)
-        self.assertDominator(graph, 'rev2b', 'rev2b')
-        self.assertDominator(graph, 'rev2a', 'rev2a')
-        self.assertDominator(graph, 'rev3', 'rev2a')
-        self.assertDominator(graph, 'rev4', 'rev4')
-
-    def test_dominators_feature_branch(self):
-        graph = self.make_known_graph(test_graph.feature_branch)
-        self.assertDominator(graph, 'rev1', NULL_REVISION)
-        self.assertDominator(graph, 'rev2b', NULL_REVISION)
-        self.assertDominator(graph, 'rev3b', NULL_REVISION)
-
-    def test_dominators_extended_history_shortcut(self):
-        graph = self.make_known_graph(test_graph.extended_history_shortcut)
-        self.assertDominator(graph, 'a', NULL_REVISION)
-        self.assertDominator(graph, 'b', 'b')
-        self.assertDominator(graph, 'c', 'b')
-        self.assertDominator(graph, 'd', 'b')
-        self.assertDominator(graph, 'e', 'e')
-        self.assertDominator(graph, 'f', 'f')
-
     def test_gdfo_ancestry_1(self):
         graph = self.make_known_graph(test_graph.ancestry_1)
         self.assertGDFO(graph, 'rev1', 2)
@@ -229,3 +202,14 @@
         self.assertEqual(set(['z']), graph.heads(['w', 's', 'z']))
         self.assertEqual(set(['w', 'q']), graph.heads(['w', 's', 'q']))
         self.assertEqual(set(['z']), graph.heads(['s', 'z']))
+
+    def test_heads_with_ghost(self):
+        graph = self.make_known_graph(test_graph.with_ghost)
+        self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
+        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c']))
+        self.assertEqual(set(['a', 'g']), graph.heads(['a', 'g']))
+        self.assertEqual(set(['f', 'g']), graph.heads(['f', 'g']))
+        self.assertEqual(set(['c']), graph.heads(['c', 'g']))
+        self.assertEqual(set(['c']), graph.heads(['c', 'b', 'd', 'g']))
+        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'e', 'g']))
+        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'f']))

=== modified file 'tools/time_graph.py'
--- tools/time_graph.py	2009-06-12 18:05:15 +0000
+++ tools/time_graph.py	2009-06-20 08:35:13 +0000
@@ -16,12 +16,15 @@
 from bzrlib.ui import text
 
 p = optparse.OptionParser()
+p.add_option('--quick', default=False, action='store_true')
 p.add_option('--max-combinations', default=500, type=int)
 p.add_option('--lsprof', default=None, type=str)
 opts, args = p.parse_args(sys.argv[1:])
+
 trace.enable_default_logging()
 ui.ui_factory = text.TextUIFactory()
 
+begin = time.clock()
 if len(args) >= 1:
     b = branch.Branch.open(args[0])
 else:
@@ -33,8 +36,9 @@
                          if p[1] is not None)
 finally:
     b.unlock()
+end = time.clock()
 
-print 'Found %d nodes' % (len(parent_map),)
+print 'Found %d nodes, loaded in %.3fs' % (len(parent_map), end - begin)
 
 def all_heads_comp(g, combinations):
     h = []
@@ -47,6 +51,7 @@
     finally:
         pb.finished()
     return h
+
 combinations = []
 # parents = parent_map.keys()
 # for p1 in parents:
@@ -61,37 +66,57 @@
 for revision_id, parent_ids in parent_map.iteritems():
     if parent_ids is not None and len(parent_ids) > 1:
         combinations.append(parent_ids)
+# The largest portion of the graph that has to be walked for a heads() check
+# combinations = [('[e-mail]-20090312021943-tu6tcog48aiujx4s',
+#                  '[e-mail]-20090312130552-09xa2xsitf6rilzc')]
 if opts.max_combinations > 0 and len(combinations) > opts.max_combinations:
     combinations = random.sample(combinations, opts.max_combinations)
 
 print '      %d combinations' % (len(combinations),)
-t1 = time.clock()
-known_g = _known_graph_py.KnownGraph(parent_map)
-if opts.lsprof is not None:
-    h_known = commands.apply_lsprofiled(opts.lsprof,
-        all_heads_comp, known_g, combinations)
-else:
-    h_known = all_heads_comp(known_g, combinations)
-t2 = time.clock()
-print "Known: %.3fs" % (t2-t1,)
-print "  %s" % (graph._counters,)
-t1 = time.clock()
-known_g = _known_graph_pyx.KnownGraph(parent_map)
-if opts.lsprof is not None:
-    h_known = commands.apply_lsprofiled(opts.lsprof,
-        all_heads_comp, known_g, combinations)
-else:
-    h_known = all_heads_comp(known_g, combinations)
-t2 = time.clock()
-print "Known (pyx): %.3fs" % (t2-t1,)
-print "  %s" % (graph._counters,)
-simple_g = graph.Graph(graph.DictParentsProvider(parent_map))
-graph._counters[1] = 0
-graph._counters[2] = 0
-h_simple = all_heads_comp(simple_g, combinations)
-t3 = time.clock()
-print "Orig: %.3fs" % (t3-t2,)
-print "  %s" % (graph._counters,)
-if h_simple != h_known:
-    import pdb; pdb.set_trace()
-print 'ratio: %.3fs' % ((t2-t1) / (t3-t2))
+
+def combi_graph(graph_klass, comb):
+    # DEBUG
+    graph._counters[1] = 0
+    graph._counters[2] = 0
+
+    begin = time.clock()
+    g = graph_klass(parent_map)
+    if opts.lsprof is not None:
+        heads = commands.apply_lsprofiled(opts.lsprof, all_heads_comp, g, comb)
+    else:
+        heads = all_heads_comp(g, comb)
+    end = time.clock()
+    return dict(elapsed=(end - begin), graph=g, heads=heads)
+
+def report(name, g):
+    print '%s: %.3fs' % (name, g['elapsed'])
+    counters_used = False
+    for c in graph._counters:
+        if c:
+            counters_used = True
+    if counters_used:
+        print '  %s' % (graph._counters,)
+
+known_python = combi_graph(_known_graph_py.KnownGraph, combinations)
+report('Known', known_python)
+
+known_pyrex = combi_graph(_known_graph_pyx.KnownGraph, combinations)
+report('Known (pyx)', known_pyrex)
+
+def _simple_graph(parent_map):
+    return graph.Graph(graph.DictParentsProvider(parent_map))
+
+if opts.quick:
+    if known_python['heads'] != known_pyrex['heads']:
+        import pdb; pdb.set_trace()
+    print 'ratio: %.1f:1 faster' % (
+        known_python['elapsed'] / known_pyrex['elapsed'],)
+else:
+    orig = combi_graph(_simple_graph, combinations)
+    report('Orig', orig)
+
+    if orig['heads'] != known_pyrex['heads']:
+        import pdb; pdb.set_trace()
+
+    print 'ratio: %.1f:1 faster' % (
+        orig['elapsed'] / known_pyrex['elapsed'],)