Commits

Maciej Fijalkowski  committed bed0162 Merge

(pjenvey, fijal reviewing) merge length-hint branch.

This branch brings __length_hint__ special method to PyPy implementing
PEP that number I don't memorize and I don't have internet.

  • Participants
  • Parent commits 74106f4, 3d0895a

Comments (0)

Files changed (30)

File pypy/interpreter/argument.py

File contents unchanged.

File pypy/interpreter/baseobjspace.py

         """
         # If we can guess the expected length we can preallocate.
         try:
-            lgt_estimate = self.len_w(w_iterable)
-        except OperationError, o:
-            if (not o.match(self, self.w_AttributeError) and
-                not o.match(self, self.w_TypeError)):
-                raise
-            items = []
-        else:
-            try:
-                items = newlist_hint(lgt_estimate)
-            except MemoryError:
-                items = [] # it might have lied
-        #
+            items = newlist_hint(self.length_hint(w_iterable, 0))
+        except MemoryError:
+            items = [] # it might have lied
+
         tp = self.type(w_iterator)
         while True:
             unpackiterable_driver.jit_merge_point(tp=tp,
         return self._unpackiterable_known_length_jitlook(w_iterator,
                                                          expected_length)
 
+    def length_hint(self, w_obj, default):
+        """Return the length of an object, consulting its __length_hint__
+        method if necessary.
+        """
+        try:
+            return self.len_w(w_obj)
+        except OperationError, e:
+            if not (e.match(self, self.w_TypeError) or
+                    e.match(self, self.w_AttributeError)):
+                raise
+
+        w_descr = self.lookup(w_obj, '__length_hint__')
+        if w_descr is None:
+            return default
+        try:
+            w_hint = self.get_and_call_function(w_descr, w_obj)
+        except OperationError, e:
+            if not (e.match(self, self.w_TypeError) or
+                    e.match(self, self.w_AttributeError)):
+                raise
+            return default
+        if self.is_w(w_hint, self.w_NotImplemented):
+            return default
+
+        hint = self.int_w(w_hint)
+        if hint < 0:
+            raise OperationError(self.w_ValueError, self.wrap(
+                    "__length_hint__() should return >= 0"))
+        return hint
+
     def fixedview(self, w_iterable, expected_length=-1):
         """ A fixed list view of w_iterable. Don't modify the result
         """
     def newlist_str(self, list_s):
         return self.newlist([self.wrap(s) for s in list_s])
 
+    def newlist_hint(self, sizehint):
+        from pypy.objspace.std.listobject import make_empty_list_with_size
+        return make_empty_list_with_size(self, sizehint)
+
     @jit.unroll_safe
     def exception_match(self, w_exc_type, w_check_class):
         """Checks if the given exception type matches 'w_check_class'."""

File pypy/interpreter/test/test_argument.py

File contents unchanged.

File pypy/module/__builtin__/app_functional.py

 Plain Python definition of the builtin functions oriented towards
 functional programming.
 """
+from __future__ import with_statement
+import operator
+from __pypy__ import resizelist_hint, newlist_hint
 
 # ____________________________________________________________
 
     if num_collections == 1:
         if none_func:
             return list(collections[0])
-        else:
-            # Special case for the really common case of a single collection,
-            # this can be eliminated if we could unroll that loop that creates
-            # `args` based on whether or not len(collections) was constant
-            result = []
-            for item in collections[0]:
+        # Special case for the really common case of a single collection,
+        # this can be eliminated if we could unroll that loop that creates
+        # `args` based on whether or not len(collections) was constant
+        seq = collections[0]
+        with _ManagedNewlistHint(operator._length_hint(seq, 0)) as result:
+            for item in seq:
                 result.append(func(item))
             return result
-    result = []
-    # Pair of (iterator, has_finished)
-    iterators = [(iter(seq), False) for seq in collections]
-    while True:
-        cont = False
-        args = []
-        for idx, (iterator, has_finished) in enumerate(iterators):
-            val = None
-            if not has_finished:
-                try:
-                    val = next(iterator)
-                except StopIteration:
-                    iterators[idx] = (None, True)
+
+    # Gather the iterators (pair of (iter, has_finished)) and guess the
+    # result length (the max of the input lengths)
+    iterators = []
+    max_hint = 0
+    for seq in collections:
+        iterators.append((iter(seq), False))
+        max_hint = max(max_hint, operator._length_hint(seq, 0))
+
+    with _ManagedNewlistHint(max_hint) as result:
+        while True:
+            cont = False
+            args = []
+            for idx, (iterator, has_finished) in enumerate(iterators):
+                val = None
+                if not has_finished:
+                    try:
+                        val = next(iterator)
+                    except StopIteration:
+                        iterators[idx] = (None, True)
+                    else:
+                        cont = True
+                args.append(val)
+            args = tuple(args)
+            if cont:
+                if none_func:
+                    result.append(args)
                 else:
-                    cont = True
-            args.append(val)
-        args = tuple(args)
-        if cont:
-            if none_func:
-                result.append(args)
+                    result.append(func(*args))
             else:
-                result.append(func(*args))
-        else:
-            return result
+                return result
+
+class _ManagedNewlistHint(object):
+    """ Context manager returning a newlist_hint upon entry.
+
+    Upon exit the list's underlying capacity will be cut back to match
+    its length if necessary (incase the initial length_hint was too
+    large).
+    """
+
+    def __init__(self, length_hint):
+        self.length_hint = length_hint
+        self.list = newlist_hint(length_hint)
+
+    def __enter__(self):
+        return self.list
+
+    def __exit__(self, type, value, tb):
+        if type is None:
+            extended = len(self.list)
+            if extended < self.length_hint:
+                resizelist_hint(self.list, extended)
 
 sentinel = object()
 
         return _filter_string(func, seq, unicode)
     elif isinstance(seq, tuple):
         return _filter_tuple(func, seq)
-    result = []
-    for item in seq:
-        if func(item):
-            result.append(item)
+    with _ManagedNewlistHint(operator._length_hint(seq, 0)) as result:
+        for item in seq:
+            if func(item):
+                result.append(item)
     return result
 
 def _filter_string(func, string, str_type):
     if func is bool and type(string) is str_type:
         return string
-    result = []
-    for i in range(len(string)):
+    length = len(string)
+    result = newlist_hint(length)
+    for i in range(length):
         # You must call __getitem__ on the strings, simply iterating doesn't
         # work :/
         item = string[i]
     return str_type().join(result)
 
 def _filter_tuple(func, seq):
-    result = []
-    for i in range(len(seq)):
+    length = len(seq)
+    result = newlist_hint(length)
+    for i in range(length):
         # Again, must call __getitem__, at least there are tests.
         item = seq[i]
         if func(item):
 in length to the length of the shortest argument sequence."""
     if not sequences:
         return []
-    result = []
-    iterators = [iter(seq) for seq in sequences]
-    while True:
-        try:
-            items = [next(it) for it in iterators]
-        except StopIteration:
-            return result
-        result.append(tuple(items))
+
+    # Gather the iterators and guess the result length (the min of the
+    # input lengths)
+    iterators = []
+    min_hint = -1
+    for seq in sequences:
+        iterators.append(iter(seq))
+        hint = operator._length_hint(seq, min_hint)
+        if min_hint == -1 or hint < min_hint:
+            min_hint = hint
+    if min_hint == -1:
+        min_hint = 0
+
+    with _ManagedNewlistHint(min_hint) as result:
+        while True:
+            try:
+                items = [next(it) for it in iterators]
+            except StopIteration:
+                return result
+            result.append(tuple(items))

File pypy/module/__builtin__/functional.py

     def descr___iter__(self, space):
         return space.wrap(self)
 
+    def descr_length(self, space):
+        return space.wrap(0 if self.remaining == -1 else self.remaining + 1)
+
     def descr_next(self, space):
         if self.remaining >= 0:
             w_index = space.wrap(self.remaining)
         return space.newtuple([w_new_inst, w_info])
 
 W_ReversedIterator.typedef = TypeDef("reversed",
-    __iter__=interp2app(W_ReversedIterator.descr___iter__),
-    next=interp2app(W_ReversedIterator.descr_next),
-    __reduce__=interp2app(W_ReversedIterator.descr___reduce__),
+    __iter__        = interp2app(W_ReversedIterator.descr___iter__),
+    __length_hint__ = interp2app(W_ReversedIterator.descr_length),
+    next            = interp2app(W_ReversedIterator.descr_next),
+    __reduce__      = interp2app(W_ReversedIterator.descr___reduce__),
 )
 
 # exported through _pickle_support
         raise OperationError(self.space.w_StopIteration, self.space.w_None)
 
     def descr_len(self):
-        return self.space.wrap(self.remaining)
+        return self.space.wrap(self.get_remaining())
 
     def descr_reduce(self):
         from pypy.interpreter.mixedmodule import MixedModule
 
 W_XRangeIterator.typedef = TypeDef("rangeiterator",
     __iter__        = interp2app(W_XRangeIterator.descr_iter),
-# XXX __length_hint__()
-##    __len__         = interp2app(W_XRangeIterator.descr_len),
+    __length_hint__ = interp2app(W_XRangeIterator.descr_len),
     next            = interp2app(W_XRangeIterator.descr_next),
     __reduce__      = interp2app(W_XRangeIterator.descr_reduce),
 )

File pypy/module/__builtin__/test/test_functional.py

    def test_three_lists(self):
       assert zip([1,2,3], [1,2], [1,2,3]) == [(1,1,1), (2,2,2)]
 
+   def test_bad_length_hint(self):
+      class Foo(object):
+         def __length_hint__(self):
+            return NotImplemented
+         def __iter__(self):
+            if False:
+               yield None
+      assert zip(Foo()) == []
+
 class AppTestReduce:
    def test_None(self):
        raises(TypeError, reduce, lambda x, y: x+y, [1,2,3], None)

File pypy/module/__pypy__/__init__.py

         'do_what_I_mean'            : 'interp_magic.do_what_I_mean',
         'list_strategy'             : 'interp_magic.list_strategy',
         'validate_fd'               : 'interp_magic.validate_fd',
+        'resizelist_hint'           : 'interp_magic.resizelist_hint',
+        'newlist_hint'              : 'interp_magic.newlist_hint',
         'newdict'                   : 'interp_dict.newdict',
         'dictstrategy'              : 'interp_dict.dictstrategy',
     }

File pypy/module/__pypy__/interp_magic.py

 from pypy.interpreter.error import OperationError, wrap_oserror
 from pypy.interpreter.gateway import unwrap_spec
 from pypy.rlib.objectmodel import we_are_translated
+from pypy.objspace.std.listobject import W_ListObject
 from pypy.objspace.std.typeobject import MethodCache
 from pypy.objspace.std.mapdict import IndexCache
 from pypy.rlib import rposix
     return space.wrap(42)
 
 def list_strategy(space, w_list):
-    from pypy.objspace.std.listobject import W_ListObject
     if isinstance(w_list, W_ListObject):
         return space.wrap(w_list.strategy._applevel_repr)
     else:
         space.wrap('cp%d' % rwin32.GetConsoleCP()),
         space.wrap('cp%d' % rwin32.GetConsoleOutputCP()),
         ])
+
+@unwrap_spec(sizehint=int)
+def resizelist_hint(space, w_iterable, sizehint):
+    if not isinstance(w_iterable, W_ListObject):
+        raise OperationError(space.w_TypeError,
+                             space.wrap("arg 1 must be a 'list'"))
+    w_iterable._resize_hint(sizehint)
+
+@unwrap_spec(sizehint=int)
+def newlist_hint(space, sizehint):
+    return space.newlist_hint(sizehint)

File pypy/module/_collections/interp_deque.py

     def iter(self):
         return self.space.wrap(self)
 
+    def length(self):
+        return self.space.wrap(self.counter)
+
     def next(self):
         self.deque.checklock(self.lock)
         if self.counter == 0:
         return w_x
 
 W_DequeIter.typedef = TypeDef("deque_iterator",
-    __iter__ = interp2app(W_DequeIter.iter),
-    next = interp2app(W_DequeIter.next),
+    __iter__        = interp2app(W_DequeIter.iter),
+    __length_hint__ = interp2app(W_DequeIter.length),
+    next            = interp2app(W_DequeIter.next),
 )
 W_DequeIter.typedef.acceptable_as_base_class = False
 
     def iter(self):
         return self.space.wrap(self)
 
+    def length(self):
+        return self.space.wrap(self.counter)
+
     def next(self):
         self.deque.checklock(self.lock)
         if self.counter == 0:
         return w_x
 
 W_DequeRevIter.typedef = TypeDef("deque_reverse_iterator",
-    __iter__ = interp2app(W_DequeRevIter.iter),
-    next = interp2app(W_DequeRevIter.next),
+    __iter__        = interp2app(W_DequeRevIter.iter),
+    __length_hint__ = interp2app(W_DequeRevIter.length),
+    next            = interp2app(W_DequeRevIter.next),
 )
 W_DequeRevIter.typedef.acceptable_as_base_class = False
 

File pypy/module/itertools/interp_itertools.py

             self.count = 0
         else:
             self.counting = True
-            self.count = self.space.int_w(w_times)
+            self.count = max(self.space.int_w(w_times), 0)
 
     def next_w(self):
         if self.counting:
     def iter_w(self):
         return self.space.wrap(self)
 
+    def length_w(self):
+        if not self.counting:
+            return self.space.w_NotImplemented
+        return self.space.wrap(self.count)
+
     def repr_w(self):
         objrepr = self.space.str_w(self.space.repr(self.w_obj))
         if self.counting:
 W_Repeat.typedef = TypeDef(
         'repeat',
         __module__ = 'itertools',
-        __new__  = interp2app(W_Repeat___new__),
-        __iter__ = interp2app(W_Repeat.iter_w),
-        next     = interp2app(W_Repeat.next_w),
-        __repr__ = interp2app(W_Repeat.repr_w),
+        __new__          = interp2app(W_Repeat___new__),
+        __iter__         = interp2app(W_Repeat.iter_w),
+        __length_hint__  = interp2app(W_Repeat.length_w),
+        next             = interp2app(W_Repeat.next_w),
+        __repr__         = interp2app(W_Repeat.repr_w),
         __doc__  = """Make an iterator that returns object over and over again.
     Runs indefinitely unless the times argument is specified.  Used
     as argument to imap() for invariant parameters to the called

File pypy/module/itertools/test/test_itertools.py

 
     def test_repeat_len(self):
         import itertools
+        import operator
 
         r = itertools.repeat('a', 15)
         r.next()
         raises(TypeError, "len(itertools.repeat('xkcd'))")
 
+        r = itertools.repeat('a', -3)
+        assert operator._length_hint(r, 3) == 0
+
     def test_takewhile(self):
         import itertools
 

File pypy/module/operator/__init__.py

                     'sub', 'truediv', 'truth', 'xor',
                     'iadd', 'iand', 'iconcat', 'idiv', 'ifloordiv',
                     'ilshift', 'imod', 'imul', 'ior', 'ipow', 'irepeat',
-                    'irshift', 'isub', 'itruediv', 'ixor']
+                    'irshift', 'isub', 'itruediv', 'ixor', '_length_hint']
 
     interpleveldefs = {}
 

File pypy/module/operator/interp_operator.py

 from pypy.interpreter.error import OperationError
+from pypy.interpreter.gateway import unwrap_spec
 
 def index(space, w_a):
     return space.index(w_a)
 
     return space.inplace_mul(w_obj1, w_obj2)
 
+# _length_hint (to be length_hint in 3.4)
+
+@unwrap_spec(default=int)
+def _length_hint(space, w_iterable, default):
+    return space.wrap(space.length_hint(w_iterable, default))

File pypy/module/pypyjit/test_pypy_c/model.py

File contents unchanged.

File pypy/objspace/std/dicttype.py

 
 # ____________________________________________________________
 
+def descr_dictiter__length_hint__(space, w_self):
+    from pypy.objspace.std.dictmultiobject import W_BaseDictMultiIterObject
+    assert isinstance(w_self, W_BaseDictMultiIterObject)
+    return space.wrap(w_self.iteratorimplementation.length())
+
+
 def descr_dictiter__reduce__(w_self, space):
     """
     This is a slightly special case of pickling.
 
 
 dictiter_typedef = StdTypeDef("dictionaryiterator",
-    __reduce__ = gateway.interp2app(descr_dictiter__reduce__),
+    __length_hint__ = gateway.interp2app(descr_dictiter__length_hint__),
+    __reduce__      = gateway.interp2app(descr_dictiter__reduce__),
     )
 
 # ____________________________________________________________

File pypy/objspace/std/iterobject.py

     w_seqiter.index += 1
     return w_item
 
-# XXX __length_hint__()
-##def len__SeqIter(space,  w_seqiter):
-##    return w_seqiter.getlength(space)
-
 
 def iter__FastTupleIter(space, w_seqiter):
     return w_seqiter
     w_seqiter.index = index + 1
     return w_item
 
-# XXX __length_hint__()
-##def len__FastTupleIter(space, w_seqiter):
-##    return w_seqiter.getlength(space)
-
 
 def iter__FastListIter(space, w_seqiter):
     return w_seqiter
     w_seqiter.index = index + 1
     return w_item
 
-# XXX __length_hint__()
-##def len__FastListIter(space, w_seqiter):
-##    return w_seqiter.getlength(space)
-
 
 def iter__ReverseSeqIter(space, w_seqiter):
     return w_seqiter
         raise OperationError(space.w_StopIteration, space.w_None)
     return w_item
 
-# XXX __length_hint__()
-##def len__ReverseSeqIter(space, w_seqiter):
-##    if w_seqiter.w_seq is None:
-##        return space.wrap(0)
-##    index = w_seqiter.index+1
-##    w_length = space.len(w_seqiter.w_seq)
-##    # if length of sequence is less than index :exhaust iterator
-##    if space.is_true(space.gt(space.wrap(w_seqiter.index), w_length)):
-##        w_len = space.wrap(0)
-##        w_seqiter.w_seq = None
-##    else:
-##        w_len =space.wrap(index)
-##    if space.is_true(space.lt(w_len,space.wrap(0))):
-##        w_len = space.wrap(0)
-##    return w_len
-
 register_all(vars())

File pypy/objspace/std/itertype.py

     tup      = [w_self.w_seq, space.wrap(w_self.index)]
     return space.newtuple([new_inst, space.newtuple(tup)])
 
+
+def descr_seqiter__length_hint__(space, w_self):
+    from pypy.objspace.std.iterobject import W_AbstractSeqIterObject
+    assert isinstance(w_self, W_AbstractSeqIterObject)
+    return w_self.getlength(space)
+
 # ____________________________________________________________
 
 def descr_reverseseqiter__reduce__(w_self, space):
     tup      = [w_self.w_seq, space.wrap(w_self.index)]
     return space.newtuple([new_inst, space.newtuple(tup)])
 
+
+def descr_reverseseqiter__length_hint__(space, w_self):
+    from pypy.objspace.std.iterobject import W_ReverseSeqIterObject
+    assert isinstance(w_self, W_ReverseSeqIterObject)
+    if w_self.w_seq is None:
+        return space.wrap(0)
+    index = w_self.index + 1
+    w_length = space.len(w_self.w_seq)
+    # if length of sequence is less than index :exhaust iterator
+    if space.is_true(space.gt(space.wrap(w_self.index), w_length)):
+        w_len = space.wrap(0)
+        w_self.w_seq = None
+    else:
+        w_len = space.wrap(index)
+    if space.is_true(space.lt(w_len, space.wrap(0))):
+        w_len = space.wrap(0)
+    return w_len
+
 # ____________________________________________________________
 iter_typedef = StdTypeDef("sequenceiterator",
     __doc__ = '''iter(collection) -> iterator
 In the second form, the callable is called until it returns the sentinel.''',
 
     __reduce__ = gateway.interp2app(descr_seqiter__reduce__),
+    __length_hint__ = gateway.interp2app(descr_seqiter__length_hint__),
     )
 iter_typedef.acceptable_as_base_class = False
 
 reverse_iter_typedef = StdTypeDef("reversesequenceiterator",
 
     __reduce__ = gateway.interp2app(descr_reverseseqiter__reduce__),
+    __length_hint__ = gateway.interp2app(descr_reverseseqiter__length_hint__),
     )
 reverse_iter_typedef.acceptable_as_base_class = False

File pypy/objspace/std/listobject.py

 from pypy.objspace.std.register_all import register_all
 from pypy.objspace.std.multimethod import FailedToImplement
 from pypy.interpreter.error import OperationError, operationerrfmt
+from pypy.interpreter.generator import GeneratorIterator
 from pypy.objspace.std.inttype import wrapint
 from pypy.objspace.std.listtype import get_list_index
 from pypy.objspace.std.sliceobject import W_SliceObject, normalize_simple_slice
 from pypy.objspace.std import slicetype
 from pypy.interpreter import gateway, baseobjspace
-from pypy.rlib.objectmodel import instantiate, specialize, newlist_hint
+from pypy.rlib.objectmodel import (instantiate, newlist_hint, specialize,
+                                   resizelist_hint)
 from pypy.rlib.listsort import make_timsort_class
 from pypy.rlib import rerased, jit, debug
 from pypy.interpreter.argument import Signature
     storage = strategy.erase(None)
     return W_ListObject.from_storage_and_strategy(space, storage, strategy)
 
+def make_empty_list_with_size(space, hint):
+    strategy = SizeListStrategy(space, hint)
+    storage = strategy.erase(None)
+    return W_ListObject.from_storage_and_strategy(space, storage, strategy)
+
 @jit.look_inside_iff(lambda space, list_w, sizehint:
                          jit.isconstant(len(list_w)) and len(list_w) < UNROLL_CUTOFF)
 def get_strategy_from_list_objects(space, list_w, sizehint):
 
     return space.fromcache(ObjectListStrategy)
 
+def _get_printable_location(w_type):
+    return ('list__do_extend_from_iterable [w_type=%s]' %
+            w_type.getname(w_type.space))
+
+_do_extend_jitdriver = jit.JitDriver(
+    name='list__do_extend_from_iterable',
+    greens=['w_type'],
+    reds=['i', 'w_iterator', 'w_list'],
+    get_printable_location=_get_printable_location)
+
+def _do_extend_from_iterable(space, w_list, w_iterable):
+    w_iterator = space.iter(w_iterable)
+    w_type = space.type(w_iterator)
+    i = 0
+    while True:
+        _do_extend_jitdriver.jit_merge_point(w_type=w_type,
+                                             i=i,
+                                             w_iterator=w_iterator,
+                                             w_list=w_list)
+        try:
+            w_list.append(space.next(w_iterator))
+        except OperationError, e:
+            if not e.match(space, space.w_StopIteration):
+                raise
+            break
+        i += 1
+    return i
+
 def is_W_IntObject(w_object):
     from pypy.objspace.std.intobject import W_IntObject
     return type(w_object) is W_IntObject
         with the same strategy and a copy of the storage"""
         return self.strategy.clone(self)
 
+    def _resize_hint(self, hint):
+        """Ensure the underlying list has room for at least hint
+        elements without changing the len() of the list"""
+        return self.strategy._resize_hint(self, hint)
+
     def copy_into(self, other):
         """Used only when extending an EmptyList. Sets the EmptyLists
         strategy and storage according to the other W_List"""
         index not."""
         self.strategy.insert(self, index, w_item)
 
-    def extend(self, items_w):
+    def extend(self, w_any):
         """Appends the given list of wrapped items."""
-        self.strategy.extend(self, items_w)
+        self.strategy.extend(self, w_any)
 
     def reverse(self):
         """Reverses the list."""
     def copy_into(self, w_list, w_other):
         raise NotImplementedError
 
+    def _resize_hint(self, w_list, hint):
+        raise NotImplementedError
+
     def contains(self, w_list, w_obj):
         # needs to be safe against eq_w() mutating the w_list behind our back
         i = 0
     def insert(self, w_list, index, w_item):
         raise NotImplementedError
 
-    def extend(self, w_list, items_w):
+    def extend(self, w_list, w_any):
+        if type(w_any) is W_ListObject or (isinstance(w_any, W_ListObject) and
+                                           self.space._uses_list_iter(w_any)):
+            self._extend_from_list(w_list, w_any)
+        elif isinstance(w_any, GeneratorIterator):
+            w_any.unpack_into_w(w_list)
+        else:
+            self._extend_from_iterable(w_list, w_any)
+
+    def _extend_from_list(self, w_list, w_other):
         raise NotImplementedError
 
+    def _extend_from_iterable(self, w_list, w_iterable):
+        """Extend w_list from a generic iterable"""
+        length_hint = self.space.length_hint(w_iterable, 0)
+        if length_hint:
+            w_list._resize_hint(w_list.length() + length_hint)
+
+        extended = _do_extend_from_iterable(self.space, w_list, w_iterable)
+
+        # cut back if the length hint was too large
+        if extended < length_hint:
+            w_list._resize_hint(w_list.length())
+
     def reverse(self, w_list):
         raise NotImplementedError
 
     def copy_into(self, w_list, w_other):
         pass
 
+    def _resize_hint(self, w_list, hint):
+        assert hint >= 0
+        if hint:
+            w_list.strategy = SizeListStrategy(self.space, hint)
+
     def contains(self, w_list, w_obj):
         return False
 
         assert index == 0
         self.append(w_list, w_item)
 
-    def extend(self, w_list, w_other):
+    def _extend_from_list(self, w_list, w_other):
         w_other.copy_into(w_list)
 
+    def _extend_from_iterable(self, w_list, w_iterable):
+        from pypy.objspace.std.tupleobject import W_AbstractTupleObject
+        space = self.space
+        if isinstance(w_iterable, W_AbstractTupleObject):
+            w_list.__init__(space, w_iterable.getitems_copy())
+            return
+
+        intlist = space.listview_int(w_iterable)
+        if intlist is not None:
+            w_list.strategy = strategy = space.fromcache(IntegerListStrategy)
+            # need to copy because intlist can share with w_iterable
+            w_list.lstorage = strategy.erase(intlist[:])
+            return
+
+        strlist = space.listview_str(w_iterable)
+        if strlist is not None:
+            w_list.strategy = strategy = space.fromcache(StringListStrategy)
+            # need to copy because intlist can share with w_iterable
+            w_list.lstorage = strategy.erase(strlist[:])
+            return
+
+        ListStrategy._extend_from_iterable(self, w_list, w_iterable)
+
     def reverse(self, w_list):
         pass
 
         self.sizehint = sizehint
         ListStrategy.__init__(self, space)
 
+    def _resize_hint(self, w_list, hint):
+        assert hint >= 0
+        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
         w_clone = W_ListObject.from_storage_and_strategy(self.space, storage, self)
         return w_clone
 
+    def _resize_hint(self, w_list, hint):
+        # XXX: this could be supported
+        assert hint >= 0
+
     def copy_into(self, w_list, w_other):
         w_other.strategy = self
         w_other.lstorage = w_list.lstorage
         self.switch_to_integer_strategy(w_list)
         w_list.insert(index, w_item)
 
-    def extend(self, w_list, items_w):
+    def extend(self, w_list, w_any):
         self.switch_to_integer_strategy(w_list)
-        w_list.extend(items_w)
+        w_list.extend(w_any)
 
     def reverse(self, w_list):
         self.switch_to_integer_strategy(w_list)
         w_clone = W_ListObject.from_storage_and_strategy(self.space, storage, self)
         return w_clone
 
+    def _resize_hint(self, w_list, hint):
+        resizelist_hint(self.unerase(w_list.lstorage), hint)
+
     def copy_into(self, w_list, w_other):
         w_other.strategy = self
         items = self.unerase(w_list.lstorage)[:]
         w_list.switch_to_object_strategy()
         w_list.insert(index, w_item)
 
-    def extend(self, w_list, w_other):
+    def _extend_from_list(self, w_list, w_other):
         l = self.unerase(w_list.lstorage)
         if self.list_is_correct_type(w_other):
             l += self.unerase(w_other.lstorage)
 init_defaults = [None]
 
 def init__List(space, w_list, __args__):
-    from pypy.objspace.std.tupleobject import W_AbstractTupleObject
     # this is on the silly side
     w_iterable, = __args__.parse_obj(
             None, 'list', init_signature, init_defaults)
     w_list.clear(space)
     if w_iterable is not None:
-        if type(w_iterable) is W_ListObject:
-            w_iterable.copy_into(w_list)
-            return
-        elif isinstance(w_iterable, W_AbstractTupleObject):
-            w_list.__init__(space, w_iterable.getitems_copy())
-            return
-
-        intlist = space.listview_int(w_iterable)
-        if intlist is not None:
-            w_list.strategy = strategy = space.fromcache(IntegerListStrategy)
-             # need to copy because intlist can share with w_iterable
-            w_list.lstorage = strategy.erase(intlist[:])
-            return
-
-        strlist = space.listview_str(w_iterable)
-        if strlist is not None:
-            w_list.strategy = strategy = space.fromcache(StringListStrategy)
-             # need to copy because intlist can share with w_iterable
-            w_list.lstorage = strategy.erase(strlist[:])
-            return
-
-        # xxx special hack for speed
-        from pypy.interpreter.generator import GeneratorIterator
-        if isinstance(w_iterable, GeneratorIterator):
-            w_iterable.unpack_into_w(w_list)
-            return
-        # /xxx
-        _init_from_iterable(space, w_list, w_iterable)
-
-def _init_from_iterable(space, w_list, w_iterable):
-    # in its own function to make the JIT look into init__List
-    w_iterator = space.iter(w_iterable)
-    while True:
-        try:
-            w_item = space.next(w_iterator)
-        except OperationError, e:
-            if not e.match(space, space.w_StopIteration):
-                raise
-            break  # done
-        w_list.append(w_item)
+        w_list.extend(w_iterable)
 
 def len__List(space, w_list):
     result = w_list.length()
     return w_list1
 
 def inplace_add__List_List(space, w_list1, w_list2):
-    list_extend__List_List(space, w_list1, w_list2)
+    list_extend__List_ANY(space, w_list1, w_list2)
     return w_list1
 
 def mul_list_times(space, w_list, w_times):
     w_list.append(w_any)
     return space.w_None
 
-def list_extend__List_List(space, w_list, w_other):
-    w_list.extend(w_other)
-    return space.w_None
-
 def list_extend__List_ANY(space, w_list, w_any):
-    w_other = W_ListObject(space, space.listview(w_any))
-    w_list.extend(w_other)
+    w_list.extend(w_any)
     return space.w_None
 
 # default of w_idx is space.w_None (see listtype.py)

File pypy/objspace/std/setobject.py

         return w_key
     raise OperationError(space.w_StopIteration, space.w_None)
 
-# XXX __length_hint__()
-##def len__SetIterObject(space, w_setiter):
-##    content = w_setiter.content
-##    if content is None or w_setiter.len == -1:
-##        return space.wrap(0)
-##    return space.wrap(w_setiter.len - w_setiter.pos)
-
 # some helper functions
 
 def newset(space):

File pypy/objspace/std/settype.py

 
 set_typedef.registermethods(globals())
 
-setiter_typedef = StdTypeDef("setiterator")
+def descr_setiterator__length_hint__(space, w_self):
+    from pypy.objspace.std.setobject import W_SetIterObject
+    assert isinstance(w_self, W_SetIterObject)
+    return space.wrap(w_self.iterimplementation.length())
+
+setiter_typedef = StdTypeDef("setiterator",
+    __length_hint__ = gateway.interp2app(descr_setiterator__length_hint__),
+    )

File pypy/objspace/std/test/test_lengthhint.py

+from pypy.module._collections.interp_deque import W_Deque
+from pypy.module.itertools.interp_itertools import W_Repeat
+
+class TestLengthHint:
+
+    SIZE = 4
+    ITEMS = range(SIZE)
+
+    def _test_length_hint(self, w_obj):
+        space = self.space
+        assert space.length_hint(w_obj, 8) == self.SIZE
+
+        w_iter = space.iter(w_obj)
+        assert space.int_w(
+            space.call_method(w_iter, '__length_hint__')) == self.SIZE
+        assert space.length_hint(w_iter, 8) == self.SIZE
+
+        space.next(w_iter)
+        assert space.length_hint(w_iter, 8) == self.SIZE - 1
+
+    def test_bytearray(self):
+        space = self.space
+        w_bytearray = space.call_function(space.w_bytearray,
+                                          space.wrap(self.ITEMS))
+        self._test_length_hint(w_bytearray)
+
+    def test_dict(self):
+        space = self.space
+        w_dict = space.call_function(space.w_dict,
+                                     space.wrap((i, None) for i in self.ITEMS))
+        self._test_length_hint(w_dict)
+
+    def test_dict_iterkeys(self):
+        w_iterkeys = self.space.appexec([], """():
+            return dict.fromkeys(%r).iterkeys()
+        """ % self.ITEMS)
+        self._test_length_hint(w_iterkeys)
+
+    def test_dict_values(self):
+        w_itervalues = self.space.appexec([], """():
+            return dict.fromkeys(%r).itervalues()
+        """ % self.ITEMS)
+        self._test_length_hint(w_itervalues)
+
+    def test_frozenset(self):
+        space = self.space
+        w_set = space.call_function(space.w_frozenset, space.wrap(self.ITEMS))
+        self._test_length_hint(w_set)
+
+    def test_set(self):
+        space = self.space
+        w_set = space.call_function(space.w_set, space.wrap(self.ITEMS))
+        self._test_length_hint(w_set)
+
+    def test_list(self):
+        self._test_length_hint(self.space.wrap(self.ITEMS))
+
+    def test_str(self):
+        self._test_length_hint(self.space.wrap('P' * self.SIZE))
+
+    def test_unicode(self):
+        self._test_length_hint(self.space.wrap(u'Y' * self.SIZE))
+
+    def test_tuple(self):
+        self._test_length_hint(self.space.newtuple(self.ITEMS))
+
+    def test_reversed(self):
+        # test the generic reversed iterator (w_foo lacks __reversed__)
+        space = self.space
+        w_foo = space.appexec([], """():
+            class Foo(object):
+                def __len__(self):
+                    return %r
+                def __getitem__(self, index):
+                    if 0 <= index < %r:
+                        return index
+                    raise IndexError()
+            return Foo()
+        """ % (self.SIZE, self.SIZE))
+        w_reversed = space.call_method(space.builtin, 'reversed', w_foo)
+        assert space.int_w(
+            space.call_method(w_reversed, '__length_hint__')) == self.SIZE
+        self._test_length_hint(w_reversed)
+
+    def test_reversedsequenceiterator(self):
+        space = self.space
+        w_reversed = space.call_method(space.builtin, 'reversed',
+                                       space.wrap(self.ITEMS))
+        assert space.int_w(
+            space.call_method(w_reversed, '__length_hint__')) == self.SIZE
+        self._test_length_hint(w_reversed)
+
+    def test_xrange(self):
+        space = self.space
+        w_xrange = space.call_method(space.builtin, 'xrange',
+                                     space.newint(self.SIZE))
+        self._test_length_hint(w_xrange)
+
+    def test_itertools_repeat(self):
+        space = self.space
+        self._test_length_hint(W_Repeat(space, space.wrap(22),
+                                        space.wrap(self.SIZE)))
+
+    def test_collections_deque(self):
+        space = self.space
+        w_deque = W_Deque(space)
+        space.call_method(w_deque, '__init__', space.wrap(self.ITEMS))
+        self._test_length_hint(w_deque)
+        self._test_length_hint(w_deque.reviter())
+
+    def test_default(self):
+        space = self.space
+        assert space.length_hint(space.w_False, 3) == 3
+
+    def test_NotImplemented(self):
+        space = self.space
+        w_foo = space.appexec([], """():
+            class Foo(object):
+                def __length_hint__(self):
+                    return NotImplemented
+            return Foo()
+        """)
+        assert space.length_hint(w_foo, 3) == 3
+
+    def test_invalid_hint(self):
+        space = self.space
+        w_foo = space.appexec([], """():
+            class Foo(object):
+                def __length_hint__(self):
+                    return -1
+            return Foo()
+        """)
+        space.raises_w(space.w_ValueError, space.length_hint, w_foo, 3)
+
+    def test_exc(self):
+        space = self.space
+        w_foo = space.appexec([], """():
+            class Foo(object):
+                def __length_hint__(self):
+                    1 / 0
+            return Foo()
+        """)
+        space.raises_w(space.w_ZeroDivisionError, space.length_hint, w_foo, 3)

File pypy/objspace/std/test/test_listobject.py

         space.call_method(w_l, 'append', space.w_None)
         assert isinstance(w_l.strategy, ObjectListStrategy)
 
+    def test_newlist_hint(self):
+        space = self.space
+        w_lst = space.newlist_hint(13)
+        assert isinstance(w_lst.strategy, SizeListStrategy)
+        assert w_lst.strategy.sizehint == 13
 
 class AppTestW_ListObject(object):
     def setup_class(cls):
             class SubClass(base):
                 def __iter__(self):
                     return iter("foobar")
-            assert list(SubClass(arg)) == ['f', 'o', 'o', 'b', 'a', 'r']
+            sub = SubClass(arg)
+            assert list(sub) == ['f', 'o', 'o', 'b', 'a', 'r']
+            l = []
+            l.extend(sub)
+            assert l == ['f', 'o', 'o', 'b', 'a', 'r']
+            # test another list strategy
+            l = ['Z']
+            l.extend(sub)
+            assert l == ['Z', 'f', 'o', 'o', 'b', 'a', 'r']
+
             class Sub2(base):
                 pass
             assert list(Sub2(arg)) == list(base(arg))

File pypy/objspace/std/test/test_liststrategies.py

File contents unchanged.

File pypy/rlib/objectmodel.py

         hop.exception_is_here()
         return rtype_newlist(hop, v_sizehint=v)
 
+def resizelist_hint(l, sizehint):
+    """Reallocate the underlying list to the specified sizehint"""
+    return
+
+class Entry(ExtRegistryEntry):
+    _about_ = resizelist_hint
+
+    def compute_result_annotation(self, s_l, s_sizehint):
+        from pypy.annotation import model as annmodel
+        assert isinstance(s_l, annmodel.SomeList)
+        assert isinstance(s_sizehint, annmodel.SomeInteger)
+        s_l.listdef.listitem.resize()
+
+    def specialize_call(self, hop):
+        r_list = hop.args_r[0]
+        v_list, v_sizehint = hop.inputargs(*hop.args_r)
+        hop.exception_is_here()
+        hop.gendirectcall(r_list.LIST._ll_resize_hint, v_list, v_sizehint)
+
 # ____________________________________________________________
 #
 # id-like functions.  The idea is that calling hash() or id() is not

File pypy/rlib/test/test_objectmodel.py

 from pypy.rlib.objectmodel import *
 from pypy.translator.translator import TranslationContext, graphof
 from pypy.rpython.test.tool import BaseRtypingTest, LLRtypeMixin, OORtypeMixin
+from pypy.rpython.test.test_llinterp import interpret
 from pypy.conftest import option
 
 def strange_key_eq(key1, key2):
             break
     assert llop.args[2] is graph.startblock.inputargs[0]
     
+def test_resizelist_hint():
+    from pypy.annotation.model import SomeInteger
+    def f(z):
+        x = []
+        resizelist_hint(x, 39)
+        return len(x)
+
+    graph = getgraph(f, [SomeInteger()])
+    for _, op in graph.iterblockops():
+        if op.opname == 'direct_call':
+            break
+    call_name = op.args[0].value._obj.graph.name
+    assert call_name.startswith('_ll_list_resize_hint')
+    call_arg2 = op.args[2].value
+    assert call_arg2 == 39
+
+def test_resizelist_hint_len():
+    def f(i):
+        l = [44]
+        resizelist_hint(l, i)
+        return len(l)
+
+    r = interpret(f, [29])
+    assert r == 1

File pypy/rpython/lltypesystem/rlist.py

                                           "_ll_resize_ge": _ll_list_resize_ge,
                                           "_ll_resize_le": _ll_list_resize_le,
                                           "_ll_resize": _ll_list_resize,
+                                          "_ll_resize_hint": _ll_list_resize_hint,
                                       }),
                                       hints = {'list': True})
                              )
 # adapted C code
 
 @enforceargs(None, int, None)
-def _ll_list_resize_really(l, newsize, overallocate):
+def _ll_list_resize_hint_really(l, newsize, overallocate):
     """
-    Ensure l.items has room for at least newsize elements, and set
-    l.length to newsize.  Note that l.items may change, and even if
-    newsize is less than l.length on entry.
+    Ensure l.items has room for at least newsize elements.  Note that
+    l.items may change, and even if newsize is less than l.length on
+    entry.
     """
     # This over-allocates proportional to the list size, making room
     # for additional growth.  The over-allocation is mild, but is
         else:
             p = newsize
         rgc.ll_arraycopy(items, newitems, 0, 0, p)
+    l.items = newitems
+
+@jit.dont_look_inside
+def _ll_list_resize_hint(l, newsize):
+    """Ensure l.items has room for at least newsize elements without
+    setting l.length to newsize.
+
+    Used before (and after) a batch operation that will likely grow the
+    list to the newsize (and after the operation incase the initial
+    guess lied).
+    """
+    assert newsize >= 0, "negative list length"
+    allocated = len(l.items)
+    if allocated < newsize or newsize < (allocated >> 1) - 5:
+        _ll_list_resize_hint_really(l, newsize, False)
+
+@enforceargs(None, int, None)
+def _ll_list_resize_really(l, newsize, overallocate):
+    """
+    Ensure l.items has room for at least newsize elements, and set
+    l.length to newsize.  Note that l.items may change, and even if
+    newsize is less than l.length on entry.
+    """
+    _ll_list_resize_hint_really(l, newsize, overallocate)
     l.length = newsize
-    l.items = newitems
 
 # this common case was factored out of _ll_list_resize
 # to see if inlining it gives some speed-up.

File pypy/rpython/ootypesystem/ootype.py

             "_ll_resize_ge": Meth([Signed], Void),
             "_ll_resize_le": Meth([Signed], Void),
             "_ll_resize": Meth([Signed], Void),
+            "_ll_resize_hint": Meth([Signed], Void),
         })
 
         self._setup_methods(generic_types)

File pypy/rpython/rlist.py

     '_ll_resize_le':   (['self', Signed        ], Void),
     # resize to exactly the given size
     '_ll_resize':      (['self', Signed        ], Void),
+    # realloc the underlying list
+    '_ll_resize_hint': (['self', Signed        ], Void),
 })
 
 

File pypy/translator/cli/src/pypylib.cs

                 this._ll_resize_le(length);
         }
 
+        public void _ll_resize_hint(int length)
+        {
+            this.Capacity(length);
+        }
+
         public void _ll_resize_ge(int length)
         {
             if (this.Count < length) 
         public void ll_getitem_fast(int index) { }
         public void ll_setitem_fast(int index) { }
         public void _ll_resize(int length) { this.Count = length; }
+        public void _ll_resize_hint(int length) { }
         public void _ll_resize_ge(int length) { this.Count = length; }
         public void _ll_resize_le(int length) { this.Count = length; }
     }

File pypy/translator/jvm/src/pypy/PyPy.java

             _ll_resize_le(self, length); 
     }
 
+    public static void _ll_resize_hint(ArrayList self, int length) {
+        self.ensureCapacity(length);
+    }
+
     // ----------------------------------------------------------------------
     // ll_math
     //