Author: Laurence Tratt <[email protected]>
Branch:
Changeset: r74946:16ce1a0def4d
Date: 2014-12-15 17:03 +0000
http://bitbucket.org/pypy/pypy/changeset/16ce1a0def4d/
Log: Reuse deleted items at the end of an orderedarray.
If a user deletes item(s) at the end of an orderedarray, they can be
immediately reused rather than marked as dead and compacted later.
diff --git a/rpython/rtyper/lltypesystem/rordereddict.py
b/rpython/rtyper/lltypesystem/rordereddict.py
--- a/rpython/rtyper/lltypesystem/rordereddict.py
+++ b/rpython/rtyper/lltypesystem/rordereddict.py
@@ -662,6 +662,19 @@
if ENTRIES.must_clear_value:
entry.value = lltype.nullptr(ENTRY.value.TO)
+ if index == d.num_ever_used_items - 1:
+ # The last element of the ordereddict has been deleted. Instead of
+ # simply marking the item as dead, we can safely reuse it. Since it's
+ # also possible that there are more dead items immediately behind the
+ # last one, we reclaim all the dead items at the end of the ordereditem
+ # at the same point.
+ i = d.num_ever_used_items - 2
+ while i >= 0 and not d.entries.valid(i):
+ i -= 1
+ j = i + 1
+ assert j >= 0
+ d.num_ever_used_items = j
+
# If the dictionary is at least 87.5% dead items, then consider shrinking
# it.
if d.num_live_items + DICT_INITSIZE <= len(d.entries) / 8:
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
