Rev 2260: Some optimizations after seeing _find_nodes_for_pos is a hot-spot. in http://bzr.arbash-meinel.com/branches/bzr/0.15-dev/list_patch
John Arbash Meinel
john at arbash-meinel.com
Tue Jan 30 20:34:16 GMT 2007
At http://bzr.arbash-meinel.com/branches/bzr/0.15-dev/list_patch
------------------------------------------------------------
revno: 2260
revision-id: john at arbash-meinel.com-20070130203411-hv76deu87n5hu3bb
parent: john at arbash-meinel.com-20070130201946-5jsmey4eftrb4s6a
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: list_patch
timestamp: Tue 2007-01-30 14:34:11 -0600
message:
Some optimizations after seeing _find_nodes_for_pos is a hot-spot.
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 20:19:46 +0000
+++ b/bzrlib/hybrid_linked_list.py 2007-01-30 20:34:11 +0000
@@ -187,13 +187,20 @@
cur_pos = 0
content = start = end = None
+ # collapsing to local variables decreased the lsprof time from:
+ # 4716 4.8879 bzrlib.hybrid_linked_list:182(_find_nodes_for_pos)
+ # to
+ # 4716 3.9053 bzrlib.hybrid_linked_list:176(_find_nodes_for_pos)
+ _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]
next_pos = cur_pos + (end - start)
if pos < next_pos:
break
prev_range_id = cur_range_id
- cur_range_id = self._links[cur_range_id]
+ cur_range_id = _links[cur_range_id]
cur_pos = next_pos
content = start = end = None
return (prev_range_id, cur_range_id, pos - cur_pos,
@@ -213,25 +220,27 @@
(prev_range_id, cur_range_id, offset,
start, end, cur_content) = self._find_nodes_for_pos(start)
+ _links = self._links
+
if offset == 0:
# We are inserting before an existing node, or at the exact end of
# the list
if prev_range_id is None:
# We are at _head, update its reference
- self._links[new_range_id] = self._head
+ _links[new_range_id] = self._head
self._head = new_range_id
else:
- self._links[new_range_id] = cur_range_id
- self._links[prev_range_id] = new_range_id
+ _links[new_range_id] = cur_range_id
+ _links[prev_range_id] = new_range_id
# We are inserting inside an existing node
elif cur_range_id is not None:
# We need to break up the current node, and insert the
# requested one
break_point = start + offset
split_range_id = self._new_range_id(break_point, end, cur_content)
- next_range_id = self._links[cur_range_id]
- self._links[split_range_id] = next_range_id
- self._links[new_range_id] = split_range_id
+ next_range_id = _links[cur_range_id]
+ _links[split_range_id] = next_range_id
+ _links[new_range_id] = split_range_id
# We could make this atomic by creating a new id for the
# initial range, and then the atomic step is
@@ -239,7 +248,7 @@
# And then afterwards we would want to delete the cur_range_id
# entry in the map
self._ranges[cur_range_id] = (start, break_point, cur_content)
- self._links[cur_range_id] = new_range_id
+ _links[cur_range_id] = new_range_id
else:
# We are appending a node
# python lists have the property that x[BIG_NUM:BIGNUM] = [10]
@@ -247,8 +256,8 @@
# range
# TODO: For now, I'm duplicating that, but it seems to make
# more sense to raise IndexError or something
- self._links[new_range_id] = None
- self._links[prev_range_id] = new_range_id
+ _links[new_range_id] = None
+ _links[prev_range_id] = new_range_id
self._length += content_len
def delete(self, start, end):
@@ -273,6 +282,9 @@
# In python "del list[BIGNUM:BIGNUM]" does nothing
return
+ _links = self._links
+ _ranges = self._ranges
+
while cur_range_id is not None:
# There are 4 possible cases
# 1) We remove this node entirely
@@ -292,22 +304,21 @@
possible_remove_length = entry_length - offset
if remove_length >= possible_remove_length:
- next_range_id = self._links[cur_range_id]
+ next_range_id = _links[cur_range_id]
if offset == 0:
# CASE 1: this node will be fully removed
if prev_range_id is None:
# Update _head
self._head = next_range_id
else:
- self._links[prev_range_id] = next_range_id
- del self._links[cur_range_id]
- del self._ranges[cur_range_id]
+ _links[prev_range_id] = next_range_id
+ del _links[cur_range_id]
+ del _ranges[cur_range_id]
else:
# CASE 2: we save the beginning, but remove the tail
# This only requires a node entry update
- self._ranges[cur_range_id] = (cur_start,
- cur_start + offset,
- content)
+ _ranges[cur_range_id] = (cur_start, cur_start + offset,
+ content)
prev_range_id = cur_range_id
remove_length -= possible_remove_length
self._length -= possible_remove_length
@@ -316,13 +327,13 @@
# step to next
offset = 0
cur_range_id = next_range_id
- cur_start, cur_end, content = self._ranges[next_range_id]
+ cur_start, cur_end, content = _ranges[next_range_id]
else:
if offset == 0:
# CASE 3: We remove only the beginning of this node
# Only requires a node entry update
- self._ranges[cur_range_id] = (cur_start + remove_length,
- cur_end, content)
+ _ranges[cur_range_id] = (cur_start + remove_length, cur_end,
+ content)
else:
# We have a beginning and a tail, we need to create a new
# record, and update the current one
@@ -334,12 +345,11 @@
new_tail_range_id = self._new_range_id(new_start, cur_end,
content)
- next_range_id = self._links[cur_range_id]
- self._links[new_tail_range_id] = next_range_id
+ next_range_id = _links[cur_range_id]
+ _links[new_tail_range_id] = next_range_id
- self._links[cur_range_id] = new_tail_range_id
- self._ranges[cur_range_id] = (cur_start, new_end,
- content)
+ _links[cur_range_id] = new_tail_range_id
+ _ranges[cur_range_id] = (cur_start, new_end, content)
# We officially removed enough, so we are done
self._length -= remove_length
break
More information about the bazaar-commits
mailing list