Rev 4432: Spend some time optimizing the inner heads() loop, approx 2x faster. in http://bazaar.launchpad.net/~jameinel/bzr/jam-gdfo-heads
John Arbash Meinel
john at arbash-meinel.com
Fri Jun 19 19:30:26 BST 2009
At http://bazaar.launchpad.net/~jameinel/bzr/jam-gdfo-heads
------------------------------------------------------------
revno: 4432
revision-id: john at arbash-meinel.com-20090619183001-xy6dp466kh3cwd1j
parent: john at arbash-meinel.com-20090619175337-uozt3bntdd48lh4z
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: jam-gdfo-heads
timestamp: Fri 2009-06-19 13:30:01 -0500
message:
Spend some time optimizing the inner heads() loop, approx 2x faster.
Various tweaks and their effect:
# Baseline
Found 25382 nodes, loaded in 2.194s
7581 combinations
Known: 1.626s
Known (pyx): 0.993s
ratio: 1.6:1 faster
# Tweaks for NULL_REVISION and PyDict_Size, min_gdfo as long
Known (pyx): 0.945s
ratio: 1.7:1 faster
# PySet_Contains, PySet_Add
Known (pyx): 0.846s
ratio: 1.9:1 faster
# Avoid pop & push
Known (pyx): 0.564s
ratio: 2.9:1 faster
# pending_pop
Known (pyx): 0.542s
ratio: 3.1:1 faster
-------------- next part --------------
=== modified file 'bzrlib/_known_graph_pyx.pyx'
--- a/bzrlib/_known_graph_pyx.pyx 2009-06-19 17:37:01 +0000
+++ b/bzrlib/_known_graph_pyx.pyx 2009-06-19 18:30:01 +0000
@@ -40,12 +40,18 @@
Py_ssize_t PyList_GET_SIZE(object l)
int PyList_SetItem(object l, Py_ssize_t o, object l) except -1
int PyDict_SetItem(object d, object k, object v) except -1
+
+ int PySet_Contains(object s, object k) except -1
int PySet_Add(object s, object k) except -1
void Py_INCREF(object)
from bzrlib import revision
+cdef object NULL_REVISION
+NULL_REVISION = revision.NULL_REVISION
+
+
cdef class _KnownGraphNode:
"""Represents a single object in the known graph."""
@@ -108,14 +114,6 @@
return <_KnownGraphNode>temp_node
-cdef _KnownGraphNode _peek_node(queue):
- cdef PyObject *temp_node
- cdef _KnownGraphNode node
-
- temp_node = PyTuple_GET_ITEM(<object>PyList_GET_ITEM(queue, 0), 1)
- node = <_KnownGraphNode>temp_node
- return node
-
# TODO: slab allocate all _KnownGraphNode objects.
# We already know how many we are going to need, except for a couple of
# ghosts that could be allocated on demand.
@@ -247,7 +245,7 @@
known_gdfo = known_gdfo + 1
if child.gdfo is None or node.gdfo + 1 > child.gdfo:
child.gdfo = node.gdfo + 1
- if known_gdfo == PyList_GET_SIZE(child.parents):
+ if known_gdfo == PyTuple_GET_SIZE(child.parents):
# This child is populated, queue it to be walked
if replace:
replace = 0
@@ -287,6 +285,8 @@
cdef PyObject *maybe_heads
cdef PyObject *temp_node
cdef _KnownGraphNode node
+ cdef Py_ssize_t pos
+ cdef long min_gdfo
heads_key = PyFrozenSet_New(keys)
maybe_heads = PyDict_GetItem(self._known_heads, heads_key)
@@ -300,39 +300,55 @@
if maybe_node == NULL:
raise KeyError('key %s not in nodes' % (key,))
PyDict_SetItem(candidate_nodes, key, <object>maybe_node)
- if revision.NULL_REVISION in candidate_nodes:
+ maybe_node = PyDict_GetItem(candidate_nodes, NULL_REVISION)
+ if maybe_node != NULL:
# NULL_REVISION is only a head if it is the only entry
- candidate_nodes.pop(revision.NULL_REVISION)
+ candidate_nodes.pop(NULL_REVISION)
if not candidate_nodes:
- return set([revision.NULL_REVISION])
+ return frozenset([NULL_REVISION])
# The keys changed, so recalculate heads_key
heads_key = PyFrozenSet_New(candidate_nodes)
- if len(candidate_nodes) < 2:
+ if PyDict_Size(candidate_nodes) < 2:
return heads_key
seen = set()
pending = []
- cdef Py_ssize_t pos
+ pending_pop = pending.pop
+ # we know a gdfo cannot be longer than a linear chain of all nodes
+ min_gdfo = PyDict_Size(self._nodes) + 1
+ # Build up nodes that need to be walked, note that starting nodes are
+ # not added to seen()
pos = 0
- min_gdfo = None
while PyDict_Next(candidate_nodes, &pos, NULL, &temp_node):
node = <_KnownGraphNode>temp_node
if node.parents is not None:
pending.extend(node.parents)
- if min_gdfo is None or node.gdfo < min_gdfo:
+ if node.gdfo < min_gdfo:
min_gdfo = node.gdfo
- nodes = self._nodes
- while pending:
- node = pending.pop()
- if node.key in seen:
+
+ # Now do all the real work
+ while PyList_GET_SIZE(pending) > 0:
+ node = _get_list_node(pending, PyList_GET_SIZE(pending) - 1)
+ if PySet_Contains(seen, node.key):
# node already appears in some ancestry
+ pending_pop()
continue
- seen.add(node.key)
+ PySet_Add(seen, node.key)
if node.gdfo <= min_gdfo:
+ pending_pop()
continue
- if node.parents:
- pending.extend(node.parents)
+ if node.parents is not None and PyTuple_GET_SIZE(node.parents) > 0:
+ for pos from 0 <= pos < PyTuple_GET_SIZE(node.parents):
+ parent_node = _get_parent(node.parents, pos)
+ if pos == 0:
+ Py_INCREF(parent_node)
+ PyList_SetItem(pending, PyList_GET_SIZE(pending) - 1,
+ parent_node)
+ else:
+ PyList_Append(pending, parent_node)
+ else:
+ pending_pop()
heads = heads_key.difference(seen)
if self.do_cache:
- self._known_heads[heads_key] = heads
+ PyDict_SetItem(self._known_heads, heads_key, heads)
return heads
More information about the bazaar-commits
mailing list