Rev 6033: Don't walk the graph a second time. in http://bazaar.launchpad.net/~jameinel/bzr/2.4-too-much-walking-388269

[John Arbash Meinel]

At http://bazaar.launchpad.net/~jameinel/bzr/2.4-too-much-walking-388269

------------------------------------------------------------
revno: 6033
revision-id: john at arbash-meinel.com-20110815141118-ka5ur3w8lozpc1xg
parent: john at arbash-meinel.com-20110812153748-7olh7g5m2jg75yqq
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 2.4-too-much-walking-388269
timestamp: Mon 2011-08-15 16:11:18 +0200
message:
  Don't walk the graph a second time.
  
  
  The second search seems to always be at least as fast, or possibly faster than
  the first search. However, I've never tripped the assertions, so the walking
  is doing a proper job of always finding truly superfluous start keys.
-------------- next part --------------
=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py	2011-08-12 12:12:35 +0000
+++ b/bzrlib/graph.py	2011-08-15 14:11:18 +0000
@@ -2021,20 +2021,13 @@
     :param depth: How far back to walk.
     """
     heads = _find_possible_heads(parent_map, tip_keys, depth)
-    def first_search():
-        return _run_search(parent_map, heads, set(tip_keys))
-    s, found_heads = first_search()
+    s, found_heads = _run_search(parent_map, heads, set(tip_keys))
+    _, start_keys, exclude_keys, key_count = s.get_result().get_recipe()
     if found_heads:
-        def second_search():
-            return _run_search(parent_map, heads - found_heads,
-                                      set(tip_keys))
-        s2, extra_heads = second_search()
-        result1 = s.get_result()
-        result2 = s2.get_result()
-        assert result1._keys == result2._keys
-        assert not extra_heads
-        return result2.get_recipe()[1:]
-    return s.get_result().get_recipe()[1:]
+        # Anything in found_heads are redundant start_keys, we hit them while
+        # walking, so we can exclude them from the start list.
+        start_keys = set(start_keys).difference(found_heads)
+    return start_keys, exclude_keys, key_count
 
 
 def search_result_from_parent_map(parent_map, missing_keys):