1. Pypy
  2. Untitled project
  3. pypy

Commits

Armin Rigo  committed 12503b1 Merge

merge heads

  • Participants
  • Parent commits f6ace31, 57c30d4
  • Branches default

Comments (0)

Files changed (23)

File pypy/doc/whatsnew-head.rst

View file
 
 .. branch: remove-numpypy
 Remove lib_pypy/numpypy in favor of external numpy fork
+
+.. branch: jit-counter
+Tweak the jit counters: decay them at minor collection (actually
+only every 32 minor collection is enough). Should avoid the "memory
+leaks" observed in long-running processes, actually created by the
+jit compiling more and more rarely executed paths.

File pypy/module/pypyjit/interp_jit.py

View file
     name = opcode_method_names[ord(bytecode.co_code[next_instr])]
     return '%s #%d %s' % (bytecode.get_repr(), next_instr, name)
 
-def make_greenkey_dict_key(next_instr, is_being_profiled):
-    # use only uints as keys in the jit_cells dict, rather than
-    # a tuple (next_instr, is_being_profiled)
-    return (
-        (next_instr << 1) |
-        r_uint(intmask(is_being_profiled))
-    )
-
-def get_jitcell_at(next_instr, is_being_profiled, bytecode):
-    key = make_greenkey_dict_key(next_instr, is_being_profiled)
-    return bytecode.jit_cells.get(key, None)
-
-def set_jitcell_at(newcell, next_instr, is_being_profiled, bytecode):
-    key = make_greenkey_dict_key(next_instr, is_being_profiled)
-    bytecode.jit_cells[key] = newcell
-
 
 def should_unroll_one_iteration(next_instr, is_being_profiled, bytecode):
     return (bytecode.co_flags & CO_GENERATOR) != 0
     virtualizables = ['frame']
 
 pypyjitdriver = PyPyJitDriver(get_printable_location = get_printable_location,
-                              get_jitcell_at = get_jitcell_at,
-                              set_jitcell_at = set_jitcell_at,
                               should_unroll_one_iteration =
                               should_unroll_one_iteration,
                               name='pypyjit')
     return intmask(decr_by)
 
 
-PyCode__initialize = PyCode._initialize
-
-class __extend__(PyCode):
-    __metaclass__ = extendabletype
-
-    def _initialize(self):
-        PyCode__initialize(self)
-        self.jit_cells = {}
-
-    def _cleanup_(self):
-        self.jit_cells = {}
-
 # ____________________________________________________________
 #
 # Public interface

File rpython/jit/backend/llsupport/gc.py

View file
         translator = self.translator
         self.layoutbuilder = framework.TransformerLayoutBuilder(translator)
         self.layoutbuilder.delay_encoding()
-        translator._jit2gc = {'layoutbuilder': self.layoutbuilder}
+        if not hasattr(translator, '_jit2gc'):
+            translator._jit2gc = {}
+        translator._jit2gc['layoutbuilder'] = self.layoutbuilder
 
     def _setup_gcclass(self):
         from rpython.memory.gcheader import GCHeaderBuilder

File rpython/jit/codewriter/longlong.py

View file
     getfloatstorage = lambda x: x
     getrealfloat    = lambda x: x
     gethash         = compute_hash
+    gethash_fast    = longlong2float.float2longlong
     is_longlong     = lambda TYPE: False
 
     # -------------------------------------
     getfloatstorage = longlong2float.float2longlong
     getrealfloat    = longlong2float.longlong2float
     gethash         = lambda xll: rarithmetic.intmask(xll - (xll >> 32))
+    gethash_fast    = gethash
     is_longlong     = lambda TYPE: (TYPE is lltype.SignedLongLong or
                                     TYPE is lltype.UnsignedLongLong)
 

File rpython/jit/metainterp/compile.py

View file
 import weakref
-from rpython.rtyper.lltypesystem import lltype
+from rpython.rtyper.lltypesystem import lltype, llmemory
 from rpython.rtyper.annlowlevel import cast_instance_to_gcref
 from rpython.rlib.objectmodel import we_are_translated
 from rpython.rlib.debug import debug_start, debug_stop, debug_print
+from rpython.rlib.rarithmetic import r_uint, intmask
 from rpython.rlib import rstack
 from rpython.rlib.jit import JitDebugInfo, Counters, dont_look_inside
 from rpython.conftest import option
     pass
 
 class ResumeGuardDescr(ResumeDescr):
-    _counter = 0        # on a GUARD_VALUE, there is one counter per value;
-    _counters = None    # they get stored in _counters then.
-
     # this class also gets the following attributes stored by resume.py code
-
     # XXX move all of unused stuff to guard_op, now that we can have
     #     a separate class, so it does not survive that long
     rd_snapshot = None
     rd_virtuals = None
     rd_pendingfields = lltype.nullptr(PENDINGFIELDSP.TO)
 
-    CNT_BASE_MASK  =  0x0FFFFFFF     # the base counter value
-    CNT_BUSY_FLAG  =  0x10000000     # if set, busy tracing from the guard
-    CNT_TYPE_MASK  =  0x60000000     # mask for the type
+    status = r_uint(0)
 
-    CNT_INT        =  0x20000000
-    CNT_REF        =  0x40000000
-    CNT_FLOAT      =  0x60000000
+    ST_BUSY_FLAG    = 0x01     # if set, busy tracing from the guard
+    ST_TYPE_MASK    = 0x06     # mask for the type (TY_xxx)
+    ST_SHIFT        = 3        # in "status >> ST_SHIFT" is stored:
+                               # - if TY_NONE, the jitcounter index directly
+                               # - otherwise, the guard_value failarg index
+    TY_NONE         = 0x00
+    TY_INT          = 0x02
+    TY_REF          = 0x04
+    TY_FLOAT        = 0x06
 
-    def store_final_boxes(self, guard_op, boxes):
+    def store_final_boxes(self, guard_op, boxes, metainterp_sd):
         guard_op.setfailargs(boxes)
         self.rd_count = len(boxes)
         self.guard_opnum = guard_op.getopnum()
+        #
+        if metainterp_sd.warmrunnerdesc is not None:   # for tests
+            jitcounter = metainterp_sd.warmrunnerdesc.jitcounter
+            self.status = jitcounter.fetch_next_index() << self.ST_SHIFT
 
     def make_a_counter_per_value(self, guard_value_op):
         assert guard_value_op.getopnum() == rop.GUARD_VALUE
         except ValueError:
             return     # xxx probably very rare
         else:
-            if i > self.CNT_BASE_MASK:
-                return    # probably never, but better safe than sorry
             if box.type == history.INT:
-                cnt = self.CNT_INT
+                ty = self.TY_INT
             elif box.type == history.REF:
-                cnt = self.CNT_REF
+                ty = self.TY_REF
             elif box.type == history.FLOAT:
-                cnt = self.CNT_FLOAT
+                ty = self.TY_FLOAT
             else:
                 assert 0, box.type
-            assert cnt > self.CNT_BASE_MASK
-            self._counter = cnt | i
+            self.status = ty | (r_uint(i) << self.ST_SHIFT)
 
     def handle_fail(self, deadframe, metainterp_sd, jitdriver_sd):
         if self.must_compile(deadframe, metainterp_sd, jitdriver_sd):
     _trace_and_compile_from_bridge._dont_inline_ = True
 
     def must_compile(self, deadframe, metainterp_sd, jitdriver_sd):
-        trace_eagerness = jitdriver_sd.warmstate.trace_eagerness
+        jitcounter = metainterp_sd.warmrunnerdesc.jitcounter
         #
-        if self._counter <= self.CNT_BASE_MASK:
-            # simple case: just counting from 0 to trace_eagerness
-            self._counter += 1
-            return self._counter >= trace_eagerness
+        if self.status & (self.ST_BUSY_FLAG | self.ST_TYPE_MASK) == 0:
+            # common case: this is not a guard_value, and we are not
+            # already busy tracing.  The rest of self.status stores a
+            # valid per-guard index in the jitcounter.
+            index = self.status >> self.ST_SHIFT
         #
         # do we have the BUSY flag?  If so, we're tracing right now, e.g. in an
         # outer invocation of the same function, so don't trace again for now.
-        elif self._counter & self.CNT_BUSY_FLAG:
+        elif self.status & self.ST_BUSY_FLAG:
             return False
         #
-        else: # we have a GUARD_VALUE that fails.  Make a _counters instance
-            # (only now, when the guard is actually failing at least once),
-            # and use it to record some statistics about the failing values.
-            index = self._counter & self.CNT_BASE_MASK
-            typetag = self._counter & self.CNT_TYPE_MASK
-            counters = self._counters
-            if typetag == self.CNT_INT:
-                intvalue = metainterp_sd.cpu.get_int_value(
-                    deadframe, index)
-                if counters is None:
-                    self._counters = counters = ResumeGuardCountersInt()
-                else:
-                    assert isinstance(counters, ResumeGuardCountersInt)
-                counter = counters.see_int(intvalue)
-            elif typetag == self.CNT_REF:
-                refvalue = metainterp_sd.cpu.get_ref_value(
-                    deadframe, index)
-                if counters is None:
-                    self._counters = counters = ResumeGuardCountersRef()
-                else:
-                    assert isinstance(counters, ResumeGuardCountersRef)
-                counter = counters.see_ref(refvalue)
-            elif typetag == self.CNT_FLOAT:
-                floatvalue = metainterp_sd.cpu.get_float_value(
-                    deadframe, index)
-                if counters is None:
-                    self._counters = counters = ResumeGuardCountersFloat()
-                else:
-                    assert isinstance(counters, ResumeGuardCountersFloat)
-                counter = counters.see_float(floatvalue)
+        else:    # we have a GUARD_VALUE that fails.
+            from rpython.rlib.objectmodel import current_object_addr_as_int
+
+            index = intmask(self.status >> self.ST_SHIFT)
+            typetag = intmask(self.status & self.ST_TYPE_MASK)
+
+            # fetch the actual value of the guard_value, possibly turning
+            # it to an integer
+            if typetag == self.TY_INT:
+                intval = metainterp_sd.cpu.get_int_value(deadframe, index)
+            elif typetag == self.TY_REF:
+                refval = metainterp_sd.cpu.get_ref_value(deadframe, index)
+                intval = lltype.cast_ptr_to_int(refval)
+            elif typetag == self.TY_FLOAT:
+                floatval = metainterp_sd.cpu.get_float_value(deadframe, index)
+                intval = longlong.gethash_fast(floatval)
             else:
                 assert 0, typetag
-            return counter >= trace_eagerness
+
+            if not we_are_translated():
+                if isinstance(intval, llmemory.AddressAsInt):
+                    intval = llmemory.cast_adr_to_int(
+                        llmemory.cast_int_to_adr(intval), "forced")
+
+            hash = (current_object_addr_as_int(self) * 777767777 +
+                    intval * 1442968193)
+            index = jitcounter.get_index(hash)
+        #
+        increment = jitdriver_sd.warmstate.increment_trace_eagerness
+        return jitcounter.tick(index, increment)
 
     def start_compiling(self):
         # start tracing and compiling from this guard.
-        self._counter |= self.CNT_BUSY_FLAG
+        self.status |= self.ST_BUSY_FLAG
 
     def done_compiling(self):
-        # done tracing and compiling from this guard.  Either the bridge has
-        # been successfully compiled, in which case whatever value we store
-        # in self._counter will not be seen any more, or not, in which case
-        # we should reset the counter to 0, in order to wait a bit until the
-        # next attempt.
-        if self._counter >= 0:
-            self._counter = 0
-        self._counters = None
+        # done tracing and compiling from this guard.  Note that if the
+        # bridge has not been successfully compiled, the jitcounter for
+        # it was reset to 0 already by jitcounter.tick() and not
+        # incremented at all as long as ST_BUSY_FLAG was set.
+        self.status &= ~self.ST_BUSY_FLAG
 
     def compile_and_attach(self, metainterp, new_loop):
         # We managed to create a bridge.  Attach the new operations
         return res
 
 
-class AbstractResumeGuardCounters(object):
-    # Completely custom algorithm for now: keep 5 pairs (value, counter),
-    # and when we need more, we discard the middle pair (middle in the
-    # current value of the counter).  That way, we tend to keep the
-    # values with a high counter, but also we avoid always throwing away
-    # the most recently added value.  **THIS ALGO MUST GO AWAY AT SOME POINT**
-    pass
-
-def _see(self, newvalue):
-    # find and update an existing counter
-    unused = -1
-    for i in range(5):
-        cnt = self.counters[i]
-        if cnt:
-            if self.values[i] == newvalue:
-                cnt += 1
-                self.counters[i] = cnt
-                return cnt
-        else:
-            unused = i
-    # not found.  Use a previously unused entry, if there is one
-    if unused >= 0:
-        self.counters[unused] = 1
-        self.values[unused] = newvalue
-        return 1
-    # no unused entry.  Overwrite the middle one.  Computed with indices
-    # a, b, c meaning the highest, second highest, and third highest
-    # entries.
-    a = 0
-    b = c = -1
-    for i in range(1, 5):
-        if self.counters[i] > self.counters[a]:
-            c = b
-            b = a
-            a = i
-        elif b < 0 or self.counters[i] > self.counters[b]:
-            c = b
-            b = i
-        elif c < 0 or self.counters[i] > self.counters[c]:
-            c = i
-    self.counters[c] = 1
-    self.values[c] = newvalue
-    return 1
-
-class ResumeGuardCountersInt(AbstractResumeGuardCounters):
-    def __init__(self):
-        self.counters = [0] * 5
-        self.values = [0] * 5
-    see_int = func_with_new_name(_see, 'see_int')
-
-class ResumeGuardCountersRef(AbstractResumeGuardCounters):
-    def __init__(self):
-        self.counters = [0] * 5
-        self.values = [history.ConstPtr.value] * 5
-    see_ref = func_with_new_name(_see, 'see_ref')
-
-class ResumeGuardCountersFloat(AbstractResumeGuardCounters):
-    def __init__(self):
-        self.counters = [0] * 5
-        self.values = [longlong.ZEROF] * 5
-    see_float = func_with_new_name(_see, 'see_float')
-
-
 class ResumeFromInterpDescr(ResumeDescr):
     def __init__(self, original_greenkey):
         self.original_greenkey = original_greenkey

File rpython/jit/metainterp/counter.py

View file
+from rpython.rlib.rarithmetic import r_singlefloat, r_uint
+from rpython.rtyper.lltypesystem import lltype, rffi
+from rpython.translator.tool.cbuild import ExternalCompilationInfo
+
+
+r_uint32 = rffi.r_uint
+assert r_uint32.BITS == 32
+UINT32MAX = 2 ** 32 - 1
+
+
+class JitCounter:
+    DEFAULT_SIZE = 4096
+
+    def __init__(self, size=DEFAULT_SIZE, translator=None):
+        "NOT_RPYTHON"
+        self.size = size
+        self.shift = 1
+        while (UINT32MAX >> self.shift) != size - 1:
+            self.shift += 1
+            assert self.shift < 999, "size is not a power of two <= 2**31"
+        self.timetable = lltype.malloc(rffi.CArray(rffi.FLOAT), size,
+                                       flavor='raw', zero=True,
+                                       track_allocation=False)
+        self.celltable = [None] * size
+        self._nextindex = r_uint(0)
+        #
+        if translator is not None:
+            class Glob:
+                step = 0
+            glob = Glob()
+            def invoke_after_minor_collection():
+                # After 32 minor collections, we call decay_all_counters().
+                # The "--jit decay=N" option measures the amount the
+                # counters are then reduced by.
+                glob.step += 1
+                if glob.step == 32:
+                    glob.step = 0
+                    self.decay_all_counters()
+            if not hasattr(translator, '_jit2gc'):
+                translator._jit2gc = {}
+            translator._jit2gc['invoke_after_minor_collection'] = (
+                invoke_after_minor_collection)
+
+    def compute_threshold(self, threshold):
+        """Return the 'increment' value corresponding to the given number."""
+        if threshold <= 0:
+            return 0.0   # no increment, never reach 1.0
+        return 1.0 / (threshold - 0.001)
+
+    def get_index(self, hash):
+        """Return the index (< self.size) from a hash value.  This truncates
+        the hash to 32 bits, and then keep the *highest* remaining bits.
+        Be sure that hash is computed correctly."""
+        hash32 = r_uint(r_uint32(hash))  # mask off the bits higher than 32
+        index = hash32 >> self.shift     # shift, resulting in a value < size
+        return index                     # return the result as a r_uint
+    get_index._always_inline_ = True
+
+    def fetch_next_index(self):
+        result = self._nextindex
+        self._nextindex = (result + 1) & self.get_index(-1)
+        return result
+
+    def tick(self, index, increment):
+        counter = float(self.timetable[index]) + increment
+        if counter < 1.0:
+            self.timetable[index] = r_singlefloat(counter)
+            return False
+        else:
+            # when the bound is reached, we immediately reset the value to 0.0
+            self.reset(index)
+            return True
+    tick._always_inline_ = True
+
+    def reset(self, index):
+        self.timetable[index] = r_singlefloat(0.0)
+
+    def lookup_chain(self, index):
+        return self.celltable[index]
+
+    def cleanup_chain(self, index):
+        self.reset(index)
+        self.install_new_cell(index, None)
+
+    def install_new_cell(self, index, newcell):
+        cell = self.celltable[index]
+        keep = newcell
+        while cell is not None:
+            nextcell = cell.next
+            if not cell.should_remove_jitcell():
+                cell.next = keep
+                keep = cell
+            cell = nextcell
+        self.celltable[index] = keep
+
+    def set_decay(self, decay):
+        """Set the decay, from 0 (none) to 1000 (max)."""
+        if decay < 0:
+            decay = 0
+        elif decay > 1000:
+            decay = 1000
+        self.decay_by_mult = 1.0 - (decay * 0.001)
+
+    def decay_all_counters(self):
+        # Called during a minor collection by the GC, to gradually decay
+        # counters that didn't reach their maximum.  Thus if a counter
+        # is incremented very slowly, it will never reach the maximum.
+        # This avoids altogether the JIT compilation of rare paths.
+        # We also call this function when any maximum bound is reached,
+        # to avoid sudden bursts of JIT-compilation (the next one will
+        # not reach the maximum bound immmediately after).  This is
+        # important in corner cases where we would suddenly compile more
+        # than one loop because all counters reach the bound at the same
+        # time, but where compiling all but the first one is pointless.
+        size = self.size
+        pypy__decay_jit_counters(self.timetable, self.decay_by_mult, size)
+
+
+# this function is written directly in C; gcc will optimize it using SSE
+eci = ExternalCompilationInfo(post_include_bits=["""
+static void pypy__decay_jit_counters(float table[], double f1, long size1) {
+    float f = (float)f1;
+    int i, size = (int)size1;
+    for (i=0; i<size; i++)
+        table[i] *= f;
+}
+"""])
+
+pypy__decay_jit_counters = rffi.llexternal(
+    "pypy__decay_jit_counters", [rffi.FLOATP, lltype.Float, lltype.Signed],
+    lltype.Void, compilation_info=eci, _nowrapper=True, sandboxsafe=True)
+
+
+# ____________________________________________________________
+#
+# A non-RPython version that avoids issues with rare random collisions,
+# which make all tests brittle
+
+class DeterministicJitCounter(JitCounter):
+    def __init__(self):
+        from collections import defaultdict
+        JitCounter.__init__(self, size=8)
+        zero = r_singlefloat(0.0)
+        self.timetable = defaultdict(lambda: zero)
+        self.celltable = defaultdict(lambda: None)
+
+    def get_index(self, hash):
+        "NOT_RPYTHON"
+        return hash
+
+    def decay_all_counters(self):
+        "NOT_RPYTHON"
+        pass

File rpython/jit/metainterp/optimizeopt/optimizer.py

View file
                 raise resume.TagOverflow
         except resume.TagOverflow:
             raise compile.giveup()
-        descr.store_final_boxes(op, newboxes)
+        descr.store_final_boxes(op, newboxes, self.metainterp_sd)
         #
         if op.getopnum() == rop.GUARD_VALUE:
             if self.getvalue(op.getarg(0)) in self.bool_boxes:

File rpython/jit/metainterp/optimizeopt/test/test_util.py

View file
 from rpython.jit.metainterp.quasiimmut import QuasiImmutDescr
 from rpython.jit.metainterp import compile, resume, history
 from rpython.jit.metainterp.jitprof import EmptyProfiler
+from rpython.jit.metainterp.counter import DeterministicJitCounter
 from rpython.config.translationoption import get_combined_translation_config
 from rpython.jit.metainterp.resoperation import rop, opname, ResOperation
 from rpython.jit.metainterp.optimizeopt.unroll import Inliner
         class memory_manager:
             retrace_limit = 5
             max_retrace_guards = 15
+        jitcounter = DeterministicJitCounter()
 
 class Storage(compile.ResumeGuardDescr):
     "for tests."
     def __init__(self, metainterp_sd=None, original_greenkey=None):
         self.metainterp_sd = metainterp_sd
         self.original_greenkey = original_greenkey
-    def store_final_boxes(self, op, boxes):
+    def store_final_boxes(self, op, boxes, metainterp_sd):
         op.setfailargs(boxes)
     def __eq__(self, other):
         return type(self) is type(other)      # xxx obscure

File rpython/jit/metainterp/pyjitpl.py

View file
             raise NotImplementedError(opname[opnum])
 
     def get_procedure_token(self, greenkey, with_compiled_targets=False):
-        cell = self.jitdriver_sd.warmstate.jit_cell_at_key(greenkey)
+        JitCell = self.jitdriver_sd.warmstate.JitCell
+        cell = JitCell.get_jit_cell_at_key(greenkey)
+        if cell is None:
+            return None
         token = cell.get_procedure_token()
         if with_compiled_targets:
             if not token:

File rpython/jit/metainterp/test/support.py

View file
 
     class FakeWarmRunnerState(object):
         def attach_procedure_to_interp(self, greenkey, procedure_token):
-            cell = self.jit_cell_at_key(greenkey)
-            cell.set_procedure_token(procedure_token)
+            assert greenkey == []
+            self._cell.set_procedure_token(procedure_token)
 
         def helper_func(self, FUNCPTR, func):
             from rpython.rtyper.annlowlevel import llhelper
         def get_location_str(self, args):
             return 'location'
 
-        def jit_cell_at_key(self, greenkey):
-            assert greenkey == []
-            return self._cell
+        class JitCell:
+            @staticmethod
+            def get_jit_cell_at_key(greenkey):
+                assert greenkey == []
+                return FakeWarmRunnerState._cell
         _cell = FakeJitCell()
 
         trace_limit = sys.maxint

File rpython/jit/metainterp/test/test_compile.py

View file
 from rpython.jit.metainterp.history import ConstInt, History, Stats
 from rpython.jit.metainterp.history import INT
 from rpython.jit.metainterp.compile import compile_loop
-from rpython.jit.metainterp.compile import ResumeGuardCountersInt
 from rpython.jit.metainterp.compile import compile_tmp_callback
 from rpython.jit.metainterp import jitexc
 from rpython.jit.metainterp import jitprof, typesystem, compile
     #
     del cpu.seen[:]
 
-def test_resume_guard_counters():
-    rgc = ResumeGuardCountersInt()
-    # fill in the table
-    for i in range(5):
-        count = rgc.see_int(100+i)
-        assert count == 1
-        count = rgc.see_int(100+i)
-        assert count == 2
-        assert rgc.counters == [0] * (4-i) + [2] * (1+i)
-    for i in range(5):
-        count = rgc.see_int(100+i)
-        assert count == 3
-    # make a distribution:  [5, 4, 7, 6, 3]
-    assert rgc.counters == [3, 3, 3, 3, 3]
-    count = rgc.see_int(101)
-    assert count == 4
-    count = rgc.see_int(101)
-    assert count == 5
-    count = rgc.see_int(101)
-    assert count == 6
-    count = rgc.see_int(102)
-    assert count == 4
-    count = rgc.see_int(102)
-    assert count == 5
-    count = rgc.see_int(102)
-    assert count == 6
-    count = rgc.see_int(102)
-    assert count == 7
-    count = rgc.see_int(103)
-    assert count == 4
-    count = rgc.see_int(104)
-    assert count == 4
-    count = rgc.see_int(104)
-    assert count == 5
-    assert rgc.counters == [5, 4, 7, 6, 3]
-    # the next new item should throw away 104, as 5 is the middle counter
-    count = rgc.see_int(190)
-    assert count == 1
-    assert rgc.counters == [1, 4, 7, 6, 3]
-    # the next new item should throw away 103, as 4 is the middle counter
-    count = rgc.see_int(191)
-    assert count == 1
-    assert rgc.counters == [1, 1, 7, 6, 3]
-    # the next new item should throw away 100, as 3 is the middle counter
-    count = rgc.see_int(192)
-    assert count == 1
-    assert rgc.counters == [1, 1, 7, 6, 1]
-
 
 def test_compile_tmp_callback():
     from rpython.jit.codewriter import heaptracker

File rpython/jit/metainterp/test/test_counter.py

View file
+from rpython.jit.metainterp.counter import JitCounter
+
+
+def test_get_index():
+    jc = JitCounter(size=128)    # 7 bits
+    for i in range(10):
+        hash = 400000001 * i
+        index = jc.get_index(hash)
+        assert index == (hash >> (32 - 7))
+
+def test_fetch_next_index():
+    jc = JitCounter(size=4)
+    lst = [jc.fetch_next_index() for i in range(10)]
+    assert lst == [0, 1, 2, 3, 0, 1, 2, 3, 0, 1]
+
+def test_tick():
+    jc = JitCounter()
+    incr = jc.compute_threshold(4)
+    for i in range(5):
+        r = jc.tick(104, incr)
+        assert r is (i == 3)
+    for i in range(5):
+        r = jc.tick(108, incr)
+        s = jc.tick(109, incr)
+        assert r is (i == 3)
+        assert s is (i == 3)
+    jc.reset(108)
+    for i in range(5):
+        r = jc.tick(108, incr)
+        assert r is (i == 3)
+
+def test_install_new_chain():
+    class Dead:
+        next = None
+        def should_remove_jitcell(self):
+            return True
+    class Alive:
+        next = None
+        def should_remove_jitcell(self):
+            return False
+    #
+    jc = JitCounter()
+    assert jc.lookup_chain(104) is None
+    d1 = Dead() 
+    jc.install_new_cell(104, d1)
+    assert jc.lookup_chain(104) is d1
+    d2 = Dead()
+    jc.install_new_cell(104, d2)
+    assert jc.lookup_chain(104) is d2
+    assert d2.next is None
+    #
+    d3 = Alive()
+    jc.install_new_cell(104, d3)
+    assert jc.lookup_chain(104) is d3
+    assert d3.next is None
+    d4 = Alive()
+    jc.install_new_cell(104, d4)
+    assert jc.lookup_chain(104) is d3
+    assert d3.next is d4
+    assert d4.next is None

File rpython/jit/metainterp/test/test_memmgr.py

View file
 from rpython.jit.metainterp.test.support import LLJitMixin
 from rpython.rlib.jit import JitDriver, dont_look_inside
 from rpython.jit.metainterp.warmspot import get_stats
-from rpython.jit.metainterp.warmstate import JitCell
+from rpython.jit.metainterp.warmstate import BaseJitCell
 from rpython.rlib import rgc
 
 class FakeLoopToken:
     # these tests to pass. But we dont want it there always since that will
     # make all other tests take forever.
     def setup_class(cls):
-        original_get_procedure_token = JitCell.get_procedure_token
+        original_get_procedure_token = BaseJitCell.get_procedure_token
         def get_procedure_token(self):
             rgc.collect();
             return original_get_procedure_token(self)
-        JitCell.get_procedure_token = get_procedure_token
+        BaseJitCell.get_procedure_token = get_procedure_token
         cls.original_get_procedure_token = original_get_procedure_token
 
     def teardown_class(cls):
-        JitCell.get_procedure_token = cls.original_get_procedure_token
+        BaseJitCell.get_procedure_token = cls.original_get_procedure_token
 
     def test_loop_kept_alive(self):
         myjitdriver = JitDriver(greens=[], reds=['n'])

File rpython/jit/metainterp/test/test_recursive.py

View file
         assert res == 0
         self.check_max_trace_length(TRACE_LIMIT)
         self.check_enter_count_at_most(10) # maybe
-        self.check_aborted_count(7)
+        self.check_aborted_count(6)
 
     def test_trace_limit_bridge(self):
         def recursive(n):
 
         res = self.meta_interp(loop, [20], failargs_limit=FAILARGS_LIMIT,
                                listops=True)
-        self.check_aborted_count(5)
+        self.check_aborted_count(4)
 
     def test_max_failure_args_exc(self):
         FAILARGS_LIMIT = 10
         res = self.meta_interp(main, [20], failargs_limit=FAILARGS_LIMIT,
                                listops=True)
         assert not res
-        self.check_aborted_count(5)
+        self.check_aborted_count(4)
 
     def test_set_param_inlining(self):
         myjitdriver = JitDriver(greens=[], reds=['n', 'recurse'])

File rpython/jit/metainterp/test/test_warmstate.py

View file
 from rpython.rtyper.annlowlevel import llhelper
 from rpython.jit.metainterp.warmstate import wrap, unwrap, specialize_value
 from rpython.jit.metainterp.warmstate import equal_whatever, hash_whatever
-from rpython.jit.metainterp.warmstate import WarmEnterState, JitCell
+from rpython.jit.metainterp.warmstate import WarmEnterState
 from rpython.jit.metainterp.history import BoxInt, BoxFloat, BoxPtr
 from rpython.jit.metainterp.history import ConstInt, ConstFloat, ConstPtr
+from rpython.jit.metainterp.counter import DeterministicJitCounter
 from rpython.jit.codewriter import longlong
 from rpython.rlib.rarithmetic import r_singlefloat
 
     interpret(fn, [42], type_system='lltype')
 
 
-def test_make_jitcell_getter_default():
-    class FakeJitDriverSD:
-        _green_args_spec = [lltype.Signed, lltype.Float]
-    state = WarmEnterState(None, FakeJitDriverSD())
-    get_jitcell = state._make_jitcell_getter_default()
-    cell1 = get_jitcell(True, 42, 42.5)
-    assert isinstance(cell1, JitCell)
-    cell2 = get_jitcell(True, 42, 42.5)
-    assert cell1 is cell2
-    cell3 = get_jitcell(True, 41, 42.5)
-    assert get_jitcell(False, 42, 0.25) is None
-    cell4 = get_jitcell(True, 42, 0.25)
-    assert get_jitcell(False, 42, 0.25) is cell4
-    assert cell1 is not cell3 is not cell4 is not cell1
-
-def test_make_jitcell_getter():
-    class FakeJitDriverSD:
-        _green_args_spec = [lltype.Float]
-        _get_jitcell_at_ptr = None
-    state = WarmEnterState(None, FakeJitDriverSD())
-    get_jitcell = state.make_jitcell_getter()
-    cell1 = get_jitcell(True, 1.75)
-    cell2 = get_jitcell(True, 1.75)
-    assert cell1 is cell2
-    assert get_jitcell is state.make_jitcell_getter()
-
-def test_make_jitcell_getter_custom():
-    from rpython.rtyper.typesystem import LowLevelTypeSystem
-    class FakeRTyper:
-        type_system = LowLevelTypeSystem.instance
-    celldict = {}
-    def getter(x, y):
-        return celldict.get((x, y))
-    def setter(newcell, x, y):
-        newcell.x = x
-        newcell.y = y
-        celldict[x, y] = newcell
-    GETTER = lltype.Ptr(lltype.FuncType([lltype.Signed, lltype.Float],
-                                        llmemory.GCREF))
-    SETTER = lltype.Ptr(lltype.FuncType([llmemory.GCREF, lltype.Signed,
-                                         lltype.Float], lltype.Void))
-    class FakeWarmRunnerDesc:
-        rtyper = FakeRTyper()
-        cpu = None
-        memory_manager = None
-    class FakeJitDriverSD:
-        _get_jitcell_at_ptr = llhelper(GETTER, getter)
-        _set_jitcell_at_ptr = llhelper(SETTER, setter)
-    #
-    state = WarmEnterState(FakeWarmRunnerDesc(), FakeJitDriverSD())
-    get_jitcell = state._make_jitcell_getter_custom()
-    cell1 = get_jitcell(True, 5, 42.5)
-    assert isinstance(cell1, JitCell)
-    assert cell1.x == 5
-    assert cell1.y == 42.5
-    cell2 = get_jitcell(True, 5, 42.5)
-    assert cell2 is cell1
-    cell3 = get_jitcell(True, 41, 42.5)
-    assert get_jitcell(False, 42, 0.25) is None
-    cell4 = get_jitcell(True, 42, 0.25)
-    assert get_jitcell(False, 42, 0.25) is cell4
-    assert cell1 is not cell3 is not cell4 is not cell1
-
 def test_make_unwrap_greenkey():
     class FakeJitDriverSD:
         _green_args_spec = [lltype.Signed, lltype.Float]
     assert greenargs == (42, 42.5)
     assert type(greenargs[0]) is int
 
-def test_attach_unoptimized_bridge_from_interp():
-    class FakeJitDriverSD:
-        _green_args_spec = [lltype.Signed, lltype.Float]
-        _get_jitcell_at_ptr = None
-    state = WarmEnterState(None, FakeJitDriverSD())
-    get_jitcell = state.make_jitcell_getter()
-    class FakeLoopToken(object):
-        invalidated = False
-    looptoken = FakeLoopToken()
-    state.attach_procedure_to_interp([ConstInt(5),
-                                      constfloat(2.25)],
-                                     looptoken)
-    cell1 = get_jitcell(True, 5, 2.25)
-    assert cell1.counter < 0
-    assert cell1.get_procedure_token() is looptoken
-
 def test_make_jitdriver_callbacks_1():
     class FakeWarmRunnerDesc:
         cpu = None
         memory_manager = None
+        jitcounter = DeterministicJitCounter()
     class FakeJitDriverSD:
         jitdriver = None
         _green_args_spec = [lltype.Signed, lltype.Float]
         rtyper = None
         cpu = None
         memory_manager = None
+        jitcounter = DeterministicJitCounter()
     class FakeJitDriverSD:
         jitdriver = None
         _green_args_spec = [lltype.Signed, lltype.Float]
         _get_printable_location_ptr = llhelper(GET_LOCATION, get_location)
         _confirm_enter_jit_ptr = None
         _can_never_inline_ptr = None
-        _get_jitcell_at_ptr = None
         _should_unroll_one_iteration_ptr = None
         red_args_types = []
     state = WarmEnterState(FakeWarmRunnerDesc(), FakeJitDriverSD())
         rtyper = None
         cpu = None
         memory_manager = None
+        jitcounter = DeterministicJitCounter()
     class FakeJitDriverSD:
         jitdriver = None
         _green_args_spec = [lltype.Signed, lltype.Float]
         _get_printable_location_ptr = None
         _confirm_enter_jit_ptr = llhelper(ENTER_JIT, confirm_enter_jit)
         _can_never_inline_ptr = None
-        _get_jitcell_at_ptr = None
         _should_unroll_one_iteration_ptr = None
         red_args_types = []
 
         rtyper = None
         cpu = None
         memory_manager = None
+        jitcounter = DeterministicJitCounter()
     class FakeJitDriverSD:
         jitdriver = None
         _green_args_spec = [lltype.Signed, lltype.Float]
         _get_printable_location_ptr = None
         _confirm_enter_jit_ptr = None
         _can_never_inline_ptr = llhelper(CAN_NEVER_INLINE, can_never_inline)
-        _get_jitcell_at_ptr = None
         _should_unroll_one_iteration_ptr = None
         red_args_types = []
 
     state.make_jitdriver_callbacks()
     res = state.can_never_inline(5, 42.5)
     assert res is True
-
-def test_cleanup_jitcell_dict():
-    class FakeJitDriverSD:
-        _green_args_spec = [lltype.Signed]
-    #
-    # Test creating tons of jitcells that remain at 0
-    warmstate = WarmEnterState(None, FakeJitDriverSD())
-    get_jitcell = warmstate._make_jitcell_getter_default()
-    cell1 = get_jitcell(True, -1)
-    assert len(warmstate._jitcell_dict) == 1
-    #
-    for i in range(1, 20005):
-        get_jitcell(True, i)     # should trigger a clean-up at 20001
-        assert len(warmstate._jitcell_dict) == (i % 20000) + 1
-    #
-    # Same test, with one jitcell that has a counter of BASE instead of 0
-    warmstate = WarmEnterState(None, FakeJitDriverSD())
-    get_jitcell = warmstate._make_jitcell_getter_default()
-    cell2 = get_jitcell(True, -2)
-    cell2.counter = BASE = warmstate.THRESHOLD_LIMIT // 2    # 50%
-    #
-    for i in range(0, 20005):
-        get_jitcell(True, i)
-        assert len(warmstate._jitcell_dict) == (i % 19999) + 2
-    #
-    assert cell2 in warmstate._jitcell_dict.values()
-    assert cell2.counter == int(BASE * 0.92)   # decayed once
-    #
-    # Same test, with jitcells that are compiled and freed by the memmgr
-    warmstate = WarmEnterState(None, FakeJitDriverSD())
-    get_jitcell = warmstate._make_jitcell_getter_default()
-    get_jitcell(True, -1)
-    #
-    for i in range(1, 20005):
-        cell = get_jitcell(True, i)
-        cell.counter = -1
-        cell.wref_procedure_token = None    # or a dead weakref, equivalently
-        assert len(warmstate._jitcell_dict) == (i % 20000) + 1
-    #
-    # Same test, with counter == -2 (rare case, kept alive)
-    warmstate = WarmEnterState(None, FakeJitDriverSD())
-    get_jitcell = warmstate._make_jitcell_getter_default()
-    cell = get_jitcell(True, -1)
-    cell.counter = -2
-    #
-    for i in range(1, 20005):
-        cell = get_jitcell(True, i)
-        cell.counter = -2
-        assert len(warmstate._jitcell_dict) == i + 1

File rpython/jit/metainterp/warmspot.py

View file
         vrefinfo = VirtualRefInfo(self)
         self.codewriter.setup_vrefinfo(vrefinfo)
         #
+        from rpython.jit.metainterp import counter
+        if self.cpu.translate_support_code:
+            self.jitcounter = counter.JitCounter(translator=translator)
+        else:
+            self.jitcounter = counter.DeterministicJitCounter()
+        #
         self.hooks = policy.jithookiface
         self.make_virtualizable_infos()
         self.make_driverhook_graphs()
         jd._maybe_compile_and_run_fn = maybe_compile_and_run
 
     def make_driverhook_graphs(self):
-        from rpython.rlib.jit import BaseJitCell
-        bk = self.rtyper.annotator.bookkeeper
-        classdef = bk.getuniqueclassdef(BaseJitCell)
-        s_BaseJitCell_or_None = annmodel.SomeInstance(classdef,
-                                                      can_be_None=True)
-        s_BaseJitCell_not_None = annmodel.SomeInstance(classdef)
         s_Str = annmodel.SomeString()
         #
         annhelper = MixLevelHelperAnnotator(self.translator.rtyper)
         for jd in self.jitdrivers_sd:
-            jd._set_jitcell_at_ptr = self._make_hook_graph(jd,
-                annhelper, jd.jitdriver.set_jitcell_at, annmodel.s_None,
-                s_BaseJitCell_not_None)
-            jd._get_jitcell_at_ptr = self._make_hook_graph(jd,
-                annhelper, jd.jitdriver.get_jitcell_at, s_BaseJitCell_or_None)
             jd._get_printable_location_ptr = self._make_hook_graph(jd,
                 annhelper, jd.jitdriver.get_printable_location, s_Str)
             jd._confirm_enter_jit_ptr = self._make_hook_graph(jd,

File rpython/jit/metainterp/warmstate.py

View file
 from rpython.jit.codewriter import support, heaptracker, longlong
 from rpython.jit.metainterp import history
 from rpython.rlib.debug import debug_start, debug_stop, debug_print
-from rpython.rlib.jit import PARAMETERS, BaseJitCell
+from rpython.rlib.jit import PARAMETERS
 from rpython.rlib.nonconst import NonConstant
 from rpython.rlib.objectmodel import specialize, we_are_translated, r_dict
 from rpython.rlib.rarithmetic import intmask
         return rffi.cast(lltype.Signed, x)
 
 
-class JitCell(BaseJitCell):
-    # the counter can mean the following things:
-    #     counter >=  0: not yet traced, wait till threshold is reached
-    #     counter == -1: there is an entry bridge for this cell
-    #     counter == -2: tracing is currently going on for this cell
-    counter = 0
-    dont_trace_here = False
-    extra_delay = chr(0)
+JC_TRACING         = 0x01
+JC_DONT_TRACE_HERE = 0x02
+JC_TEMPORARY       = 0x04
+
+class BaseJitCell(object):
+    flags = 0     # JC_xxx flags
     wref_procedure_token = None
+    next = None
 
     def get_procedure_token(self):
         if self.wref_procedure_token is not None:
                 return token
         return None
 
-    def set_procedure_token(self, token):
+    def set_procedure_token(self, token, tmp=False):
         self.wref_procedure_token = self._makeref(token)
+        if tmp:
+            self.flags |= JC_TEMPORARY
+        else:
+            self.flags &= ~JC_TEMPORARY
 
     def _makeref(self, token):
         assert token is not None
         return weakref.ref(token)
 
+    def should_remove_jitcell(self):
+        if self.get_procedure_token() is not None:
+            return False    # don't remove JitCells with a procedure_token
+        # don't remove JitCells that are being traced, or JitCells with
+        # the "don't trace here" flag.  Other JitCells can be removed.
+        return (self.flags & (JC_TRACING | JC_DONT_TRACE_HERE)) == 0
+
 # ____________________________________________________________
 
 
 class WarmEnterState(object):
-    THRESHOLD_LIMIT = sys.maxint // 2
 
     def __init__(self, warmrunnerdesc, jitdriver_sd):
         "NOT_RPYTHON"
             self.profiler = None
         # initialize the state with the default values of the
         # parameters specified in rlib/jit.py
-        for name, default_value in PARAMETERS.items():
-            meth = getattr(self, 'set_param_' + name)
-            meth(default_value)
+        if self.warmrunnerdesc is not None:
+            for name, default_value in PARAMETERS.items():
+                meth = getattr(self, 'set_param_' + name)
+                meth(default_value)
 
     def _compute_threshold(self, threshold):
-        if threshold <= 0:
-            return 0 # never reach the THRESHOLD_LIMIT
-        if threshold < 2:
-            threshold = 2
-        return (self.THRESHOLD_LIMIT // threshold) + 1
-        # the number is at least 1, and at most about half THRESHOLD_LIMIT
+        return self.warmrunnerdesc.jitcounter.compute_threshold(threshold)
 
     def set_param_threshold(self, threshold):
         self.increment_threshold = self._compute_threshold(threshold)
         self.increment_function_threshold = self._compute_threshold(threshold)
 
     def set_param_trace_eagerness(self, value):
-        self.trace_eagerness = value
+        self.increment_trace_eagerness = self._compute_threshold(value)
 
     def set_param_trace_limit(self, value):
         self.trace_limit = value
 
+    def set_param_decay(self, decay):
+        self.warmrunnerdesc.jitcounter.set_decay(decay)
+
     def set_param_inlining(self, value):
         self.inlining = value
 
                 self.warmrunnerdesc.memory_manager.max_unroll_loops = value
 
     def disable_noninlinable_function(self, greenkey):
-        cell = self.jit_cell_at_key(greenkey)
-        cell.dont_trace_here = True
+        cell = self.JitCell.ensure_jit_cell_at_key(greenkey)
+        cell.flags |= JC_DONT_TRACE_HERE
         debug_start("jit-disableinlining")
         loc = self.get_location_str(greenkey)
         debug_print("disabled inlining", loc)
         debug_stop("jit-disableinlining")
 
     def attach_procedure_to_interp(self, greenkey, procedure_token):
-        cell = self.jit_cell_at_key(greenkey)
+        cell = self.JitCell.ensure_jit_cell_at_key(greenkey)
         old_token = cell.get_procedure_token()
         cell.set_procedure_token(procedure_token)
-        cell.counter = -1       # valid procedure bridge attached
         if old_token is not None:
             self.cpu.redirect_call_assembler(old_token, procedure_token)
             # procedure_token is also kept alive by any loop that used
         vinfo = jitdriver_sd.virtualizable_info
         index_of_virtualizable = jitdriver_sd.index_of_virtualizable
         num_green_args = jitdriver_sd.num_green_args
-        get_jitcell = self.make_jitcell_getter()
+        JitCell = self.make_jitcell_subclass()
         self.make_jitdriver_callbacks()
         confirm_enter_jit = self.confirm_enter_jit
         range_red_args = unrolling_iterable(
                 assert 0, kind
         func_execute_token = self.cpu.make_execute_token(*ARGS)
         cpu = self.cpu
+        jitcounter = self.warmrunnerdesc.jitcounter
 
         def execute_assembler(loop_token, *args):
             # Call the backend to run the 'looptoken' with the given
             #
             assert 0, "should have raised"
 
-        def bound_reached(cell, *args):
-            # bound reached, but we do a last check: if it is the first
-            # time we reach the bound, or if another loop or bridge was
-            # compiled since the last time we reached it, then decrease
-            # the counter by a few percents instead.  It should avoid
-            # sudden bursts of JIT-compilation, and also corner cases
-            # where we suddenly compile more than one loop because all
-            # counters reach the bound at the same time, but where
-            # compiling all but the first one is pointless.
-            curgen = warmrunnerdesc.memory_manager.current_generation
-            curgen = chr(intmask(curgen) & 0xFF)    # only use 8 bits
-            if we_are_translated() and curgen != cell.extra_delay:
-                cell.counter = int(self.THRESHOLD_LIMIT * 0.98)
-                cell.extra_delay = curgen
+        def bound_reached(index, cell, *args):
+            if not confirm_enter_jit(*args):
                 return
-            #
-            if not confirm_enter_jit(*args):
-                cell.counter = 0
-                return
+            jitcounter.decay_all_counters()
             # start tracing
             from rpython.jit.metainterp.pyjitpl import MetaInterp
             metainterp = MetaInterp(metainterp_sd, jitdriver_sd)
-            # set counter to -2, to mean "tracing in effect"
-            cell.counter = -2
+            greenargs = args[:num_green_args]
+            if cell is None:
+                cell = JitCell(*greenargs)
+                jitcounter.install_new_cell(index, cell)
+            cell.flags |= JC_TRACING
             try:
                 metainterp.compile_and_run_once(jitdriver_sd, *args)
             finally:
-                if cell.counter == -2:
-                    cell.counter = 0
+                cell.flags &= ~JC_TRACING
 
-        def maybe_compile_and_run(threshold, *args):
+        def maybe_compile_and_run(increment_threshold, *args):
             """Entry point to the JIT.  Called at the point with the
             can_enter_jit() hint.
             """
-            # look for the cell corresponding to the current greenargs
+            # Look for the cell corresponding to the current greenargs.
+            # Search for the JitCell that is of the correct subclass of
+            # BaseJitCell, and that stores a key that compares equal.
+            # These few lines inline some logic that is also on the
+            # JitCell class, to avoid computing the hash several times.
             greenargs = args[:num_green_args]
-            cell = get_jitcell(True, *greenargs)
+            index = JitCell.get_index(*greenargs)
+            cell = jitcounter.lookup_chain(index)
+            while cell is not None:
+                if isinstance(cell, JitCell) and cell.comparekey(*greenargs):
+                    break    # found
+                cell = cell.next
+            else:
+                # not found. increment the counter
+                if jitcounter.tick(index, increment_threshold):
+                    bound_reached(index, None, *args)
+                return
 
-            if cell.counter >= 0:
-                # update the profiling counter
-                n = cell.counter + threshold
-                if n <= self.THRESHOLD_LIMIT:       # bound not reached
-                    cell.counter = n
-                    return
-                else:
-                    bound_reached(cell, *args)
-                    return
-            else:
-                if cell.counter != -1:
-                    assert cell.counter == -2
+            # Here, we have found 'cell'.
+            #
+            if cell.flags & (JC_TRACING | JC_TEMPORARY):
+                if cell.flags & JC_TRACING:
                     # tracing already happening in some outer invocation of
                     # this function. don't trace a second time.
                     return
-                if not confirm_enter_jit(*args):
-                    return
-                # machine code was already compiled for these greenargs
-                procedure_token = cell.get_procedure_token()
-                if procedure_token is None:   # it was a weakref that has been freed
-                    cell.counter = 0
-                    return
-                # extract and unspecialize the red arguments to pass to
-                # the assembler
-                execute_args = ()
-                for i in range_red_args:
-                    execute_args += (unspecialize_value(args[i]), )
-                # run it!  this executes until interrupted by an exception
-                execute_assembler(procedure_token, *execute_args)
-            #
+                # attached by compile_tmp_callback().  count normally
+                if jitcounter.tick(index, increment_threshold):
+                    bound_reached(index, cell, *args)
+                return
+            # machine code was already compiled for these greenargs
+            procedure_token = cell.get_procedure_token()
+            if procedure_token is None:
+                # it was an aborted compilation, or maybe a weakref that
+                # has been freed
+                jitcounter.cleanup_chain(index)
+                return
+            if not confirm_enter_jit(*args):
+                return
+            # extract and unspecialize the red arguments to pass to
+            # the assembler
+            execute_args = ()
+            for i in range_red_args:
+                execute_args += (unspecialize_value(args[i]), )
+            # run it!  this executes until interrupted by an exception
+            execute_assembler(procedure_token, *execute_args)
             assert 0, "should not reach this point"
 
         maybe_compile_and_run._dont_inline_ = True
 
     # ----------
 
-    def make_jitcell_getter(self):
+    def make_jitcell_subclass(self):
         "NOT_RPYTHON"
-        if hasattr(self, 'jit_getter'):
-            return self.jit_getter
+        if hasattr(self, 'JitCell'):
+            return self.JitCell
         #
-        if self.jitdriver_sd._get_jitcell_at_ptr is None:
-            jit_getter = self._make_jitcell_getter_default()
-        else:
-            jit_getter = self._make_jitcell_getter_custom()
+        jitcounter = self.warmrunnerdesc.jitcounter
+        jitdriver_sd = self.jitdriver_sd
+        green_args_name_spec = unrolling_iterable([('g%d' % i, TYPE)
+                     for i, TYPE in enumerate(jitdriver_sd._green_args_spec)])
+        unwrap_greenkey = self.make_unwrap_greenkey()
+        random_initial_value = hash(self)
         #
-        unwrap_greenkey = self.make_unwrap_greenkey()
+        class JitCell(BaseJitCell):
+            def __init__(self, *greenargs):
+                i = 0
+                for attrname, _ in green_args_name_spec:
+                    setattr(self, attrname, greenargs[i])
+                    i = i + 1
+
+            def comparekey(self, *greenargs2):
+                i = 0
+                for attrname, TYPE in green_args_name_spec:
+                    item1 = getattr(self, attrname)
+                    if not equal_whatever(TYPE, item1, greenargs2[i]):
+                        return False
+                    i = i + 1
+                return True
+
+            @staticmethod
+            def get_index(*greenargs):
+                x = random_initial_value
+                i = 0
+                for _, TYPE in green_args_name_spec:
+                    item = greenargs[i]
+                    y = hash_whatever(TYPE, item)
+                    x = intmask((x ^ y) * 1405695061)  # prime number, 2**30~31
+                    i = i + 1
+                return jitcounter.get_index(x)
+
+            @staticmethod
+            def get_jitcell(*greenargs):
+                index = JitCell.get_index(*greenargs)
+                cell = jitcounter.lookup_chain(index)
+                while cell is not None:
+                    if (isinstance(cell, JitCell) and
+                            cell.comparekey(*greenargs)):
+                        return cell
+                    cell = cell.next
+                return None
+
+            @staticmethod
+            def get_jit_cell_at_key(greenkey):
+                greenargs = unwrap_greenkey(greenkey)
+                return JitCell.get_jitcell(*greenargs)
+
+            @staticmethod
+            def ensure_jit_cell_at_key(greenkey):
+                greenargs = unwrap_greenkey(greenkey)
+                index = JitCell.get_index(*greenargs)
+                cell = jitcounter.lookup_chain(index)
+                while cell is not None:
+                    if (isinstance(cell, JitCell) and
+                            cell.comparekey(*greenargs)):
+                        return cell
+                    cell = cell.next
+                newcell = JitCell(*greenargs)
+                jitcounter.install_new_cell(index, newcell)
+                return newcell
         #
-        def jit_cell_at_key(greenkey):
-            greenargs = unwrap_greenkey(greenkey)
-            return jit_getter(True, *greenargs)
-        self.jit_cell_at_key = jit_cell_at_key
-        self.jit_getter = jit_getter
-        #
-        return jit_getter
-
-    def _make_jitcell_getter_default(self):
-        "NOT_RPYTHON"
-        jitdriver_sd = self.jitdriver_sd
-        green_args_spec = unrolling_iterable(jitdriver_sd._green_args_spec)
-        #
-        def comparekey(greenargs1, greenargs2):
-            i = 0
-            for TYPE in green_args_spec:
-                if not equal_whatever(TYPE, greenargs1[i], greenargs2[i]):
-                    return False
-                i = i + 1
-            return True
-        #
-        def hashkey(greenargs):
-            x = 0x345678
-            i = 0
-            for TYPE in green_args_spec:
-                item = greenargs[i]
-                y = hash_whatever(TYPE, item)
-                x = intmask((1000003 * x) ^ y)
-                i = i + 1
-            return x
-        #
-        jitcell_dict = r_dict(comparekey, hashkey)
-        try:
-            self.warmrunnerdesc.stats.jitcell_dicts.append(jitcell_dict)
-        except AttributeError:
-            pass
-        #
-        def _cleanup_dict():
-            minimum = self.THRESHOLD_LIMIT // 20     # minimum 5%
-            killme = []
-            for key, cell in jitcell_dict.iteritems():
-                if cell.counter >= 0:
-                    cell.counter = int(cell.counter * 0.92)
-                    if cell.counter < minimum:
-                        killme.append(key)
-                elif (cell.counter == -1
-                      and cell.get_procedure_token() is None):
-                    killme.append(key)
-            for key in killme:
-                del jitcell_dict[key]
-        #
-        def _maybe_cleanup_dict():
-            # Once in a while, rarely, when too many entries have
-            # been put in the jitdict_dict, we do a cleanup phase:
-            # we decay all counters and kill entries with a too
-            # low counter.
-            self._trigger_automatic_cleanup += 1
-            if self._trigger_automatic_cleanup > 20000:
-                self._trigger_automatic_cleanup = 0
-                _cleanup_dict()
-        #
-        self._trigger_automatic_cleanup = 0
-        self._jitcell_dict = jitcell_dict       # for tests
-        #
-        def get_jitcell(build, *greenargs):
-            try:
-                cell = jitcell_dict[greenargs]
-            except KeyError:
-                if not build:
-                    return None
-                _maybe_cleanup_dict()
-                cell = JitCell()
-                jitcell_dict[greenargs] = cell
-            return cell
-        return get_jitcell
-
-    def _make_jitcell_getter_custom(self):
-        "NOT_RPYTHON"
-        rtyper = self.warmrunnerdesc.rtyper
-        get_jitcell_at_ptr = self.jitdriver_sd._get_jitcell_at_ptr
-        set_jitcell_at_ptr = self.jitdriver_sd._set_jitcell_at_ptr
-        lltohlhack = {}
-        # note that there is no equivalent of _maybe_cleanup_dict()
-        # in the case of custom getters.  We assume that the interpreter
-        # stores the JitCells on some objects that can go away by GC,
-        # like the PyCode objects in PyPy.
-        #
-        def get_jitcell(build, *greenargs):
-            fn = support.maybe_on_top_of_llinterp(rtyper, get_jitcell_at_ptr)
-            cellref = fn(*greenargs)
-            # <hacks>
-            if we_are_translated():
-                BASEJITCELL = lltype.typeOf(cellref)
-                cell = cast_base_ptr_to_instance(JitCell, cellref)
-            else:
-                if isinstance(cellref, (BaseJitCell, type(None))):
-                    BASEJITCELL = None
-                    cell = cellref
-                else:
-                    BASEJITCELL = lltype.typeOf(cellref)
-                    if cellref:
-                        cell = lltohlhack[rtyper.type_system.deref(cellref)]
-                    else:
-                        cell = None
-            if not build:
-                return cell
-            if cell is None:
-                cell = JitCell()
-                # <hacks>
-                if we_are_translated():
-                    cellref = cast_object_to_ptr(BASEJITCELL, cell)
-                else:
-                    if BASEJITCELL is None:
-                        cellref = cell
-                    else:
-                        if isinstance(BASEJITCELL, lltype.Ptr):
-                            cellref = lltype.malloc(BASEJITCELL.TO)
-                        else:
-                            assert False, "no clue"
-                        lltohlhack[rtyper.type_system.deref(cellref)] = cell
-                # </hacks>
-                fn = support.maybe_on_top_of_llinterp(rtyper,
-                                                      set_jitcell_at_ptr)
-                fn(cellref, *greenargs)
-            return cell
-        return get_jitcell
+        self.JitCell = JitCell
+        return JitCell
 
     # ----------
 
         #
         warmrunnerdesc = self.warmrunnerdesc
         unwrap_greenkey = self.make_unwrap_greenkey()
-        jit_getter = self.make_jitcell_getter()
+        JitCell = self.make_jitcell_subclass()
         jd = self.jitdriver_sd
         cpu = self.cpu
 
         def can_inline_greenargs(*greenargs):
             if can_never_inline(*greenargs):
                 return False
-            cell = jit_getter(False, *greenargs)
-            if cell is not None and cell.dont_trace_here:
+            cell = JitCell.get_jitcell(*greenargs)
+            if cell is not None and (cell.flags & JC_DONT_TRACE_HERE) != 0:
                 return False
             return True
         def can_inline_callable(greenkey):
         redargtypes = ''.join([kind[0] for kind in jd.red_args_types])
 
         def get_assembler_token(greenkey):
-            cell = self.jit_cell_at_key(greenkey)
+            cell = JitCell.ensure_jit_cell_at_key(greenkey)
             procedure_token = cell.get_procedure_token()
             if procedure_token is None:
                 from rpython.jit.metainterp.compile import compile_tmp_callback
-                if cell.counter == -1:    # used to be a valid entry bridge,
-                    cell.counter = 0      # but was freed in the meantime.
                 memmgr = warmrunnerdesc.memory_manager
                 procedure_token = compile_tmp_callback(cpu, jd, greenkey,
                                                        redargtypes, memmgr)
-                cell.set_procedure_token(procedure_token)
+                cell.set_procedure_token(procedure_token, tmp=True)
             return procedure_token
         self.get_assembler_token = get_assembler_token
 

File rpython/memory/gc/incminimark.py

View file
                     self.get_total_memory_used())
         if self.DEBUG >= 2:
             self.debug_check_consistency()     # expensive!
+        #
+        self.root_walker.finished_minor_collection()
+        #
         debug_stop("gc-minor")
 
 

File rpython/memory/gc/test/test_direct.py

View file
     def _walk_prebuilt_gc(self, callback):
         pass
 
+    def finished_minor_collection(self):
+        pass
+
 
 class BaseDirectGCTest(object):
     GC_PARAMS = {}

File rpython/memory/gctransform/framework.py

View file
 
         if hasattr(translator, '_jit2gc'):
             self.layoutbuilder = translator._jit2gc['layoutbuilder']
+            finished_minor_collection = translator._jit2gc.get(
+                'invoke_after_minor_collection', None)
         else:
             self.layoutbuilder = TransformerLayoutBuilder(translator, GCClass)
+            finished_minor_collection = None
         self.layoutbuilder.transformer = self
         self.get_type_id = self.layoutbuilder.get_type_id
 
 
         gcdata.gc = GCClass(translator.config.translation, **GC_PARAMS)
         root_walker = self.build_root_walker()
+        root_walker.finished_minor_collection_func = finished_minor_collection
         self.root_walker = root_walker
         gcdata.set_query_functions(gcdata.gc)
         gcdata.gc.set_root_walker(root_walker)
 
 class BaseRootWalker(object):
     thread_setup = None
+    finished_minor_collection_func = None
 
     def __init__(self, gctransformer):
         self.gcdata = gctransformer.gcdata
         if collect_stack_root:
             self.walk_stack_roots(collect_stack_root)     # abstract
 
+    def finished_minor_collection(self):
+        func = self.finished_minor_collection_func
+        if func is not None:
+            func()
+
     def need_stacklet_support(self):
         raise Exception("%s does not support stacklets" % (
             self.__class__.__name__,))

File rpython/memory/gcwrapper.py

View file
         for obj in self.gcheap._all_prebuilt_gc:
             collect(llmemory.cast_ptr_to_adr(obj._as_ptr()))
 
+    def finished_minor_collection(self):
+        pass
+
 
 class DirectRunLayoutBuilder(gctypelayout.TypeLayoutBuilder):
 

File rpython/memory/test/test_transformed_gc.py

View file
     taggedpointers = False
 
     def setup_class(cls):
+        cls.marker = lltype.malloc(rffi.CArray(lltype.Signed), 1,
+                                   flavor='raw', zero=True)
         funcs0 = []
         funcs2 = []
         cleanups = []
     def ensure_layoutbuilder(cls, translator):
         jit2gc = getattr(translator, '_jit2gc', None)
         if jit2gc:
+            assert 'invoke_after_minor_collection' in jit2gc
             return jit2gc['layoutbuilder']
+        marker = cls.marker
         GCClass = cls.gcpolicy.transformerclass.GCClass
         layoutbuilder = framework.TransformerLayoutBuilder(translator, GCClass)
         layoutbuilder.delay_encoding()
+
+        def seeme():
+            marker[0] += 1
         translator._jit2gc = {
             'layoutbuilder': layoutbuilder,
+            'invoke_after_minor_collection': seeme,
         }
         return layoutbuilder
 
                 g()
                 i += 1
             return 0
+
+        if cls.gcname == 'incminimark':
+            marker = cls.marker
+            def cleanup():
+                assert marker[0] > 0
+                marker[0] = 0
+        else:
+            cleanup = None
+
         def fix_graph_of_g(translator):
             from rpython.translator.translator import graphof
             from rpython.flowspace.model import Constant
                     break
             else:
                 assert 0, "oups, not found"
-        return f, None, fix_graph_of_g
+        return f, cleanup, fix_graph_of_g
 
     def test_do_malloc_operations(self):
         run = self.runner("do_malloc_operations")

File rpython/rlib/jit.py

View file
     'threshold': 'number of times a loop has to run for it to become hot',
     'function_threshold': 'number of times a function must run for it to become traced from start',
     'trace_eagerness': 'number of times a guard has to fail before we start compiling a bridge',
+    'decay': 'amount to regularly decay counters by (0=none, 1000=max)',
     'trace_limit': 'number of recorded operations before we abort tracing with ABORT_TOO_LONG',
     'inlining': 'inline python functions or not (1/0)',
     'loop_longevity': 'a parameter controlling how long loops will be kept before being freed, an estimate',
 PARAMETERS = {'threshold': 1039, # just above 1024, prime
               'function_threshold': 1619, # slightly more than one above, also prime
               'trace_eagerness': 200,
+              'decay': 40,
               'trace_limit': 6000,
               'inlining': 1,
               'loop_longevity': 1000,
                                   if '.' not in name])
         self._heuristic_order = {}   # check if 'reds' and 'greens' are ordered
         self._make_extregistryentries()
-        self.get_jitcell_at = get_jitcell_at
-        self.set_jitcell_at = set_jitcell_at
+        assert get_jitcell_at is None, "get_jitcell_at no longer used"
+        assert set_jitcell_at is None, "set_jitcell_at no longer used"
         self.get_printable_location = get_printable_location
         self.confirm_enter_jit = confirm_enter_jit
         self.can_never_inline = can_never_inline
 #
 # Annotation and rtyping of some of the JitDriver methods
 
-class BaseJitCell(object):
-    __slots__ = ()
-
 
 class ExtEnterLeaveMarker(ExtRegistryEntry):
     # Replace a call to myjitdriver.jit_merge_point(**livevars)
 
     def annotate_hooks(self, **kwds_s):
         driver = self.instance.im_self
-        s_jitcell = self.bookkeeper.valueoftype(BaseJitCell)
         h = self.annotate_hook
-        h(driver.get_jitcell_at, driver.greens, **kwds_s)
-        h(driver.set_jitcell_at, driver.greens, [s_jitcell], **kwds_s)
         h(driver.get_printable_location, driver.greens, **kwds_s)
 
     def annotate_hook(self, func, variables, args_s=[], **kwds_s):