Commits

Carl Friedrich Bolz committed 1ecd25d Merge

merge faster-heapcache

Comments (0)

Files changed (2)

pypy/jit/metainterp/heapcache.py

         self.dependencies = {}
         # contains frame boxes that are not virtualizables
         self.nonstandard_virtualizables = {}
+
         # heap cache
         # maps descrs to {from_box, to_box} dicts
         self.heap_cache = {}
         # cache the length of arrays
         self.length_cache = {}
 
+        # replace_box is called surprisingly often, therefore it's not efficient
+        # to go over all the dicts and fix them.
+        # instead, these two dicts are kept, and a replace_box adds an entry to
+        # each of them.
+        # every time one of the dicts heap_cache, heap_array_cache, length_cache
+        # is accessed, suitable indirections need to be performed
+
+        # this looks all very subtle, but in practice the patterns of
+        # replacements should not be that complex. Usually a box is replaced by
+        # a const, once. Also, if something goes wrong, the effect is that less
+        # caching than possible is done, which is not a huge problem.
+        self.input_indirections = {}
+        self.output_indirections = {}
+
+    def _input_indirection(self, box):
+        return self.input_indirections.get(box, box)
+
+    def _output_indirection(self, box):
+        return self.output_indirections.get(box, box)
+
     def invalidate_caches(self, opnum, descr, argboxes):
         self.mark_escaped(opnum, argboxes)
         self.clear_caches(opnum, descr, argboxes)
         self.arraylen_now_known(box, lengthbox)
 
     def getfield(self, box, descr):
+        box = self._input_indirection(box)
         d = self.heap_cache.get(descr, None)
         if d:
             tobox = d.get(box, None)
-            if tobox:
-                return tobox
+            return self._output_indirection(tobox)
         return None
 
     def getfield_now_known(self, box, descr, fieldbox):
+        box = self._input_indirection(box)
+        fieldbox = self._input_indirection(fieldbox)
         self.heap_cache.setdefault(descr, {})[box] = fieldbox
 
     def setfield(self, box, descr, fieldbox):
         self.heap_cache[descr] = new_d
 
     def _do_write_with_aliasing(self, d, box, fieldbox):
+        box = self._input_indirection(box)
+        fieldbox = self._input_indirection(fieldbox)
         # slightly subtle logic here
         # a write to an arbitrary box, all other boxes can alias this one
         if not d or box not in self.new_boxes:
         return new_d
 
     def getarrayitem(self, box, descr, indexbox):
+        box = self._input_indirection(box)
         if not isinstance(indexbox, ConstInt):
             return
         index = indexbox.getint()
         if cache:
             indexcache = cache.get(index, None)
             if indexcache is not None:
-                return indexcache.get(box, None)
+                return self._output_indirection(indexcache.get(box, None))
 
     def getarrayitem_now_known(self, box, descr, indexbox, valuebox):
+        box = self._input_indirection(box)
+        valuebox = self._input_indirection(valuebox)
         if not isinstance(indexbox, ConstInt):
             return
         index = indexbox.getint()
         cache[index] = self._do_write_with_aliasing(indexcache, box, valuebox)
 
     def arraylen(self, box):
-        return self.length_cache.get(box, None)
+        box = self._input_indirection(box)
+        return self._output_indirection(self.length_cache.get(box, None))
 
     def arraylen_now_known(self, box, lengthbox):
-        self.length_cache[box] = lengthbox
-
-    def _replace_box(self, d, oldbox, newbox):
-        new_d = {}
-        for frombox, tobox in d.iteritems():
-            if frombox is oldbox:
-                frombox = newbox
-            if tobox is oldbox:
-                tobox = newbox
-            new_d[frombox] = tobox
-        return new_d
+        box = self._input_indirection(box)
+        self.length_cache[box] = self._input_indirection(lengthbox)
 
     def replace_box(self, oldbox, newbox):
-        for descr, d in self.heap_cache.iteritems():
-            self.heap_cache[descr] = self._replace_box(d, oldbox, newbox)
-        for descr, d in self.heap_array_cache.iteritems():
-            for index, cache in d.iteritems():
-                d[index] = self._replace_box(cache, oldbox, newbox)
-        self.length_cache = self._replace_box(self.length_cache, oldbox, newbox)
+        self.input_indirections[self._output_indirection(newbox)] = self._input_indirection(oldbox)
+        self.output_indirections[self._input_indirection(oldbox)] = self._output_indirection(newbox)

pypy/jit/metainterp/test/test_heapcache.py

 from pypy.jit.metainterp.resoperation import rop
 from pypy.jit.metainterp.history import ConstInt
 
-box1 = object()
-box2 = object()
-box3 = object()
-box4 = object()
+box1 = "box1"
+box2 = "box2"
+box3 = "box3"
+box4 = "box4"
+box5 = "box5"
 lengthbox1 = object()
 lengthbox2 = object()
+lengthbox3 = object()
 descr1 = object()
 descr2 = object()
 descr3 = object()
         h.setfield(box1, descr2, box3)
         h.setfield(box2, descr3, box3)
         h.replace_box(box1, box4)
-        assert h.getfield(box1, descr1) is None
-        assert h.getfield(box1, descr2) is None
         assert h.getfield(box4, descr1) is box2
         assert h.getfield(box4, descr2) is box3
         assert h.getfield(box2, descr3) is box3
+        h.setfield(box4, descr1, box3)
+        assert h.getfield(box4, descr1) is box3
+
+        h = HeapCache()
+        h.setfield(box1, descr1, box2)
+        h.setfield(box1, descr2, box3)
+        h.setfield(box2, descr3, box3)
+        h.replace_box(box3, box4)
+        assert h.getfield(box1, descr1) is box2
+        assert h.getfield(box1, descr2) is box4
+        assert h.getfield(box2, descr3) is box4
+
+    def test_replace_box_twice(self):
+        h = HeapCache()
+        h.setfield(box1, descr1, box2)
+        h.setfield(box1, descr2, box3)
+        h.setfield(box2, descr3, box3)
+        h.replace_box(box1, box4)
+        h.replace_box(box4, box5)
+        assert h.getfield(box5, descr1) is box2
+        assert h.getfield(box5, descr2) is box3
+        assert h.getfield(box2, descr3) is box3
+        h.setfield(box5, descr1, box3)
+        assert h.getfield(box4, descr1) is box3
+
+        h = HeapCache()
+        h.setfield(box1, descr1, box2)
+        h.setfield(box1, descr2, box3)
+        h.setfield(box2, descr3, box3)
+        h.replace_box(box3, box4)
+        h.replace_box(box4, box5)
+        assert h.getfield(box1, descr1) is box2
+        assert h.getfield(box1, descr2) is box5
+        assert h.getfield(box2, descr3) is box5
 
     def test_replace_box_array(self):
         h = HeapCache()
         h.setarrayitem(box3, descr2, index2, box1)
         h.setarrayitem(box2, descr3, index2, box3)
         h.replace_box(box1, box4)
-        assert h.getarrayitem(box1, descr1, index1) is None
-        assert h.getarrayitem(box1, descr2, index1) is None
-        assert h.arraylen(box1) is None
         assert h.arraylen(box4) is lengthbox1
         assert h.getarrayitem(box4, descr1, index1) is box2
         assert h.getarrayitem(box4, descr2, index1) is box3
         h.replace_box(lengthbox1, lengthbox2)
         assert h.arraylen(box4) is lengthbox2
 
+    def test_replace_box_array_twice(self):
+        h = HeapCache()
+        h.setarrayitem(box1, descr1, index1, box2)
+        h.setarrayitem(box1, descr2, index1, box3)
+        h.arraylen_now_known(box1, lengthbox1)
+        h.setarrayitem(box2, descr1, index2, box1)
+        h.setarrayitem(box3, descr2, index2, box1)
+        h.setarrayitem(box2, descr3, index2, box3)
+        h.replace_box(box1, box4)
+        h.replace_box(box4, box5)
+        assert h.arraylen(box4) is lengthbox1
+        assert h.getarrayitem(box5, descr1, index1) is box2
+        assert h.getarrayitem(box5, descr2, index1) is box3
+        assert h.getarrayitem(box2, descr1, index2) is box5
+        assert h.getarrayitem(box3, descr2, index2) is box5
+        assert h.getarrayitem(box2, descr3, index2) is box3
+
+        h.replace_box(lengthbox1, lengthbox2)
+        h.replace_box(lengthbox2, lengthbox3)
+        assert h.arraylen(box4) is lengthbox3
+
     def test_ll_arraycopy(self):
         h = HeapCache()
         h.new_array(box1, lengthbox1)