Rev 4387: Adding some debugging counters shows that in http://bazaar.launchpad.net/~jameinel/bzr/1.16-better_heads

[John Arbash Meinel]

At http://bazaar.launchpad.net/~jameinel/bzr/1.16-better_heads

------------------------------------------------------------
revno: 4387
revision-id: john at arbash-meinel.com-20090610163143-unn2fkyrcuwtkf62
parent: john at arbash-meinel.com-20090609003046-kg75mbqk000u0475
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Wed 2009-06-10 11:31:43 -0500
message:
  Adding some debugging counters shows that
  1) Without linear_dominator we are still a little faster. 0.68:1
  2) Without linear_dominator we access 86% of the entries that Graph does
  3) With linear_dominator we are *much* faster 0.46:1, and access 57% of
     the same keys.
-------------- next part --------------
=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py	2009-06-08 22:04:34 +0000
+++ b/bzrlib/graph.py	2009-06-10 16:31:43 +0000
@@ -63,6 +63,8 @@
     def get_parent_map(self, keys):
         """See _StackedParentsProvider.get_parent_map"""
         ancestry = self.ancestry
+        _counters[1] += len(keys)
+        _counters[2] += 1
         return dict((k, ancestry[k]) for k in keys if k in ancestry)
 
 
@@ -1345,6 +1347,7 @@
             order if they need it.
         """
         candidate_nodes = dict((key, self._nodes[key]) for key in keys)
+        _counters[0] += len(candidate_nodes)
         if revision.NULL_REVISION in candidate_nodes:
             # NULL_REVISION is only a head if it is the only entry
             candidate_nodes.pop(revision.NULL_REVISION)
@@ -1400,10 +1403,12 @@
                 # This node is now considered 'common'
                 # Make sure all parent nodes are marked as such
                 for parent_key in node.parent_keys:
+                    _counters[0] += 1
                     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:
+                    _counters[0] += 1
                     parent_node = nodes[node.linear_dominator]
                     if parent_node.ancestor_of is not None:
                         parent_node.ancestor_of = next_ancestor_of
@@ -1430,6 +1435,7 @@
                     candidate_nodes.pop(parent_key)
                     if len(candidate_nodes) <= 1:
                         break
+                _counters[0] += 1
                 parent_node = nodes[parent_key]
                 ancestor_of = parent_node.ancestor_of
                 if ancestor_of is None:

=== modified file 'tools/time_graph.py'
--- a/tools/time_graph.py	2009-06-09 00:30:46 +0000
+++ b/tools/time_graph.py	2009-06-10 16:31:43 +0000
@@ -33,7 +33,8 @@
     pb = ui.ui_factory.nested_progress_bar()
     try:
         for idx, combo in enumerate(combinations):
-            pb.update('proc', idx, len(combinations))
+            if idx & 0x1f == 0:
+                pb.update('proc', idx, len(combinations))
             h.append(g.heads(combo))
     finally:
         pb.finished()
@@ -67,9 +68,12 @@
 print "Known: %.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))