Author: Jasper.Schulz <jasper.b.sch...@gmail.com>
Branch: reorder-map-attributes
Changeset: r82146:a9ed2fa16365
Date: 2016-02-10 15:28 +0000
http://bitbucket.org/pypy/pypy/changeset/a9ed2fa16365/
Log: (cfbolz, jbs): Make sure that we end up with the same map if
attributes are inserted in different orders
diff --git a/pypy/objspace/std/mapdict.py b/pypy/objspace/std/mapdict.py
--- a/pypy/objspace/std/mapdict.py
+++ b/pypy/objspace/std/mapdict.py
@@ -20,6 +20,8 @@
# note: we use "x * NUM_DIGITS_POW2" instead of "x << NUM_DIGITS" because
# we want to propagate knowledge that the result cannot be negative
+NOT_REORDERED, JUST_REORDERED, SOMEWHERE_REORDERED = range(3)
+
class AbstractAttribute(object):
_immutable_fields_ = ['terminator']
cache_attrs = None
@@ -156,7 +158,12 @@
jit.isconstant(name) and
jit.isconstant(index))
def add_attr(self, obj, name, index, w_value):
- # grumble, jit needs this
+ reordered = self._try_reorder_and_add(obj, name, index, w_value)
+ if reordered != NOT_REORDERED:
+ return
+ self._add_attr_without_reordering(obj, name, index, w_value)
+
+ def _add_attr_without_reordering(self, obj, name, index, w_value):
attr = self._get_new_attr(name, index)
oldattr = obj._get_mapdict_map()
if not jit.we_are_jitted():
@@ -176,6 +183,39 @@
obj._set_mapdict_map(attr)
obj._mapdict_write_storage(attr.storageindex, w_value)
+ def _try_reorder_and_add(self, obj, name, index, w_value):
+ key = name, index
+ if self.cache_attrs is not None and key in self.cache_attrs:
+ attr = self.cache_attrs[key]
+ # xxx: remove duplicated code
+
+ if attr.length() > obj._mapdict_storage_length():
+ # note that attr.size_estimate() is always at least
attr.length()
+ new_storage = [None] * attr.size_estimate()
+ for i in range(obj._mapdict_storage_length()):
+ new_storage[i] = obj._mapdict_read_storage(i)
+ obj._set_mapdict_storage_and_map(new_storage, attr)
+
+ obj._set_mapdict_map(attr)
+ obj._mapdict_write_storage(attr.storageindex, w_value)
+ return JUST_REORDERED
+
+ elif isinstance(self, PlainAttribute):
+ w_self_value = obj._mapdict_read_storage(self.storageindex)
+ reordered = self.back._try_reorder_and_add(obj, name, index,
w_value)
+ if reordered == JUST_REORDERED:
+ obj._get_mapdict_map()._add_attr_without_reordering(
+ obj, self.name, self.index, w_self_value)
+ elif reordered == SOMEWHERE_REORDERED:
+ obj._get_mapdict_map().add_attr(obj, self.name, self.index,
w_self_value)
+ else:
+ assert reordered == NOT_REORDERED
+ return NOT_REORDERED
+ return SOMEWHERE_REORDERED
+ else:
+ # we are terminator
+ return NOT_REORDERED
+
def materialize_r_dict(self, space, obj, dict_w):
raise NotImplementedError("abstract base class")
diff --git a/pypy/objspace/std/test/test_mapdict.py
b/pypy/objspace/std/test/test_mapdict.py
--- a/pypy/objspace/std/test/test_mapdict.py
+++ b/pypy/objspace/std/test/test_mapdict.py
@@ -107,6 +107,87 @@
assert obj2.getdictvalue(space, "b") == 60
assert obj2.map is obj.map
+def test_insert_different_orders():
+ cls = Class()
+ obj = cls.instantiate()
+ obj.setdictvalue(space, "a", 10)
+ obj.setdictvalue(space, "b", 20)
+
+ obj2 = cls.instantiate()
+ obj2.setdictvalue(space, "b", 30)
+ obj2.setdictvalue(space, "a", 40)
+
+ assert obj.map is obj2.map
+
+def test_insert_different_orders_2():
+ cls = Class()
+ obj = cls.instantiate()
+ obj2 = cls.instantiate()
+
+ obj.setdictvalue(space, "a", 10)
+
+ obj2.setdictvalue(space, "b", 20)
+ obj2.setdictvalue(space, "a", 30)
+
+ obj.setdictvalue(space, "b", 40)
+ assert obj.map is obj2.map
+
+def test_insert_different_orders_3():
+ cls = Class()
+ obj = cls.instantiate()
+ obj2 = cls.instantiate()
+ obj3 = cls.instantiate()
+ obj4 = cls.instantiate()
+ obj5 = cls.instantiate()
+ obj6 = cls.instantiate()
+
+ obj.setdictvalue(space, "a", 10)
+ obj.setdictvalue(space, "b", 20)
+ obj.setdictvalue(space, "c", 30)
+
+ obj2.setdictvalue(space, "a", 30)
+ obj2.setdictvalue(space, "c", 40)
+ obj2.setdictvalue(space, "b", 50)
+
+ obj3.setdictvalue(space, "c", 30)
+ obj3.setdictvalue(space, "a", 40)
+ obj3.setdictvalue(space, "b", 50)
+
+ obj4.setdictvalue(space, "c", 30)
+ obj4.setdictvalue(space, "b", 40)
+ obj4.setdictvalue(space, "a", 50)
+
+ obj5.setdictvalue(space, "b", 30)
+ obj5.setdictvalue(space, "a", 40)
+ obj5.setdictvalue(space, "c", 50)
+
+ obj6.setdictvalue(space, "b", 30)
+ obj6.setdictvalue(space, "c", 40)
+ obj6.setdictvalue(space, "a", 50)
+
+ assert obj.map is obj2.map
+ assert obj.map is obj3.map
+ assert obj.map is obj4.map
+ assert obj.map is obj5.map
+ assert obj.map is obj6.map
+
+
+def test_insert_different_orders_perm():
+ from itertools import permutations
+ cls = Class()
+ seen_maps = {}
+ for i, attributes in enumerate(permutations("abcdef")):
+ obj = cls.instantiate()
+ key = ""
+ for j, attr in enumerate(attributes):
+ obj.setdictvalue(space, attr, i*10+j)
+ key = "".join(sorted(key+attr))
+ if key in seen_maps:
+ assert obj.map is seen_maps[key]
+ else:
+ seen_maps[key] = obj.map
+ print len(seen_maps)
+
def test_attr_immutability(monkeypatch):
cls = Class()
obj = cls.instantiate()
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit
