Rev 2262: Collapsing if _links grows to long has very good benefits for performance. in http://bzr.arbash-meinel.com/branches/bzr/0.15-dev/list_patch
John Arbash Meinel
john at arbash-meinel.com
Tue Jan 30 22:46:44 GMT 2007
At http://bzr.arbash-meinel.com/branches/bzr/0.15-dev/list_patch
------------------------------------------------------------
revno: 2262
revision-id: john at arbash-meinel.com-20070130224637-f3c7gx2ya50r1rej
parent: john at arbash-meinel.com-20070130210407-ny0eh3g3fpf2bwnm
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: list_patch
timestamp: Tue 2007-01-30 16:46:37 -0600
message:
Collapsing if _links grows to long has very good benefits for performance.
modified:
bzrlib/hybrid_linked_list.py hybrid_linked_list.p-20070130001028-zlexwz74tzo56o2t-1
-------------- next part --------------
=== modified file 'bzrlib/hybrid_linked_list.py'
--- a/bzrlib/hybrid_linked_list.py 2007-01-30 21:04:07 +0000
+++ b/bzrlib/hybrid_linked_list.py 2007-01-30 22:46:37 +0000
@@ -40,8 +40,32 @@
be stored with _ranges, but it makes it easier to update links if they
are in a separate dict. (less tuple churn)
:ivar _length: The current length of the output content
+ :cvar _max_links: When copying, flatten the text if we exceed _max_links
"""
+ # This was determined empirically on a knit with 55,000 lines of content,
+ # and 458 line-deltas. A number of 100 caused flatten to occur 28 times, at
+ # approximately 300ms each. Without any flattening max_links grows to 4000,
+ # and _find_nodes_for_pos starts to become a bottleneck.
+ # Under --lsprof, 1000 looks the best (it flattens 3 times). However real
+ # testing shows that 500 is better (it flattens 7 times). This is because
+ # --lsprof penalizes __iter__ more than it penalizes _find_nodes_for_pos
+
+ # TODO: jam 20070130 We could make this dynamic based on the length of the
+ # text versus the length of the delta chain.
+ # For example, in the current tradeoff, we have 55,000 lines, and we
+ # want to collapse if we have more than 500 links. This works out to
+ # be very close to 1/100 (if links grows larger that 1/100th of the
+ # total length, we want to collapse).
+ # However, I'm not convinced that _find_nodes_for_pos is going to
+ # scale based on relative amount, versus scaling based on actual
+ # number of nodes. But theoretically we are trading off flatten()
+ # calls for _find_nodes_for_pos performance.
+ #
+ # TODO: jam 20070130 This seems like a pretty good class to
+ # optimize as a C or pyrex extension.
+ _max_links = 500
+
__slots__ = ['_head', '_ranges', '_links', '_length']
def __init__(self, starting=[]):
@@ -71,11 +95,13 @@
"""Iterate over the final content."""
cur_range_id = self._head
+ _ranges = self._ranges
+ _links = self._links
while cur_range_id is not None:
- start, end, content = self._ranges[cur_range_id]
+ start, end, content = _ranges[cur_range_id]
for pos in xrange(start, end):
yield content[pos]
- cur_range_id = self._links[cur_range_id]
+ cur_range_id = _links[cur_range_id]
def __len__(self):
# Profiling shows __len__ to be adding a lot of overhead, so we use a
@@ -164,8 +190,9 @@
"""repr(HybridLinkedList) gives more information about internals."""
flattened = []
cur = self._head
+ _ranges = self._ranges
while cur is not None:
- flattened.append('%s:%s' % (cur, self._ranges[cur]))
+ flattened.append('%s:%s' % (cur, _ranges[cur]))
cur = self._links[cur]
return 'HybridLinkedList(' + ', '.join(flattened) + ')'
@@ -193,6 +220,11 @@
# 4716 3.9053 bzrlib.hybrid_linked_list:176(_find_nodes_for_pos)
# and switching to lists instead of dicts
# 4716 3.4728 bzrlib.hybrid_linked_list:176(_find_nodes_for_pos)
+ # flattening if we exceed 1000 links yields:
+ # 3 1.0809 bzrlib.hybrid_linked_list:179(flatten)
+ # 4719 1.4945 bzrlib.hybrid_linked_list:183(_find_nodes_for_pos)
+ # So while it takes 300+ms to flatten, we avoid bad O(N) behavior for
+ # number of links.
_ranges = self._ranges
_links = self._links
@@ -385,6 +417,12 @@
copies of the contents. However, since contents are never modified,
that should be fine.
"""
+ # If we get too many links, just collapse them.
+ # Without flattening on the mozilla tree, with 458 deltas, we end up
+ # with 4000 links. Which starts being a bottleneck in
+ # _find_nodes_for_pos
+ if len(self._links) > self._max_links:
+ self.flatten()
new_hll = HybridLinkedList()
new_hll._head = self._head
new_hll._ranges = self._ranges[:]
More information about the bazaar-commits
mailing list