Author: Armin Rigo <[email protected]>
Branch: array-overallocation-in-nursery
Changeset: r67524:6535af3b2988
Date: 2013-10-23 06:52 +0200
http://bitbucket.org/pypy/pypy/changeset/6535af3b2988/
Log: 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).
diff --git a/rpython/annotator/unaryop.py b/rpython/annotator/unaryop.py
--- a/rpython/annotator/unaryop.py
+++ b/rpython/annotator/unaryop.py
@@ -303,20 +303,6 @@
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()
diff --git a/rpython/rlib/objectmodel.py b/rpython/rlib/objectmodel.py
--- a/rpython/rlib/objectmodel.py
+++ b/rpython/rlib/objectmodel.py
@@ -375,6 +375,47 @@
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
diff --git a/rpython/rlib/test/test_objectmodel.py
b/rpython/rlib/test/test_objectmodel.py
--- a/rpython/rlib/test/test_objectmodel.py
+++ b/rpython/rlib/test/test_objectmodel.py
@@ -549,6 +549,27 @@
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
diff --git a/rpython/rtyper/lltypesystem/rlist.py
b/rpython/rtyper/lltypesystem/rlist.py
--- a/rpython/rtyper/lltypesystem/rlist.py
+++ b/rpython/rtyper/lltypesystem/rlist.py
@@ -116,34 +116,6 @@
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):
@@ -401,26 +373,6 @@
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.
diff --git a/rpython/rtyper/rlist.py b/rpython/rtyper/rlist.py
--- a/rpython/rtyper/rlist.py
+++ b/rpython/rtyper/rlist.py
@@ -489,6 +489,11 @@
i += 1
return l
[email protected]("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):
diff --git a/rpython/translator/simplify.py b/rpython/translator/simplify.py
--- a/rpython/translator/simplify.py
+++ b/rpython/translator/simplify.py
@@ -617,16 +617,18 @@
# ____________________________________________________________
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
@@ -672,7 +674,7 @@
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):
@@ -805,6 +807,9 @@
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):
@@ -814,6 +819,56 @@
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:
@@ -912,6 +967,19 @@
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:
@@ -919,8 +987,8 @@
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
@@ -930,34 +998,33 @@
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!
diff --git a/rpython/translator/test/test_simplify.py
b/rpython/translator/test/test_simplify.py
--- a/rpython/translator/test/test_simplify.py
+++ b/rpython/translator/test/test_simplify.py
@@ -244,13 +244,11 @@
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):
@@ -264,12 +262,10 @@
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):
@@ -281,13 +277,12 @@
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):
@@ -302,12 +297,10 @@
return new_l
self.check(f, {
- 'hint': 2,
- 'newlist': 1,
'iter': 1,
'next': 1,
- 'getattr': 1,
- 'simple_call': 3,
+ 'getattr': 3,
+ 'simple_call': 6,
})
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
