Author: Carl Friedrich Bolz <cfb...@gmx.de> Branch: Changeset: r54719:1ecd25d20dab Date: 2012-04-24 14:52 +0200 http://bitbucket.org/pypy/pypy/changeset/1ecd25d20dab/
Log: merge faster-heapcache diff --git a/pypy/jit/metainterp/heapcache.py b/pypy/jit/metainterp/heapcache.py --- a/pypy/jit/metainterp/heapcache.py +++ b/pypy/jit/metainterp/heapcache.py @@ -20,6 +20,7 @@ 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 = {} @@ -29,6 +30,26 @@ # 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) @@ -132,14 +153,16 @@ 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): @@ -148,6 +171,8 @@ 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: @@ -166,6 +191,7 @@ return new_d def getarrayitem(self, box, descr, indexbox): + box = self._input_indirection(box) if not isinstance(indexbox, ConstInt): return index = indexbox.getint() @@ -173,9 +199,11 @@ 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() @@ -198,25 +226,13 @@ 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) diff --git a/pypy/jit/metainterp/test/test_heapcache.py b/pypy/jit/metainterp/test/test_heapcache.py --- a/pypy/jit/metainterp/test/test_heapcache.py +++ b/pypy/jit/metainterp/test/test_heapcache.py @@ -2,12 +2,14 @@ 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() @@ -276,11 +278,43 @@ 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() @@ -291,9 +325,6 @@ 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 @@ -304,6 +335,27 @@ 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) _______________________________________________ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit