Rev 3112: We only need to find_seen_ancestors for some common nodes. in http://bzr.arbash-meinel.com/branches/bzr/0.93-dev/graph_update

[John Arbash Meinel]

At http://bzr.arbash-meinel.com/branches/bzr/0.93-dev/graph_update

------------------------------------------------------------
revno: 3112
revision-id:john at arbash-meinel.com-20071220220939-xp7tdaa71hu23sk5
parent: john at arbash-meinel.com-20071220184915-vf7uo3xk18aj5sd3
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: graph_update
timestamp: Thu 2007-12-20 16:09:39 -0600
message:
  We only need to find_seen_ancestors for some common nodes.
  If it is a tip that shows up in common, we are already searching
  its ancestors there.
  If it is a newly common node, then we need to jump to the tips
  for the other searcher.
modified:
  bzrlib/graph.py                graph_walker.py-20070525030359-y852guab65d4wtn0-1
-------------- next part --------------
=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py	2007-12-20 18:49:15 +0000
+++ b/bzrlib/graph.py	2007-12-20 22:09:39 +0000
@@ -376,8 +376,7 @@
             parent_map = self.get_parent_map(next_to_search)
             ancestors = set()
             # advance searches
-            new_common = set()
-            new_common.update(common_walker.step(parent_map))
+            common_walker.step(parent_map)
             for candidate in active_searchers.keys():
                 try:
                     searcher = active_searchers[candidate]
@@ -392,6 +391,8 @@
                 else:
                     del active_searchers[candidate]
             # process found nodes
+            new_common = set()
+            new_common_tips = set()
             for ancestor in ancestors:
                 if ancestor in candidate_heads:
                     candidate_heads.remove(ancestor)
@@ -405,8 +406,9 @@
                 # it may meet up with a known common node
                 if ancestor in common_walker.seen:
                     # some searcher has encountered our known common nodes:
-                    # just stop it
-                    new_common.add(ancestor)
+                    # just stop it. we don't need to check the ancestry,
+                    # because this is a tip running into common.
+                    new_common_tips.add(ancestor)
                 else:
                     # or it may have been just reached by all the searchers:
                     for searcher in searchers.itervalues():
@@ -417,23 +419,27 @@
                         # making it be known as a descendant of all candidates,
                         # so we can stop searching it, and any seen ancestors
                         new_common.add(ancestor)
-            # After we stop searching nodes, figure out what the next nodes are
-            # going to be, so we can preload them
-            next_to_search = set()
+            if new_common_tips:
+                for searcher in searchers.itervalues():
+                    searcher.stop_searching_any(new_common_tips)
             if new_common:
                 known_common = common_walker.seen - new_common
                 for searcher in searchers.itervalues():
                     seen_ancestors = searcher.find_seen_ancestors(new_common,
                                                                   known_common)
                     stopped = searcher.stop_searching_any(seen_ancestors)
-                    # Make sure to put all seen ancestors into the common set. This
-                    # will allow the common_walker to jump past them.
-                    new_common.update(stopped)
+                    # Start walking the stopped nodes in the common searcher
+                    # Also, add all seen ancesters to the common seen list, so
+                    # the common walker doesn't have to search them again if
+                    # they show up by a different path (we are already
+                    # searching their ancestors).
                     common_walker.start_searching(stopped)
                     common_walker.seen.update(seen_ancestors)
+            # After we stop searching nodes, figure out what the next nodes are
+            # going to be, so we can preload them
+            next_to_search = set()
             for searcher in searchers.itervalues():
                 next_to_search.update(searcher.will_search())
-            common_walker.start_searching(new_common)
             next_to_search.update(common_walker.will_search())
         return candidate_heads