Author: Squeaky <[email protected]>
Branch:
Changeset: r69685:4d70ac4b69b1
Date: 2014-03-04 18:47 +0100
http://bitbucket.org/pypy/pypy/changeset/4d70ac4b69b1/
Log: Implements SimpleRangeListStrategy for case range(n) where n is a
positive number.
diff --git a/pypy/doc/whatsnew-head.rst b/pypy/doc/whatsnew-head.rst
--- a/pypy/doc/whatsnew-head.rst
+++ b/pypy/doc/whatsnew-head.rst
@@ -94,3 +94,8 @@
.. branch: test-58c3d8552833
Fix for getarrayitem_gc_pure optimization
+
+.. branch: simple-range-strategy
+Implements SimpleRangeListStrategy for case range(n) where n is a positive
number.
+Makes some traces nicer by getting rid of multiplication for calculating loop
counter
+and propagates that n > 0 further to get rid of guards.
diff --git a/pypy/objspace/std/listobject.py b/pypy/objspace/std/listobject.py
--- a/pypy/objspace/std/listobject.py
+++ b/pypy/objspace/std/listobject.py
@@ -43,6 +43,10 @@
if length <= 0:
strategy = space.fromcache(EmptyListStrategy)
storage = strategy.erase(None)
+ elif start == 0 and step == 1:
+ strategy = space.fromcache(SimpleRangeListStrategy)
+ assert length > 0
+ storage = strategy.erase((length,))
else:
strategy = space.fromcache(RangeListStrategy)
storage = strategy.erase((start, step, length))
@@ -999,15 +1003,7 @@
self.sizehint = hint
-class RangeListStrategy(ListStrategy):
- """RangeListStrategy is used when a list is created using the range method.
- The storage is a tuple containing only three integers start, step and
- length and elements are calculated based on these values. On any operation
- destroying the range (inserting, appending non-ints) the strategy is
- switched to IntegerListStrategy."""
-
- _applevel_repr = "range"
-
+class BaseRangeListStrategy(ListStrategy):
def switch_to_integer_strategy(self, w_list):
items = self._getitems_range(w_list, False)
strategy = w_list.strategy = self.space.fromcache(IntegerListStrategy)
@@ -1022,10 +1018,6 @@
def init_from_list_w(self, w_list, list_w):
raise NotImplementedError
- erase, unerase = rerased.new_erasing_pair("range")
- erase = staticmethod(erase)
- unerase = staticmethod(unerase)
-
def clone(self, w_list):
storage = w_list.lstorage # lstorage is tuple, no need to clone
w_clone = W_ListObject.from_storage_and_strategy(self.space, storage,
@@ -1040,6 +1032,155 @@
w_other.strategy = self
w_other.lstorage = w_list.lstorage
+ def getitem(self, w_list, i):
+ return self.wrap(self._getitem_unwrapped(w_list, i))
+
+ def getitems_int(self, w_list):
+ return self._getitems_range(w_list, False)
+
+ def getitems_copy(self, w_list):
+ return self._getitems_range(w_list, True)
+
+ def getstorage_copy(self, w_list):
+ # tuple is immutable
+ return w_list.lstorage
+
+ @jit.dont_look_inside
+ def getitems_fixedsize(self, w_list):
+ return self._getitems_range_unroll(w_list, True)
+
+ def getitems_unroll(self, w_list):
+ return self._getitems_range_unroll(w_list, True)
+
+ def getslice(self, w_list, start, stop, step, length):
+ self.switch_to_integer_strategy(w_list)
+ return w_list.getslice(start, stop, step, length)
+
+ def append(self, w_list, w_item):
+ if type(w_item) is W_IntObject:
+ self.switch_to_integer_strategy(w_list)
+ else:
+ w_list.switch_to_object_strategy()
+ w_list.append(w_item)
+
+ def inplace_mul(self, w_list, times):
+ self.switch_to_integer_strategy(w_list)
+ w_list.inplace_mul(times)
+
+ def deleteslice(self, w_list, start, step, slicelength):
+ self.switch_to_integer_strategy(w_list)
+ w_list.deleteslice(start, step, slicelength)
+
+ def setitem(self, w_list, index, w_item):
+ self.switch_to_integer_strategy(w_list)
+ w_list.setitem(index, w_item)
+
+ def setslice(self, w_list, start, step, slicelength, sequence_w):
+ self.switch_to_integer_strategy(w_list)
+ w_list.setslice(start, step, slicelength, sequence_w)
+
+ def insert(self, w_list, index, w_item):
+ self.switch_to_integer_strategy(w_list)
+ w_list.insert(index, w_item)
+
+ def extend(self, w_list, w_any):
+ self.switch_to_integer_strategy(w_list)
+ w_list.extend(w_any)
+
+ def reverse(self, w_list):
+ self.switch_to_integer_strategy(w_list)
+ w_list.reverse()
+
+ def sort(self, w_list, reverse):
+ step = self.step(w_list)
+ if step > 0 and reverse or step < 0 and not reverse:
+ self.switch_to_integer_strategy(w_list)
+ w_list.sort(reverse)
+
+
+class SimpleRangeListStrategy(BaseRangeListStrategy):
+ """SimpleRangeListStrategy is used when a list is created using the range
+ method providing only positive length. The storage is a one element
tuple
+ with positive integer storing length."""
+
+ _applevel_repr = "simple_range"
+
+ erase, unerase = rerased.new_erasing_pair("simple_range")
+ erase = staticmethod(erase)
+ unerase = staticmethod(unerase)
+
+ def find(self, w_list, w_obj, startindex, stopindex):
+ if type(w_obj) is W_IntObject:
+ obj = self.unwrap(w_obj)
+ length = self.unerase(w_list.lstorage)[0]
+ if 0 <= obj < length and startindex <= obj < stopindex:
+ return obj
+ else:
+ raise ValueError
+ return ListStrategy.find(self, w_list, w_obj, startindex, stopindex)
+
+ def length(self, w_list):
+ return self.unerase(w_list.lstorage)[0]
+
+ def step(self, w_list):
+ return 1
+
+ def _getitem_unwrapped(self, w_list, i):
+ length = self.unerase(w_list.lstorage)[0]
+ assert length > 0
+ if 0 <= i < length:
+ return i
+ else:
+ raise IndexError
+
+ @specialize.arg(2)
+ def _getitems_range(self, w_list, wrap_items):
+ length = self.unerase(w_list.lstorage)[0]
+ if wrap_items:
+ r = [None] * length
+ else:
+ r = [0] * length
+ i = 0
+ while i < length:
+ if wrap_items:
+ r[i] = self.wrap(i)
+ else:
+ r[i] = i
+ i += 1
+
+ return r
+
+ _getitems_range_unroll = jit.unroll_safe(
+ func_with_new_name(_getitems_range, "_getitems_range_unroll"))
+
+ def pop_end(self, w_list):
+ new_length = self.unerase(w_list.lstorage)[0] - 1
+ w_result = self.wrap(new_length)
+ if new_length > 0:
+ w_list.lstorage = self.erase((new_length,))
+ else:
+ strategy = w_list.strategy =
self.space.fromcache(EmptyListStrategy)
+ w_list.lstorage = strategy.erase(None)
+ return w_result
+
+ def pop(self, w_list, index):
+ self.switch_to_integer_strategy(w_list)
+ return w_list.pop(index)
+
+
+class RangeListStrategy(BaseRangeListStrategy):
+ """RangeListStrategy is used when a list is created using the range method.
+ The storage is a tuple containing only three integers start, step and
+ length and elements are calculated based on these values. On any operation
+ destroying the range (inserting, appending non-ints) the strategy is
+ switched to IntegerListStrategy."""
+
+ _applevel_repr = "range"
+
+ erase, unerase = rerased.new_erasing_pair("range")
+ erase = staticmethod(erase)
+ unerase = staticmethod(unerase)
+
def find(self, w_list, w_obj, startindex, stopindex):
if type(w_obj) is W_IntObject:
obj = self.unwrap(w_obj)
@@ -1059,6 +1200,9 @@
def length(self, w_list):
return self.unerase(w_list.lstorage)[2]
+ def step(self, w_list):
+ return self.unerase(w_list.lstorage)[1]
+
def _getitem_unwrapped(self, w_list, i):
v = self.unerase(w_list.lstorage)
start = v[0]
@@ -1072,19 +1216,6 @@
raise IndexError
return start + i * step
- def getitems_int(self, w_list):
- return self._getitems_range(w_list, False)
-
- def getitem(self, w_list, i):
- return self.wrap(self._getitem_unwrapped(w_list, i))
-
- def getitems_copy(self, w_list):
- return self._getitems_range(w_list, True)
-
- def getstorage_copy(self, w_list):
- # tuple is unmutable
- return w_list.lstorage
-
@specialize.arg(2)
def _getitems_range(self, w_list, wrap_items):
l = self.unerase(w_list.lstorage)
@@ -1107,34 +1238,9 @@
return r
- @jit.dont_look_inside
- def getitems_fixedsize(self, w_list):
- return self._getitems_range_unroll(w_list, True)
-
- def getitems_unroll(self, w_list):
- return self._getitems_range_unroll(w_list, True)
_getitems_range_unroll = jit.unroll_safe(
func_with_new_name(_getitems_range, "_getitems_range_unroll"))
- def getslice(self, w_list, start, stop, step, length):
- self.switch_to_integer_strategy(w_list)
- return w_list.getslice(start, stop, step, length)
-
- def append(self, w_list, w_item):
- if type(w_item) is W_IntObject:
- self.switch_to_integer_strategy(w_list)
- else:
- w_list.switch_to_object_strategy()
- w_list.append(w_item)
-
- def inplace_mul(self, w_list, times):
- self.switch_to_integer_strategy(w_list)
- w_list.inplace_mul(times)
-
- def deleteslice(self, w_list, start, step, slicelength):
- self.switch_to_integer_strategy(w_list)
- w_list.deleteslice(start, step, slicelength)
-
def pop_end(self, w_list):
start, step, length = self.unerase(w_list.lstorage)
w_result = self.wrap(start + (length - 1) * step)
@@ -1158,32 +1264,6 @@
self.switch_to_integer_strategy(w_list)
return w_list.pop(index)
- def setitem(self, w_list, index, w_item):
- self.switch_to_integer_strategy(w_list)
- w_list.setitem(index, w_item)
-
- def setslice(self, w_list, start, step, slicelength, sequence_w):
- self.switch_to_integer_strategy(w_list)
- w_list.setslice(start, step, slicelength, sequence_w)
-
- def sort(self, w_list, reverse):
- step = self.unerase(w_list.lstorage)[1]
- if step > 0 and reverse or step < 0 and not reverse:
- self.switch_to_integer_strategy(w_list)
- w_list.sort(reverse)
-
- def insert(self, w_list, index, w_item):
- self.switch_to_integer_strategy(w_list)
- w_list.insert(index, w_item)
-
- def extend(self, w_list, w_any):
- self.switch_to_integer_strategy(w_list)
- w_list.extend(w_any)
-
- def reverse(self, w_list):
- self.switch_to_integer_strategy(w_list)
- w_list.reverse()
-
class AbstractUnwrappedStrategy(object):
@@ -1541,7 +1621,7 @@
_base_extend_from_list = _extend_from_list
def _extend_from_list(self, w_list, w_other):
- if w_other.strategy is self.space.fromcache(RangeListStrategy):
+ if isinstance(w_other.strategy, BaseRangeListStrategy):
l = self.unerase(w_list.lstorage)
other = w_other.getitems_int()
assert other is not None
diff --git a/pypy/objspace/std/test/test_liststrategies.py
b/pypy/objspace/std/test/test_liststrategies.py
--- a/pypy/objspace/std/test/test_liststrategies.py
+++ b/pypy/objspace/std/test/test_liststrategies.py
@@ -1,5 +1,8 @@
import sys
-from pypy.objspace.std.listobject import W_ListObject, EmptyListStrategy,
ObjectListStrategy, IntegerListStrategy, FloatListStrategy, BytesListStrategy,
RangeListStrategy, make_range_list, UnicodeListStrategy
+from pypy.objspace.std.listobject import (
+ W_ListObject, EmptyListStrategy, ObjectListStrategy, IntegerListStrategy,
+ FloatListStrategy, BytesListStrategy, RangeListStrategy,
+ SimpleRangeListStrategy, make_range_list, UnicodeListStrategy)
from pypy.objspace.std import listobject
from pypy.objspace.std.test.test_listobject import TestW_ListObject
@@ -18,7 +21,7 @@
UnicodeListStrategy)
assert isinstance(W_ListObject(space, [w(u'a'), w('b')]).strategy,
ObjectListStrategy) # mixed unicode and bytes
-
+
def test_empty_to_any(self):
space = self.space
w = space.wrap
@@ -183,7 +186,7 @@
def test_setslice(self):
space = self.space
w = space.wrap
-
+
l = W_ListObject(space, [])
assert isinstance(l.strategy, EmptyListStrategy)
l.setslice(0, 1, 2, W_ListObject(space, [w(1), w(2), w(3)]))
@@ -286,7 +289,7 @@
def test_empty_setslice_with_objectlist(self):
space = self.space
w = space.wrap
-
+
l = W_ListObject(space, [])
o = W_ListObject(space, [space.wrap(1), space.wrap("2"),
space.wrap(3)])
l.setslice(0, 1, o.length(), o)
@@ -347,6 +350,13 @@
empty = W_ListObject(space, [])
assert isinstance(empty.strategy, EmptyListStrategy)
+ r = make_range_list(space, 0, 1, 10)
+ empty.extend(r)
+ assert isinstance(empty.strategy, SimpleRangeListStrategy)
+ assert space.is_true(space.eq(empty.getitem(1), w(1)))
+
+ empty = W_ListObject(space, [])
+ assert isinstance(empty.strategy, EmptyListStrategy)
empty.extend(W_ListObject(space, [w(1), w(2), w(3)]))
assert isinstance(empty.strategy, IntegerListStrategy)
@@ -397,6 +407,72 @@
l.append(self.space.wrap(19))
assert isinstance(l.strategy, IntegerListStrategy)
+ def test_simplerangelist(self):
+ l = make_range_list(self.space, 0, 1, 10)
+ assert isinstance(l.strategy, SimpleRangeListStrategy)
+ v = l.pop(5)
+ assert self.space.eq_w(v, self.space.wrap(5))
+ assert isinstance(l.strategy, IntegerListStrategy)
+
+ l = make_range_list(self.space, 0, 1, 10)
+ assert isinstance(l.strategy, SimpleRangeListStrategy)
+ v = l.pop(0)
+ assert self.space.eq_w(v, self.space.wrap(0))
+ assert isinstance(l.strategy, IntegerListStrategy)
+
+ l = make_range_list(self.space, 0, 1, 10)
+ assert isinstance(l.strategy, SimpleRangeListStrategy)
+ v = l.pop_end()
+ assert self.space.eq_w(v, self.space.wrap(9))
+ assert isinstance(l.strategy, SimpleRangeListStrategy)
+ v = l.pop_end()
+ assert self.space.eq_w(v, self.space.wrap(8))
+ assert isinstance(l.strategy, SimpleRangeListStrategy)
+
+ l = make_range_list(self.space, 0, 1, 5)
+ assert isinstance(l.strategy, SimpleRangeListStrategy)
+ l.append(self.space.wrap("string"))
+ assert isinstance(l.strategy, ObjectListStrategy)
+
+ l = make_range_list(self.space, 0,1,5)
+ assert isinstance(l.strategy, SimpleRangeListStrategy)
+ l.append(self.space.wrap(19))
+ assert isinstance(l.strategy, IntegerListStrategy)
+
+ l = make_range_list(self.space, 0,1,5)
+ assert isinstance(l.strategy, SimpleRangeListStrategy)
+ assert l.find(self.space.wrap(0)) == 0
+ assert l.find(self.space.wrap(4)) == 4
+
+ try:
+ l.find(self.space.wrap(5))
+ except ValueError:
+ pass
+ else:
+ assert False, "Did not raise ValueError"
+
+ try:
+ l.find(self.space.wrap(0), 5, 6)
+ except ValueError:
+ pass
+ else:
+ assert False, "Did not raise ValueError"
+
+ assert l.length() == 5
+
+ l = make_range_list(self.space, 0, 1, 1)
+ assert self.space.eq_w(l.pop(0), self.space.wrap(0))
+
+ l = make_range_list(self.space, 0, 1, 10)
+ l.sort(False)
+ assert isinstance(l.strategy, SimpleRangeListStrategy)
+
+ assert self.space.eq_w(l.getitem(5), self.space.wrap(5))
+
+ l = make_range_list(self.space, 0, 1, 1)
+ assert self.space.eq_w(l.pop_end(), self.space.wrap(0))
+ assert isinstance(l.strategy, EmptyListStrategy)
+
def test_keep_range(self):
# simple list
l = make_range_list(self.space, 1,1,5)
diff --git a/pypy/objspace/std/test/test_rangeobject.py
b/pypy/objspace/std/test/test_rangeobject.py
--- a/pypy/objspace/std/test/test_rangeobject.py
+++ b/pypy/objspace/std/test/test_rangeobject.py
@@ -72,28 +72,43 @@
r.sort(key=lambda x: -x)
assert r == range(9, -1, -1)
def test_pop(self):
+ # RangeListStrategy
+ r = range(1, 10)
+ res = r.pop()
+ assert res == 9
+ assert self.not_forced(r)
+ assert repr(r) == repr(range(1, 9))
+ res = r.pop(0)
+ assert res == 1
+ assert self.not_forced(r)
+ assert repr(r) == repr(range(2, 9))
+ res = r.pop(len(r) - 1)
+ assert res == 8
+ assert self.not_forced(r)
+ assert repr(r) == repr(range(2, 8))
+ res = r.pop(2)
+ assert res == 4
+ assert not self.not_forced(r)
+ assert r == [2, 3, 5, 6, 7]
+ res = r.pop(2)
+ assert res == 5
+ assert not self.not_forced(r)
+ assert r == [2, 3, 6, 7]
+
+ # SimpleRangeListStrategy
r = range(10)
res = r.pop()
assert res == 9
assert self.not_forced(r)
- assert repr(r) == repr(range(9))
+ res = r.pop()
+ assert res == 8
+ assert repr(r) == repr(range(8))
+ assert self.not_forced(r)
res = r.pop(0)
assert res == 0
- assert self.not_forced(r)
- assert repr(r) == repr(range(1, 9))
- res = r.pop(len(r) - 1)
- assert res == 8
- assert self.not_forced(r)
- assert repr(r) == repr(range(1, 8))
- res = r.pop(2)
- assert res == 3
assert not self.not_forced(r)
- assert r == [1, 2, 4, 5, 6, 7]
- res = r.pop(2)
- assert res == 4
- assert not self.not_forced(r)
- assert r == [1, 2, 5, 6, 7]
-
+ assert r == [1, 2, 3, 4, 5, 6, 7]
+
def test_reduce(self):
it = iter(range(10))
assert it.next() == 0
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
