Commits

Carl Friedrich Bolz committed 184f4bd

a version of cell dicts that gives free global lookups for globals that don't
change using quasi-immutable fields. The strategy is very similar to that of
version tags on types, but it seemed hard to share code.

Comments (0)

Files changed (4)

pypy/objspace/std/celldict.py

-""" A very simple cell dict implementation. The dictionary maps keys to cell.
-This ensures that the function (dict, key) -> cell is pure. By itself, this
-optimization is not helping at all, but in conjunction with the JIT it can
-speed up global lookups a lot."""
+""" A very simple cell dict implementation using a version tag. The dictionary
+maps keys to objects. If a specific key is changed a lot, a level of
+indirection is introduced to make the version tag change less often.
+"""
 
+from pypy.interpreter.baseobjspace import W_Root
 from pypy.objspace.std.dictmultiobject import IteratorImplementation
 from pypy.objspace.std.dictmultiobject import DictStrategy, _never_equal_to_string
 from pypy.objspace.std.dictmultiobject import ObjectDictStrategy
 from pypy.rlib import jit, rerased
 
-class ModuleCell(object):
+class VersionTag(object):
+    pass
+
+class ModuleCell(W_Root):
     def __init__(self, w_value=None):
         self.w_value = w_value
 
-    def invalidate(self):
-        w_value = self.w_value
-        self.w_value = None
-        return w_value
-
     def __repr__(self):
         return "<ModuleCell: %s>" % (self.w_value, )
 
+def unwrap_cell(w_value):
+    if isinstance(w_value, ModuleCell):
+        return w_value.w_value
+    return w_value
+
 class ModuleDictStrategy(DictStrategy):
 
     erase, unerase = rerased.new_erasing_pair("modulecell")
     erase = staticmethod(erase)
     unerase = staticmethod(unerase)
 
+    _immutable_fields_ = ["version?"]
+
     def __init__(self, space):
         self.space = space
+        self.version = VersionTag()
 
     def get_empty_storage(self):
        return self.erase({})
 
-    def getcell(self, w_dict, key, makenew):
-        if makenew or jit.we_are_jitted():
-            # when we are jitting, we always go through the pure function
-            # below, to ensure that we have no residual dict lookup
-            self = jit.hint(self, promote=True)
-            return self._getcell_makenew(w_dict, key)
+    def mutated(self):
+       self.version = VersionTag()
+
+    def getdictvalue_no_unwrapping(self, w_dict, key):
+        return self._getdictvalue_no_unwrapping_pure(self.version, w_dict, key)
+
+    @jit.purefunction_promote('0,1,2')
+    def _getdictvalue_no_unwrapping_pure(self, version, w_dict, key):
         return self.unerase(w_dict.dstorage).get(key, None)
 
-    @jit.purefunction
-    def _getcell_makenew(self, w_dict, key):
-        return self.unerase(w_dict.dstorage).setdefault(key, ModuleCell())
-
     def setitem(self, w_dict, w_key, w_value):
         space = self.space
         if space.is_w(space.type(w_key), space.w_str):
             w_dict.setitem(w_key, w_value)
 
     def setitem_str(self, w_dict, key, w_value):
-        self.getcell(w_dict, key, True).w_value = w_value
+        cell = self.getdictvalue_no_unwrapping(w_dict, key)
+        if isinstance(cell, ModuleCell):
+            cell.w_value = w_value
+            return
+        if cell is not None:
+            w_value = ModuleCell(w_value)
+        self.mutated()
+        self.unerase(w_dict.dstorage)[key] = w_value
 
     def setdefault(self, w_dict, w_key, w_default):
         space = self.space
         if space.is_w(space.type(w_key), space.w_str):
-            cell = self.getcell(w_dict, space.str_w(w_key), True)
-            if cell.w_value is None:
-                cell.w_value = w_default
-            return cell.w_value
+            key = space.str_w(w_key)
+            w_result = self.getitem_str(w_dict, key)
+            if w_result is not None:
+                return w_result
+            self.setitem_str(w_dict, key, w_default)
+            return w_default
         else:
             self.switch_to_object_strategy(w_dict)
             return w_dict.setdefault(w_key, w_default)
         w_key_type = space.type(w_key)
         if space.is_w(w_key_type, space.w_str):
             key = space.str_w(w_key)
-            cell = self.getcell(w_dict, key, False)
-            if cell is None or cell.w_value is None:
-                raise KeyError
-            # note that we don't remove the cell from self.content, to make
-            # sure that a key that was found at any point in the dict, still
-            # maps to the same cell later (even if this cell no longer
-            # represents a key)
-            cell.invalidate()
+            dict_w = self.unerase(w_dict.dstorage)
+            try:
+                del dict_w[key]
+            except KeyError:
+                raise
+            else:
+                self.mutated()
         elif _never_equal_to_string(space, w_key_type):
             raise KeyError
         else:
             w_dict.delitem(w_key)
 
     def length(self, w_dict):
-        # inefficient, but do we care?
-        res = 0
-        for cell in self.unerase(w_dict.dstorage).itervalues():
-            if cell.w_value is not None:
-                res += 1
-        return res
+        return len(self.unerase(w_dict.dstorage))
 
     def getitem(self, w_dict, w_key):
         space = self.space
             return w_dict.getitem(w_key)
 
     def getitem_str(self, w_dict, key):
-        res = self.getcell(w_dict, key, False)
-        if res is None:
-            return None
-        # note that even if the res.w_value is None, the next line is fine
-        return res.w_value
+        w_res = self.getdictvalue_no_unwrapping(w_dict, key)
+        return unwrap_cell(w_res)
 
     def iter(self, w_dict):
         return ModuleDictIteratorImplementation(self.space, self, w_dict)
     def keys(self, w_dict):
         space = self.space
         iterator = self.unerase(w_dict.dstorage).iteritems
-        return [space.wrap(key) for key, cell in iterator()
-                    if cell.w_value is not None]
+        return [space.wrap(key) for key, cell in iterator()]
 
     def values(self, w_dict):
         iterator = self.unerase(w_dict.dstorage).itervalues
-        return [cell.w_value for cell in iterator()
-                    if cell.w_value is not None]
+        return [unwrap_cell(cell) for cell in iterator()]
 
     def items(self, w_dict):
         space = self.space
         iterator = self.unerase(w_dict.dstorage).iteritems
-        return [space.newtuple([space.wrap(key), cell.w_value])
-                    for (key, cell) in iterator()
-                        if cell.w_value is not None]
+        return [space.newtuple([space.wrap(key), unwrap_cell(cell)])
+                    for key, cell in iterator()]
 
     def clear(self, w_dict):
-        iterator = self.unerase(w_dict.dstorage).iteritems
-        for k, cell in iterator():
-            cell.invalidate()
+        iterator = self.unerase(w_dict.dstorage).clear()
+        self.mutated()
 
     def switch_to_object_strategy(self, w_dict):
         d = self.unerase(w_dict.dstorage)
         strategy = self.space.fromcache(ObjectDictStrategy)
         d_new = strategy.unerase(strategy.get_empty_storage())
         for key, cell in d.iteritems():
-            d_new[self.space.wrap(key)] = cell.w_value
+            d_new[self.space.wrap(key)] = unwrap_cell(cell)
         w_dict.strategy = strategy
         w_dict.dstorage = strategy.erase(d_new)
 
-    def _as_rdict(self):
-        r_dict_content = self.initialize_as_rdict()
-        for k, cell in self.content.iteritems():
-            if cell.w_value is not None:
-                r_dict_content[self.space.wrap(k)] = cell.w_value
-            cell.invalidate()
-        self._clear_fields()
-        return self
-
     def _clear_fields(self):
         self.content = None
 
 
     def next_entry(self):
         for key, cell in self.iterator:
-            if cell.w_value is not None:
-                return (self.space.wrap(key), cell.w_value)
+            return (self.space.wrap(key), unwrap_cell(cell))
         else:
             return None, None

pypy/objspace/std/dictmultiobject.py

         if space.config.objspace.std.withcelldict and module:
             from pypy.objspace.std.celldict import ModuleDictStrategy
             assert w_type is None
-            strategy = space.fromcache(ModuleDictStrategy)
+            # every module needs its own strategy, because the strategy stores
+            # the version tag
+            strategy = ModuleDictStrategy(space)
 
         elif instance or strdict or module:
             assert w_type is None

pypy/objspace/std/test/test_celldict.py

 from pypy.conftest import gettestobjspace, option
 from pypy.objspace.std.dictmultiobject import W_DictMultiObject
 from pypy.objspace.std.celldict import ModuleCell, ModuleDictStrategy
-from pypy.objspace.std.test.test_dictmultiobject import FakeSpace
+from pypy.objspace.std.test.test_dictmultiobject import FakeSpace. \
+        BaseTestRDictImplementation, BaseTestDevolvedDictImplementation
 from pypy.interpreter import gateway
 
+from pypy.conftest import gettestobjspace
+
 space = FakeSpace()
 
 class TestCellDict(object):
-    def test_basic_property(self):
+    def test_basic_property_cells(self):
         strategy = ModuleDictStrategy(space)
         storage = strategy.get_empty_storage()
         d = W_DictMultiObject(space, strategy, storage)
 
-        # replace getcell with getcell from strategy
-        def f(key, makenew):
-            return strategy.getcell(d, key, makenew)
-        d.getcell = f
+        v1 = strategy.version
+        d.setitem("a", 1)
+        v2 = strategy.version
+        assert v1 is not v2
+        assert d.getitem("a") == 1
 
-        d.setitem("a", 1)
-        assert d.getcell("a", False) is d.getcell("a", False)
-        acell = d.getcell("a", False)
-        d.setitem("b", 2)
-        assert d.getcell("b", False) is d.getcell("b", False)
-        assert d.getcell("c", True) is d.getcell("c", True)
+        d.setitem("a", 2)
+        v3 = strategy.version
+        assert v2 is not v3
+        assert d.getitem("a") == 2
 
-        assert d.getitem("a") == 1
-        assert d.getitem("b") == 2
+        d.setitem("a", 3)
+        v4 = strategy.version
+        assert v3 is v4
+        assert d.getitem("a") == 3
 
         d.delitem("a")
-        py.test.raises(KeyError, d.delitem, "a")
+        v5 = strategy.version
+        assert v5 is not v4
         assert d.getitem("a") is None
-        assert d.getcell("a", False) is acell
-        assert d.length() == 1
 
-        d.clear()
-        assert d.getitem("a") is None
-        assert d.getcell("a", False) is acell
-        assert d.length() == 0
+class AppTestModuleDict(object):
+    def setup_class(cls):
+        cls.space = gettestobjspace(**{"objspace.std.withcelldict": True})
+
+    def w_impl_used(self, obj):
+        import __pypy__
+        assert "ModuleDictStrategy" in __pypy__.internal_repr(obj)
+
+    def test_check_module_uses_module_dict(self):
+        m = type(__builtins__)("abc")
+        self.impl_used(m.__dict__)
+
+    def test_key_not_there(self):
+        d = type(__builtins__)("abc").__dict__
+        raises(KeyError, "d['def']")
+
+    def test_fallback_evil_key(self):
+        class F(object):
+            def __hash__(self):
+                return hash("s")
+            def __eq__(self, other):
+                return other == "s"
+        d = type(__builtins__)("abc").__dict__
+        d["s"] = 12
+        assert d["s"] == 12
+        assert d[F()] == d["s"]
+
+        d = type(__builtins__)("abc").__dict__
+        x = d.setdefault("s", 12)
+        assert x == 12
+        x = d.setdefault(F(), 12)
+        assert x == 12
+
+        d = type(__builtins__)("abc").__dict__
+        x = d.setdefault(F(), 12)
+        assert x == 12
+
+        d = type(__builtins__)("abc").__dict__
+        d["s"] = 12
+        del d[F()]
+
+        assert "s" not in d
+        assert F() not in d
+
+
+class TestModuleDictImplementation(BaseTestRDictImplementation):
+    StrategyClass = ModuleDictStrategy
+
+class TestModuleDictImplementationWithBuiltinNames(BaseTestRDictImplementation):
+    StrategyClass = ModuleDictStrategy
+
+    string = "int"
+    string2 = "isinstance"
+
+
+class TestDevolvedModuleDictImplementation(BaseTestDevolvedDictImplementation):
+    StrategyClass = ModuleDictStrategy
+
+class TestDevolvedModuleDictImplementationWithBuiltinNames(BaseTestDevolvedDictImplementation):
+    StrategyClass = ModuleDictStrategy
+
+    string = "int"
+    string2 = "isinstance"
+

pypy/objspace/std/test/test_dictmultiobject.py

      W_DictMultiObject, setitem__DictMulti_ANY_ANY, getitem__DictMulti_ANY, \
      StringDictStrategy, ObjectDictStrategy
 
-from pypy.objspace.std.celldict import ModuleDictStrategy
 from pypy.conftest import gettestobjspace
 
 
                 set([('a', 1), ('b', 2), ('d', 4), ('e', 5)]))
 
 
-class AppTestModuleDict(object):
-    def setup_class(cls):
-        cls.space = gettestobjspace(**{"objspace.std.withcelldict": True})
-
-    def w_impl_used(self, obj):
-        import __pypy__
-        assert "ModuleDictStrategy" in __pypy__.internal_repr(obj)
-
-    def test_check_module_uses_module_dict(self):
-        m = type(__builtins__)("abc")
-        self.impl_used(m.__dict__)
-
-    def test_key_not_there(self):
-        d = type(__builtins__)("abc").__dict__
-        raises(KeyError, "d['def']")
-
-    def test_fallback_evil_key(self):
-        class F(object):
-            def __hash__(self):
-                return hash("s")
-            def __eq__(self, other):
-                return other == "s"
-        d = type(__builtins__)("abc").__dict__
-        d["s"] = 12
-        assert d["s"] == 12
-        assert d[F()] == d["s"]
-
-        d = type(__builtins__)("abc").__dict__
-        x = d.setdefault("s", 12)
-        assert x == 12
-        x = d.setdefault(F(), 12)
-        assert x == 12
-
-        d = type(__builtins__)("abc").__dict__
-        x = d.setdefault(F(), 12)
-        assert x == 12
-
-        d = type(__builtins__)("abc").__dict__
-        d["s"] = 12
-        del d[F()]
-
-        assert "s" not in d
-        assert F() not in d
 
 class AppTestStrategies(object):
     def w_get_strategy(self, obj):
 ##     ImplementionClass = MeasuringDictImplementation
 ##     DevolvedClass = MeasuringDictImplementation
 
-class TestModuleDictImplementation(BaseTestRDictImplementation):
-    StrategyClass = ModuleDictStrategy
-
-class TestModuleDictImplementationWithBuiltinNames(BaseTestRDictImplementation):
-    StrategyClass = ModuleDictStrategy
-
-    string = "int"
-    string2 = "isinstance"
-
-
 class BaseTestDevolvedDictImplementation(BaseTestRDictImplementation):
     def fill_impl(self):
         BaseTestRDictImplementation.fill_impl(self)
 class TestDevolvedStrDictImplementation(BaseTestDevolvedDictImplementation):
     StrategyClass = StringDictStrategy
 
-class TestDevolvedModuleDictImplementation(BaseTestDevolvedDictImplementation):
-    StrategyClass = ModuleDictStrategy
-
-class TestDevolvedModuleDictImplementationWithBuiltinNames(BaseTestDevolvedDictImplementation):
-    StrategyClass = ModuleDictStrategy
-
-    string = "int"
-    string2 = "isinstance"
-
 
 def test_module_uses_strdict():
     fakespace = FakeSpace()