Author: Armin Rigo <[email protected]>
Branch:
Changeset: r74897:2b51137c528f
Date: 2014-12-12 14:48 +0000
http://bitbucket.org/pypy/pypy/changeset/2b51137c528f/
Log: (cfbolz, arigo)
Copy support for prepare_dict_update() from rdict to rordereddict.
diff --git a/rpython/rlib/test/test_objectmodel.py
b/rpython/rlib/test/test_objectmodel.py
--- a/rpython/rlib/test/test_objectmodel.py
+++ b/rpython/rlib/test/test_objectmodel.py
@@ -329,6 +329,18 @@
res = self.interpret(g, [3])
assert res == 42 # "did not crash"
+ def test_prepare_dict_update_2(self):
+ try:
+ from collections import OrderedDict
+ except ImportError: # Python 2.6
+ py.test.skip("requires collections.OrderedDict")
+ def g(n):
+ d = OrderedDict()
+ prepare_dict_update(d, n)
+ return 42
+ res = self.interpret(g, [3])
+ assert res == 42 # "did not crash"
+
def test_compute_hash(self):
class Foo(object):
pass
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
@@ -290,6 +290,11 @@
hop.exception_cannot_occur()
return hop.gendirectcall(ll_dict_update, v_dic1, v_dic2)
+ def rtype_method__prepare_dict_update(self, hop):
+ v_dict, v_num = hop.inputargs(self, lltype.Signed)
+ hop.exception_cannot_occur()
+ hop.gendirectcall(ll_prepare_dict_update, v_dict, v_num)
+
def _rtype_method_kvi(self, hop, ll_func):
v_dic, = hop.inputargs(self)
r_list = hop.r_result
@@ -654,11 +659,14 @@
# make a 'new_size' estimate and shrink it if there are many
# deleted entry markers. See CPython for why it is a good idea to
# quadruple the dictionary size as long as it's not too big.
- num_items = d.num_items
- if num_items > 50000:
- new_estimate = num_items * 2
- else:
- new_estimate = num_items * 4
+ # (Quadrupling comes from '(d.num_items + d.num_items + 1) * 2'
+ # as long as num_items is not too large.)
+ num_extra = min(d.num_items + 1, 30000)
+ _ll_dict_resize_to(d, num_extra)
+ll_dict_resize.oopspec = 'odict.resize(d)'
+
+def _ll_dict_resize_to(d, num_extra):
+ new_estimate = (d.num_items + num_extra) * 2
new_size = DICT_INITSIZE
while new_size <= new_estimate:
new_size *= 2
@@ -667,7 +675,6 @@
ll_dict_remove_deleted_items(d)
else:
ll_dict_reindex(d, new_size)
-ll_dict_resize.oopspec = 'odict.resize(d)'
def ll_dict_reindex(d, new_size):
ll_malloc_indexes_and_choose_lookup(d, new_size)
@@ -982,6 +989,9 @@
ll_dict_clear.oopspec = 'odict.clear(d)'
def ll_dict_update(dic1, dic2):
+ if dic1 == dic2:
+ return
+ ll_prepare_dict_update(dic1, dic2.num_items)
i = 0
while i < dic2.num_used_items:
entries = dic2.entries
@@ -995,6 +1005,16 @@
i += 1
ll_dict_update.oopspec = 'odict.update(dic1, dic2)'
+def ll_prepare_dict_update(d, num_extra):
+ # Prescale 'd' for 'num_extra' items, assuming that most items don't
+ # collide. If this assumption is false, 'd' becomes too large by at
+ # most 'num_extra'. The logic is based on:
+ # (d.resize_counter - 1) // 3 = room left in d
+ # so, if num_extra == 1, we need d.resize_counter > 3
+ # if num_extra == 2, we need d.resize_counter > 6 etc.
+ jit.conditional_call(d.resize_counter <= num_extra * 3,
+ _ll_dict_resize_to, d, num_extra)
+
# this is an implementation of keys(), values() and items()
# in a single function.
# note that by specialization on func, three different
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
