Author: Maciej Fijalkowski <[email protected]>
Branch:
Changeset: r74899:ac553d5be503
Date: 2014-12-12 17:34 +0200
http://bitbucket.org/pypy/pypy/changeset/ac553d5be503/
Log: merge
diff --git a/rpython/annotator/bookkeeper.py b/rpython/annotator/bookkeeper.py
--- a/rpython/annotator/bookkeeper.py
+++ b/rpython/annotator/bookkeeper.py
@@ -19,7 +19,7 @@
from rpython.annotator import description
from rpython.annotator.signature import annotationoftype
from rpython.annotator.argument import simple_args
-from rpython.rlib.objectmodel import r_dict, Symbolic
+from rpython.rlib.objectmodel import r_dict, r_ordereddict, Symbolic
from rpython.tool.algo.unionfind import UnionFind
from rpython.rtyper import extregistry
@@ -260,21 +260,23 @@
result.listdef.generalize(self.immutablevalue(e))
result.const_box = key
return result
- elif tp is dict or tp is r_dict or tp is SomeOrderedDict.knowntype:
- if tp is SomeOrderedDict.knowntype:
- cls = SomeOrderedDict
- else:
- cls = SomeDict
+ elif (tp is dict or tp is r_dict or
+ tp is SomeOrderedDict.knowntype or tp is r_ordereddict):
key = Constant(x)
try:
return self.immutable_cache[key]
except KeyError:
+ if tp is SomeOrderedDict.knowntype or tp is r_ordereddict:
+ cls = SomeOrderedDict
+ else:
+ cls = SomeDict
+ is_r_dict = issubclass(tp, r_dict)
result = cls(DictDef(self,
s_ImpossibleValue,
s_ImpossibleValue,
- is_r_dict = tp is r_dict))
+ is_r_dict = is_r_dict))
self.immutable_cache[key] = result
- if tp is r_dict:
+ if is_r_dict:
s_eqfn = self.immutablevalue(x.key_eq)
s_hashfn = self.immutablevalue(x.key_hash)
result.dictdef.dictkey.update_rdict_annotations(s_eqfn,
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
@@ -217,7 +217,7 @@
#dictobj = getattr(dictobj, '__self__', dictobj)
if dictobj is None:
return lltype.nullptr(self.DICT)
- if not isinstance(dictobj, (dict, objectmodel.r_dict)):
+ if not isinstance(dictobj, (dict, objectmodel.r_ordereddict)):
raise TypeError("expected a dict: %r" % (dictobj,))
try:
key = Constant(dictobj)
@@ -231,7 +231,8 @@
if r_key.lowleveltype == llmemory.Address:
raise TypeError("No prebuilt dicts of address keys")
r_value = self.value_repr
- if isinstance(dictobj, objectmodel.r_dict):
+ if isinstance(dictobj, objectmodel.r_ordereddict):
+
if self.r_rdict_eqfn.lowleveltype != lltype.Void:
l_fn = self.r_rdict_eqfn.convert_const(dictobj.key_eq)
l_dict.fnkeyeq = l_fn
@@ -289,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
@@ -653,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
@@ -666,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)
@@ -981,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
@@ -994,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
diff --git a/rpython/rtyper/test/test_rdict.py
b/rpython/rtyper/test/test_rdict.py
--- a/rpython/rtyper/test/test_rdict.py
+++ b/rpython/rtyper/test/test_rdict.py
@@ -878,6 +878,81 @@
res = self.interpret(func, [])
assert lltype.typeOf(res.item0) == lltype.typeOf(res.item1)
+ def test_r_dict(self):
+ class FooError(Exception):
+ pass
+ def myeq(n, m):
+ return n == m
+ def myhash(n):
+ if n < 0:
+ raise FooError
+ return -n
+ def f(n):
+ d = self.new_r_dict(myeq, myhash)
+ for i in range(10):
+ d[i] = i*i
+ try:
+ value1 = d[n]
+ except FooError:
+ value1 = 99
+ try:
+ value2 = n in d
+ except FooError:
+ value2 = 99
+ try:
+ value3 = d[-n]
+ except FooError:
+ value3 = 99
+ try:
+ value4 = (-n) in d
+ except FooError:
+ value4 = 99
+ return (value1 * 1000000 +
+ value2 * 10000 +
+ value3 * 100 +
+ value4)
+ res = self.interpret(f, [5])
+ assert res == 25019999
+
+ def test_r_dict_popitem_hash(self):
+ def deq(n, m):
+ return n == m
+ def dhash(n):
+ return ~n
+ def func():
+ d = self.new_r_dict(deq, dhash)
+ d[5] = 2
+ d[6] = 3
+ k1, v1 = d.popitem()
+ assert len(d) == 1
+ k2, v2 = d.popitem()
+ try:
+ d.popitem()
+ except KeyError:
+ pass
+ else:
+ assert 0, "should have raised KeyError"
+ assert len(d) == 0
+ return k1*1000 + v1*100 + k2*10 + v2
+
+ res = self.interpret(func, [])
+ assert res in [5263, 6352]
+
+ def test_prebuilt_r_dict(self):
+ def deq(n, m):
+ return (n & 3) == (m & 3)
+ def dhash(n):
+ return n & 3
+ d = self.new_r_dict(deq, dhash)
+ d[0x123] = "abcd"
+ d[0x231] = "efgh"
+ def func():
+ return d[0x348973] + d[0x12981]
+
+ res = self.interpret(func, [])
+ res = self.ll_to_string(res)
+ assert res == "abcdefgh"
+
class TestRDict(BaseTestRDict):
@staticmethod
@@ -888,6 +963,10 @@
def newdict2():
return {}
+ @staticmethod
+ def new_r_dict(myeq, myhash):
+ return r_dict(myeq, myhash)
+
def test_two_dicts_with_different_value_types(self):
def func(i):
d1 = {}
@@ -1043,66 +1122,6 @@
assert lltype.typeOf(res.item1) == lltype.typeOf(res.item2)
assert lltype.typeOf(res.item1) == lltype.typeOf(res.item3)
- def test_r_dict(self):
- class FooError(Exception):
- pass
- def myeq(n, m):
- return n == m
- def myhash(n):
- if n < 0:
- raise FooError
- return -n
- def f(n):
- d = r_dict(myeq, myhash)
- for i in range(10):
- d[i] = i*i
- try:
- value1 = d[n]
- except FooError:
- value1 = 99
- try:
- value2 = n in d
- except FooError:
- value2 = 99
- try:
- value3 = d[-n]
- except FooError:
- value3 = 99
- try:
- value4 = (-n) in d
- except FooError:
- value4 = 99
- return (value1 * 1000000 +
- value2 * 10000 +
- value3 * 100 +
- value4)
- res = self.interpret(f, [5])
- assert res == 25019999
-
- def test_dict_popitem_hash(self):
- def deq(n, m):
- return n == m
- def dhash(n):
- return ~n
- def func():
- d = r_dict(deq, dhash)
- d[5] = 2
- d[6] = 3
- k1, v1 = d.popitem()
- assert len(d) == 1
- k2, v2 = d.popitem()
- try:
- d.popitem()
- except KeyError:
- pass
- else:
- assert 0, "should have raised KeyError"
- assert len(d) == 0
- return k1*1000 + v1*100 + k2*10 + v2
-
- res = self.interpret(func, [])
- assert res in [5263, 6352]
-
def test_nonnull_hint(self):
def eq(a, b):
return a == b
diff --git a/rpython/rtyper/test/test_rordereddict.py
b/rpython/rtyper/test/test_rordereddict.py
--- a/rpython/rtyper/test/test_rordereddict.py
+++ b/rpython/rtyper/test/test_rordereddict.py
@@ -268,6 +268,10 @@
def newdict2():
return OrderedDict()
+ @staticmethod
+ def new_r_dict(myeq, myhash):
+ return objectmodel.r_ordereddict(myeq, myhash)
+
def test_two_dicts_with_different_value_types(self):
def func(i):
d1 = OrderedDict()
@@ -283,64 +287,3 @@
def test_memoryerror_should_not_insert(self):
py.test.skip("I don't want to edit this file on two branches")
-
-
- def test_r_dict(self):
- class FooError(Exception):
- pass
- def myeq(n, m):
- return n == m
- def myhash(n):
- if n < 0:
- raise FooError
- return -n
- def f(n):
- d = objectmodel.r_ordereddict(myeq, myhash)
- for i in range(10):
- d[i] = i*i
- try:
- value1 = d[n]
- except FooError:
- value1 = 99
- try:
- value2 = n in d
- except FooError:
- value2 = 99
- try:
- value3 = d[-n]
- except FooError:
- value3 = 99
- try:
- value4 = (-n) in d
- except FooError:
- value4 = 99
- return (value1 * 1000000 +
- value2 * 10000 +
- value3 * 100 +
- value4)
- res = self.interpret(f, [5])
- assert res == 25019999
-
- def test_dict_popitem_hash(self):
- def deq(n, m):
- return n == m
- def dhash(n):
- return ~n
- def func():
- d = objectmodel.r_ordereddict(deq, dhash)
- d[5] = 2
- d[6] = 3
- k1, v1 = d.popitem()
- assert len(d) == 1
- k2, v2 = d.popitem()
- try:
- d.popitem()
- except KeyError:
- pass
- else:
- assert 0, "should have raised KeyError"
- assert len(d) == 0
- return k1*1000 + v1*100 + k2*10 + v2
-
- res = self.interpret(func, [])
- assert res in [5263, 6352]
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
