Commits

Armin Rigo committed 6535af3

Change the list comprehension optimization to not depend on
lltypesystem/rlist.py any more (in particular, we want here
to remove the fact that fixed-size and var-size lists share
the GcArray part).

Comments (0)

Files changed (7)

rpython/annotator/unaryop.py

         return s_Bool
     op_contains.can_only_throw = []
 
-    def hint(lst, *args_s):
-        hints = args_s[-1].const
-        if 'maxlength' in hints:
-            # only for iteration over lists or dicts at the moment,
-            # not over an iterator object (because it has no known length)
-            s_iterable = args_s[0]
-            if isinstance(s_iterable, (SomeList, SomeDict)):
-                lst = SomeList(lst.listdef) # create a fresh copy
-                lst.listdef.resize()
-                lst.listdef.listitem.hint_maxlength = True
-        elif 'fence' in hints:
-            lst = lst.listdef.offspring()
-        return lst
-
     def getslice(lst, s_start, s_stop):
         check_negative_slice(s_start, s_stop)
         return lst.listdef.offspring()

rpython/rlib/objectmodel.py

         hop.exception_is_here()
         hop.gendirectcall(r_list.LIST._ll_resize_hint, v_list, v_sizehint)
 
+def newlist_fixed(length):
+    """Create a new fixed-size list of the given length.  The elements
+    are initialized with 0/None/whatever."""
+    return [None] * length    # xxx when not translated, assume list of objects
+
+class Entry(ExtRegistryEntry):
+    _about_ = newlist_fixed
+
+    def compute_result_annotation(self, s_length):
+        from rpython.annotator import model as annmodel
+        assert isinstance(s_length, annmodel.SomeInteger)
+        return self.bookkeeper.newlist()
+
+    def specialize_call(self, hop):
+        from rpython.rtyper.lltypesystem import lltype
+        from rpython.rtyper.rlist import ll_newlist_fixed
+        r_list = hop.r_result
+        v_count, = hop.inputargs(lltype.Signed)
+        cLIST = hop.inputconst(lltype.Void, r_list.LIST)
+        hop.exception_cannot_occur()
+        return hop.gendirectcall(ll_newlist_fixed, cLIST, v_count)
+
+def _is_list_or_dict(x):
+    return isinstance(x, (list, dict))
+
+class Entry(ExtRegistryEntry):
+    _about_ = _is_list_or_dict
+
+    def compute_result_annotation(self, s_x):
+        from rpython.annotator import model as annmodel
+        if annmodel.s_None.contains(s_x):
+            return annmodel.s_ImpossibleValue
+        s = annmodel.SomeBool()
+        s.const = (isinstance(s_x, annmodel.SomeList) or
+                   isinstance(s_x, annmodel.SomeDict))
+        return s
+
+    def specialize_call(self, hop):
+        hop.exception_cannot_occur()
+        return hop.inputconst(hop.r_result.lowleveltype, hop.s_result.const)
+
 # ____________________________________________________________
 #
 # id-like functions.  The idea is that calling hash() or id() is not

rpython/rlib/test/test_objectmodel.py

     r = interpret(f, [29])
     assert r == 1
 
+def test_newlist_fixed():
+    def f(i):
+        l = newlist_fixed(i)
+        return len(l)
+
+    r = interpret(f, [5])
+    assert r == 5
+
+def test_is_list_or_dict():
+    from rpython.rlib.objectmodel import _is_list_or_dict
+    #
+    def f(x):
+        return _is_list_or_dict(x)
+    r = interpret(f, [5])
+    assert r is False
+    #
+    def f(x):
+        return _is_list_or_dict([x])
+    r = interpret(f, [5])
+    assert r is True
+
 def test_import_from_mixin():
     class M:    # old-style
         def f(self): pass

rpython/rtyper/lltypesystem/rlist.py

         result.items = malloc(self.LIST.items.TO, n)
         return result
 
-    def rtype_method_append(self, hop):
-        if getattr(self.listitem, 'hint_maxlength', False):
-            v_lst, v_value = hop.inputargs(self, self.item_repr)
-            hop.exception_cannot_occur()
-            hop.gendirectcall(ll_append_noresize, v_lst, v_value)
-        else:
-            AbstractListRepr.rtype_method_append(self, hop)
-
-    def rtype_hint(self, hop):
-        optimized = getattr(self.listitem, 'hint_maxlength', False)
-        hints = hop.args_s[-1].const
-        if 'maxlength' in hints:
-            if optimized:
-                v_list = hop.inputarg(self, arg=0)
-                v_maxlength = self._get_v_maxlength(hop)
-                hop.llops.gendirectcall(ll_set_maxlength, v_list, v_maxlength)
-                return v_list
-        if 'fence' in hints:
-            v_list = hop.inputarg(self, arg=0)
-            if isinstance(hop.r_result, FixedSizeListRepr):
-                if optimized and 'exactlength' in hints:
-                    llfn = ll_list2fixed_exact
-                else:
-                    llfn = ll_list2fixed
-                v_list = hop.llops.gendirectcall(llfn, v_list)
-            return v_list
-        return AbstractListRepr.rtype_hint(self, hop)
-
 
 class FixedSizeListRepr(AbstractFixedSizeListRepr, BaseListRepr):
 
         llops.gendirectcall(ll_setitem_nonneg, v_func, v_result, ci, v_item)
     return v_result
 
-# special operations for list comprehension optimization
-def ll_set_maxlength(l, n):
-    LIST = typeOf(l).TO
-    l.items = malloc(LIST.items.TO, n)
-
-def ll_list2fixed(l):
-    n = l.length
-    olditems = l.items
-    if n == len(olditems):
-        return olditems
-    else:
-        LIST = typeOf(l).TO
-        newitems = malloc(LIST.items.TO, n)
-        rgc.ll_arraycopy(olditems, newitems, 0, 0, n)
-        return newitems
-
-def ll_list2fixed_exact(l):
-    ll_assert(l.length == len(l.items), "ll_list2fixed_exact: bad length")
-    return l.items
-
 # ____________________________________________________________
 #
 #  Iteration.

rpython/rtyper/rlist.py

             i += 1
     return l
 
+@jit.oopspec("newlist(count)")
+def ll_newlist_fixed(LIST, count):
+    # called by rtyping of objectmodel.newlist_fixed()
+    return LIST.ll_newlist(count)
+
 
 # return a nullptr() if lst is a list of pointers it, else None.
 def ll_null_item(lst):

rpython/translator/simplify.py

 # ____________________________________________________________
 
 def detect_list_comprehension(graph):
-    """Look for the pattern:            Replace it with marker operations:
+    """Look for the pattern:            Replace it with these operations:
 
-                                         v0 = newlist()
-        v2 = newlist()                   v1 = hint(v0, iterable, {'maxlength'})
+        v2 = newlist()                   v1 = simple_call(RListCompr)
+        ...                              ...
+        v4 = iter(v3)                    v4 = iter(v3)
+                                         v1.setup(v3)   # initialize
         loop start                       loop start
         ...                              ...
         exactly one append per loop      v1.append(..)
         and nothing else done with v2
         ...                              ...
-        loop end                         v2 = hint(v1, {'fence'})
+        loop end                         v2 = v1.fence() or .fence_exact()
     """
     # NB. this assumes RPythonicity: we can only iterate over something
     # that has a len(), and this len() cannot change as long as we are
     if not newlist_v or not loops:
         return
 
-    # XXX works with Python >= 2.4 only: find calls to append encoded as
+    # find calls to append encoded as
     # getattr/simple_call pairs, as produced by the LIST_APPEND bytecode.
     for block in graph.iterblocks():
         for i in range(len(block.operations)-1):
         else:
             return None
 
+    def returns_vlist(self, v_result):
+        return self.variable_families.find_rep(v_result) is self.vlistfamily
+
     def remove_vlist(self, args):
         removed = 0
         for i in range(len(args)-1, -1, -1):
                 removed += 1
         assert removed == 1
 
+    def make_RListCompr_class(self):
+
+        class RListCompr(object):
+            """Class used temporarily for list comprehension, when the
+            list is being built.  In all cases, the instance should be
+            later killed by malloc removal."""
+
+            def setup(self, iterable):
+                # Only optimize iteration over lists or dicts, not over
+                # an iterator object (because it has no known length).
+                # In all cases, 'self.optimize' is an annotation-time
+                # constant.
+                from rpython.rlib import objectmodel
+                self.optimize = objectmodel._is_list_or_dict(iterable)
+                if self.optimize:
+                    self.fixed_list = objectmodel.newlist_fixed(len(iterable))
+                    self.position = 0
+                else:
+                    self.fallback_list = []
+            setup._always_inline_ = True
+
+            def append(self, item):
+                if self.optimize:
+                    p = self.position
+                    self.position = p + 1
+                    self.fixed_list[p] = item
+                else:
+                    self.fallback_list.append(item)
+            append._always_inline_ = True
+
+            def fence_exact(self):
+                if self.optimize:
+                    assert self.position == len(self.fixed_list)
+                    return self.fixed_list
+                else:
+                    return self.fallback_list[:]
+            fence_exact._always_inline_ = True
+
+            def fence(self):
+                if self.optimize:
+                    if self.position == len(self.fixed_list):
+                        return self.fixed_list
+                    else:
+                        return self.fixed_list[:self.position]
+                else:
+                    return self.fallback_list[:]
+            fence._always_inline_ = True
+
+        return RListCompr
+
     def run(self, vlist, vmeth, appendblock):
         # first check that the 'append' method object doesn't escape
         for op in appendblock.operations:
         for stopblock1 in stopblocks:
             assert stopblock1 not in loopbody
 
+        # Get a fresh copy of the RListCompr class
+        RListCompr = self.make_RListCompr_class()
+
+        # Replace the original newlist() with simple_call(RListCompr)
+        for op in newlistblock.operations:
+            if self.returns_vlist(op.result):
+                assert op.opname == 'newlist'
+                op.opname = 'simple_call'
+                op.args[:] = [Constant(RListCompr)]
+                break
+        else:
+            raise AssertionError("lost 'newlist' operation")
+
         # at StopIteration, the new list is exactly of the same length as
         # the one we iterate over if it's not possible to skip the appendblock
         # in the body:
                                                 avoid = appendblock,
                                                 stay_within = loopbody)
 
-        # - add a hint(vlist, iterable, {'maxlength'}) in the iterblock,
-        #   where we can compute the known maximum length
+        # - add a 'v2 = getattr(v, 'setup'); simple_call(v2, iterable)'
+        #   in the iterblock, where we can compute the known maximum length
         link = iterblock.exits[0]
         vlist = self.contains_vlist(link.args)
         assert vlist
                 break
         else:
             raise AssertionError("lost 'iter' operation")
-        vlist2 = Variable(vlist)
-        chint = Constant({'maxlength': True})
+        v_method = Variable()
+        v_none = Variable()
         iterblock.operations += [
-            SpaceOperation('hint', [vlist, op.args[0], chint], vlist2)]
-        link.args = list(link.args)
-        for i in range(len(link.args)):
-            if link.args[i] is vlist:
-                link.args[i] = vlist2
+            SpaceOperation('getattr', [vlist, Constant('setup')], v_method),
+            SpaceOperation('simple_call', [v_method, op.args[0]], v_none)]
 
-        # - wherever the list exits the loop body, add a 'hint({fence})'
+        # - wherever the list exits the loop body, add a '.fence()'
         for block in loopbody:
             for link in block.exits:
                 if link.target not in loopbody:
                     vlist = self.contains_vlist(link.args)
                     if vlist is None:
                         continue  # list not passed along this link anyway
-                    hints = {'fence': True}
+                    name = 'fence'
                     if (exactlength and block is loopnextblock and
                         link.target in stopblocks):
-                        hints['exactlength'] = True
-                    chints = Constant(hints)
+                        name = 'fence_exact'
+                    c_name = Constant(name)
                     newblock = unsimplify.insert_empty_block(None, link)
                     index = link.args.index(vlist)
                     vlist2 = newblock.inputargs[index]
                     vlist3 = Variable(vlist2)
                     newblock.inputargs[index] = vlist3
-                    newblock.operations.append(
-                        SpaceOperation('hint', [vlist3, chints], vlist2))
+                    v_method = Variable()
+                    newblock.operations.extend([
+                        SpaceOperation('getattr', [vlist3, c_name], v_method),
+                        SpaceOperation('simple_call', [v_method], vlist2)])
         # done!
 
 

rpython/translator/test/test_simplify.py

         def f1(l):
             return [x*17 for x in l]
         self.check(f1, {
-            'newlist': 1,
             'iter': 1,
             'next': 1,
             'mul':  1,
-            'getattr': 1,
-            'simple_call': 1,
-            'hint': 2,
+            'getattr': 3,       # setup, append, fence_exact
+            'simple_call': 4,   # RListCompr, setup, append, fence_exact
             })
 
     def test_with_exc(self):
             finally:
                 free_some_stuff()
         self.check(f1, {
-            'newlist': 1,
             'iter': 1,
             'next': 1,
-            'getattr': 1,
-            'simple_call': 4,
-            'hint': 2,
+            'getattr': 3,
+            'simple_call': 7,
             })
 
     def test_canraise_before_iter(self):
             except ValueError:
                 return []
         self.check(f1, {
-            'newlist': 2,
+            'newlist': 1,
             'iter': 1,
             'next': 1,
             'mul':  1,
-            'getattr': 1,
-            'simple_call': 2,
-            'hint': 2,
+            'getattr': 3,
+            'simple_call': 5,
             })
 
     def test_iterate_over_list(self):
             return new_l
 
         self.check(f, {
-            'hint': 2,
-            'newlist': 1,
             'iter': 1,
             'next': 1,
-            'getattr': 1,
-            'simple_call': 3,
+            'getattr': 3,
+            'simple_call': 6,
             })