Rev 4409: Add a failing test for handling nodes that are in the same linear chain. 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: 4409
revision-id: john at arbash-meinel.com-20090612180515-t0cwbjsnve094oik
parent: john at arbash-meinel.com-20090612044424-3kv1qr5wkns35c22
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Fri 2009-06-12 13:05:15 -0500
message:
  Add a failing test for handling nodes that are in the same linear chain.
  
  It fails because the ancestry skipping causes us to miss the fact that the two nodes
  are actually directly related. We could check at the beginning, as the 
  code used to do, but I think that will be incomplete for the more-than-two
  heads cases.
-------------- next part --------------
=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py	2009-06-11 04:28:57 +0000
+++ b/bzrlib/graph.py	2009-06-12 18:05:15 +0000
@@ -1657,6 +1657,7 @@
     return result
 
 
+_counters = [0,0,0,0,0,0,0]
 try:
     from bzrlib._known_graph_pyx import KnownGraph
 except ImportError:

=== modified file 'bzrlib/tests/test__known_graph.py'
--- a/bzrlib/tests/test__known_graph.py	2009-06-10 18:58:02 +0000
+++ b/bzrlib/tests/test__known_graph.py	2009-06-12 18:05:15 +0000
@@ -224,5 +224,8 @@
         self.assertEqual(set(['rev2c', 'rev3a']),
                          graph.heads(['rev2c', 'rev3a']))
 
-
-
+    def test_heads_linear(self):
+        graph = self.make_known_graph(test_graph.racing_shortcuts)
+        self.assertEqual(set(['w']), graph.heads(['w', 's']))
+        self.assertEqual(set(['z']), graph.heads(['w', 's', 'z']))
+        self.assertEqual(set(['w', 'q']), graph.heads(['w', 's', 'q']))

=== added file 'tools/time_graph.py'
--- a/tools/time_graph.py	1970-01-01 00:00:00 +0000
+++ b/tools/time_graph.py	2009-06-12 18:05:15 +0000
@@ -0,0 +1,97 @@
+#!/usr/bin/env python
+import random
+import os
+import time
+import sys
+import optparse
+from bzrlib import (
+    branch,
+    commands,
+    graph,
+    ui,
+    trace,
+    _known_graph_py,
+    _known_graph_pyx,
+    )
+from bzrlib.ui import text
+
+p = optparse.OptionParser()
+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()
+
+if len(args) >= 1:
+    b = branch.Branch.open(args[0])
+else:
+    b = branch.Branch.open('.')
+b.lock_read()
+try:
+    g = b.repository.get_graph()
+    parent_map = dict(p for p in g.iter_ancestry([b.last_revision()])
+                         if p[1] is not None)
+finally:
+    b.unlock()
+
+print 'Found %d nodes' % (len(parent_map),)
+
+def all_heads_comp(g, combinations):
+    h = []
+    pb = ui.ui_factory.nested_progress_bar()
+    try:
+        for idx, combo in enumerate(combinations):
+            if idx & 0x1f == 0:
+                pb.update('proc', idx, len(combinations))
+            h.append(g.heads(combo))
+    finally:
+        pb.finished()
+    return h
+combinations = []
+# parents = parent_map.keys()
+# for p1 in parents:
+#     for p2 in random.sample(parents, 10):
+#         combinations.append((p1, p2))
+# Times for random sampling of 10x1150 of bzrtools
+#   Graph        KnownGraph
+#   96.1s   vs   25.7s  :)
+# Times for 500 'merge parents' from bzr.dev
+#   25.6s   vs   45.0s  :(
+
+for revision_id, parent_ids in parent_map.iteritems():
+    if parent_ids is not None and len(parent_ids) > 1:
+        combinations.append(parent_ids)
+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))