Rev 2399: Make Graph.get_descendants be lazy, and return the internal reference to avoid copy-overhead. Also increase GraphDelta performance. in file:///home/robertc/source/baz/netsim/
Robert Collins
robertc at robertcollins.net
Tue Apr 3 08:43:10 BST 2007
At file:///home/robertc/source/baz/netsim/
------------------------------------------------------------
revno: 2399
revision-id: robertc at robertcollins.net-20070403074302-fo3x80f961hh7e7f
parent: robertc at robertcollins.net-20070402072850-a7b90xg48rdujr63
committer: Robert Collins <robertc at robertcollins.net>
branch nick: netsim
timestamp: Tue 2007-04-03 17:43:02 +1000
message:
Make Graph.get_descendants be lazy, and return the internal reference to avoid copy-overhead. Also increase GraphDelta performance.
modified:
bzrlib/graph.py graph.py-20050905070950-b47dce53236c5e48
bzrlib/revision.py revision.py-20050309040759-e77802c08f3999d5
=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py 2007-04-02 07:28:50 +0000
+++ b/bzrlib/graph.py 2007-04-03 07:43:02 +0000
@@ -117,34 +117,42 @@
self.roots = set([])
self.ghosts = set([])
self._graph_ancestors = {}
- self._graph_descendants = {}
+ self._graph_descendants = None
def __eq__(self, other):
- return isinstance(other, Graph) and self.__dict__ == other.__dict__
+ if not isinstance(other, Graph):
+ return False
+ if self._graph_descendants and not other._graph_descendants:
+ self._generate_descendants()
+ return self.__dict__ == other.__dict__
def add_ghost(self, node_id):
"""Add a ghost to the graph."""
self.ghosts.add(node_id)
- self._ensure_descendant(node_id)
+ if self._graph_descendants is not None:
+ self._graph_descendants.setdefault(node_id, {})
def add_node(self, node_id, parent_ids):
"""Add node_id to the graph with parent_ids as its parents."""
if parent_ids == []:
self.roots.add(node_id)
self._graph_ancestors[node_id] = list(parent_ids)
- self._ensure_descendant(node_id)
- for parent in parent_ids:
- self._ensure_descendant(parent)
- self._graph_descendants[parent][node_id] = 1
+ if self._graph_descendants is not None:
+ self._graph_descendants.setdefault(node_id, {})
+ for parent in parent_ids:
+ self._graph_descendants.setdefault(parent, {})[node_id] = 1
def changes_from(self, graph_from):
"""Create a GraphDelta from graph_from to self."""
return GraphDelta._changes_from(graph_from, self)
- def _ensure_descendant(self, node_id):
- """Ensure that a descendant lookup for node_id will work."""
- if not node_id in self._graph_descendants:
- self._graph_descendants[node_id] = {}
+ def _generate_descendants(self):
+ """Construct the _graph_descendants node if needed."""
+ self._graph_descendants = {}
+ for node_id in self._graph_ancestors:
+ self._graph_descendants.setdefault(node_id, {})
+ for parent in self._graph_ancestors[node_id]:
+ self._graph_descendants.setdefault(parent, {})[node_id] = 1
def get_ancestors(self):
"""Return a dictionary of graph node:ancestor_list entries."""
@@ -167,16 +175,18 @@
def get_descendants(self):
"""Return a dictionary of graph node:child_node:distance entries."""
- return dict(self._graph_descendants.items())
+ if self._graph_descendants is None:
+ self._generate_descendants()
+ return self._graph_descendants
def get_heads(self):
"""Determine the heads of the graph."""
return set([node for node, descendants in
- self._graph_descendants.items() if not descendants])
+ self.get_descendants().items() if not descendants])
def __repr__(self):
return "Graph ancestors=%s, descendants=%r, ghosts=%r" % (
- self._graph_ancestors, self._graph_descendants, self.ghosts)
+ self._graph_ancestors, self.get_descendants(), self.ghosts)
class GraphDelta(object):
@@ -211,15 +221,16 @@
pending = set(from_.get_heads())
cut_from = set(self.cut_from) # in case its a list
ancestors = from_.get_ancestors()
+ done = set()
while pending:
node = pending.pop()
+ done.add(node)
if node not in cut_from:
try:
result.add_node(node, ancestors[node])
- pending.update(ancestors[node])
+ pending.update(set(ancestors[node]).difference(done))
except KeyError:
result.add_ghost(node)
- pass
return result
@classmethod
@@ -227,9 +238,12 @@
"""Construct a delta from from_ to to."""
result = GraphDelta()
ancestors = from_.get_ancestors()
+ from_nodes = set(ancestors)
to_nodes = set(to.get_ancestors())
- if to_nodes.difference(ancestors):
+ if to_nodes.difference(from_nodes):
raise errors.NotSubGraph(from_, to)
+ if to_nodes == from_nodes:
+ return result
to_heads = to.get_heads()
result.heads = to_heads
# if the heads list is equal to the from_ heads list,
@@ -250,8 +264,10 @@
result.cut_from = from_.get_heads()
return result
pending = set(to_heads)
+ done = set()
while pending:
node = pending.pop()
+ done.add(node)
node_parents = ancestors[node]
for parent in node_parents:
if parent in from_.ghosts:
@@ -261,7 +277,8 @@
continue
if parent in result.heads:
result.heads.remove(parent)
- pending.add(parent)
+ if parent not in done:
+ pending.add(parent)
# remove heads that
return result
=== modified file 'bzrlib/revision.py'
--- a/bzrlib/revision.py 2007-01-17 15:37:08 +0000
+++ b/bzrlib/revision.py 2007-04-03 07:43:02 +0000
@@ -253,7 +253,7 @@
[revision_a, revision_b])
# convert to a NULL_REVISION based graph.
ancestors = graph.get_ancestors()
- descendants = graph.get_descendants()
+ descendants = dict(graph.get_descendants().items())
common = set(graph.get_ancestry(revision_a)).intersection(
set(graph.get_ancestry(revision_b)))
descendants[NULL_REVISION] = {}
More information about the bazaar-commits
mailing list