Rev 4395: A couple of cleanups. in http://bazaar.launchpad.net/~jameinel/bzr/1.16-better_heads
John Arbash Meinel
john at arbash-meinel.com
Thu Jun 11 05:29:06 BST 2009
At http://bazaar.launchpad.net/~jameinel/bzr/1.16-better_heads
------------------------------------------------------------
revno: 4395
revision-id: john at arbash-meinel.com-20090611042857-d9ug6gtlo867ibn2
parent: john at arbash-meinel.com-20090610221322-uv24p5wlgtic7j13
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Wed 2009-06-10 23:28:57 -0500
message:
A couple of cleanups.
left_parent/right_parent didn't show a real-world win, so they have been removed.
The code is quite a bit clearer without them.
-------------- next part --------------
=== modified file 'bzrlib/_known_graph_pyx.pyx'
--- a/bzrlib/_known_graph_pyx.pyx 2009-06-10 22:13:22 +0000
+++ b/bzrlib/_known_graph_pyx.pyx 2009-06-11 04:28:57 +0000
@@ -44,10 +44,6 @@
"""Represents a single object in the known graph."""
cdef object key
- # 99% of all revisions have <= 2 parents, so we pre-allocate space for it,
- # but allow the flexibility of having N parents
- cdef _KnownGraphNode left_parent
- cdef _KnownGraphNode right_parent
cdef list parents
cdef list children
cdef _KnownGraphNode linear_dominator_node
@@ -57,13 +53,10 @@
cdef object ancestor_of
def __init__(self, key, parents):
- cdef _KnownGraphNode _parent_node
cdef int i
self.key = key
- self.left_parent = None
- self.right_parent = None
- self.set_parents(parents)
+ self.parents = parents
self.children = []
# oldest ancestor, such that no parents between here and there have >1
@@ -93,26 +86,10 @@
else:
return self.linear_dominator_node.key
- cdef set_parents(self, list parents):
- cdef int num_parents
- self.parents = parents
- if parents is None:
- return
- num_parents = len(self.parents)
- if num_parents > 2:
- # No special ops
- return
- if num_parents > 0:
- self.left_parent = self.parents[0]
- if num_parents > 1:
- self.right_parent = self.parents[1]
-
cdef clear_references(self):
self.parents = None
self.children = None
self.linear_dominator_node = None
- self.left_parent = None
- self.right_parent = None
def __repr__(self):
parent_keys = []
@@ -186,7 +163,7 @@
if key in nodes:
node = nodes[key]
assert node.parents is None
- node.set_parents(parent_nodes)
+ node.parents = parent_nodes
else:
node = _KnownGraphNode(key, parent_nodes)
nodes[key] = node
@@ -273,8 +250,6 @@
tails = self._find_tails()
todo = []
- heappush = heapq.heappush
- heappop = heapq.heappop
for node in tails:
node.gdfo = 1
heappush(todo, (1, node))
@@ -324,6 +299,12 @@
cdef _KnownGraphNode node
cdef PyObject *maybe_node
+ heads_key = PyFrozenSet_New(keys)
+ try:
+ heads = self._known_heads[heads_key]
+ return heads
+ except KeyError:
+ pass # compute it ourselves
candidate_nodes = {}
nodes = self._nodes
for key in keys:
@@ -338,14 +319,10 @@
candidate_nodes.pop(revision.NULL_REVISION)
if not candidate_nodes:
return set([revision.NULL_REVISION])
- heads_key = PyFrozenSet_New(candidate_nodes)
+ # The keys changed, so recalculate heads_key
+ heads_key = PyFrozenSet_New(candidate_nodes)
if len(candidate_nodes) < 2:
return heads_key
- try:
- heads = self._known_heads[heads_key]
- return heads
- except KeyError:
- pass # compute it ourselves
# Check the linear dominators of these keys, to see if we already
# know the heads answer
dom_lookup_key, heads = self._heads_from_dominators(
@@ -452,8 +429,6 @@
# walking
# Now we walk nodes until all nodes that are being walked are 'common'
num_candidates = len(candidate_nodes)
- heappop = heapq.heappop
- heappush = heapq.heappush
while len(queue) > 0 and len(candidate_nodes) > 1:
_, node = heappop(queue)
if len(node.ancestor_of) == num_candidates:
@@ -472,9 +447,6 @@
continue
# Now project the current nodes ancestor list to the parent nodes,
# and queue them up to be walked
- # Note: using linear_dominator speeds things up quite a bit
- # enough that we actually start to be slightly faster
- # than the default heads() implementation
if node.linear_dominator_node is not node:
# We are at the tip of a long linear region
# We know that there is nothing between here and the tail
@@ -483,21 +455,10 @@
candidate_nodes, queue)):
break
else:
- num_parents = len(node.parents)
- if num_parents > 2:
- for parent_node in node.parents:
- if (self._process_parent(node, parent_node,
- candidate_nodes, queue)):
- break
- else:
- if num_parents > 0:
- if (self._process_parent(node, node.left_parent,
- candidate_nodes, queue)):
- break
- if num_parents > 1:
- if (self._process_parent(node, node.right_parent,
- candidate_nodes, queue)):
- break
+ for parent_node in node.parents:
+ if (self._process_parent(node, parent_node,
+ candidate_nodes, queue)):
+ break
for node in self._to_cleanup:
node.ancestor_of = None
self._to_cleanup = []
=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py 2009-06-10 19:56:16 +0000
+++ b/bzrlib/graph.py 2009-06-11 04:28:57 +0000
@@ -1657,7 +1657,6 @@
return result
-_counters = [0, 0, 0, 0, 0]
try:
from bzrlib._known_graph_pyx import KnownGraph
except ImportError:
More information about the bazaar-commits
mailing list