__length_hint__ isn't a hint for list() #73126

Activity

1. ronaldoussoren commented on Dec 11, 2016

   

   ronaldoussoren

   on Dec 11, 2016

   ContributorAuthor

   More actions

   The following code raises MemoryError instead of creating an empty list:

   # START
   import sys
   
   class CustomIter:
       def __iter__(self):
           return self
       def __next__(self):
           raise StopIteration
       def __length_hint__(self):
           return sys.maxsize
   
   l = list(CustomIter())
   #END

   That's because this empty iterator has a __length_hint__ that claims it returns a very large number of methods.

   The function listextend in Objects/listobject.c already ignores __length_hint__() when using it would overflow the size of the list, it would IMHO also be better to ignore the length hint when the attempt to resize fails as __length_hint__() is documented as a hint that may be incorrect.
2. ronaldoussoren

   added

   interpreter-core(Objects, Python, Grammar, and Parser dirs)(Objects, Python, Grammar, and Parser dirs)

   on Dec 11, 2016
3. ezio-melotti

   transferred this issue fromon Apr 10, 2022
4. serhiy-storchaka commented on Aug 11, 2026

   

   serhiy-storchaka

   on Aug 11, 2026

   Member

   More actions

   list() and bytes() preallocate the result using __length_hint__(), while PySequence_Tuple() no longer uses it. An incorrect hint can therefore cause MemoryError, or, if it is large but not large enough to fail, exhaust memory and swap.

   There are three variants:

   1. Do nothing. The correctness of __length_hint__() is the responsibility of the class which implements it, and we do not protect against other protocol methods lying either.
   2. Limit the preallocation to some reasonable value.
   3. Do not use the hint for preallocation at all, as PySequence_Tuple() already does.

   The benefit of the hint is mostly saving memory for small lists, where its relative cost in time is higher. Calling __length_hint__() on a Python iterator costs about 0.2 microseconds, which is not repaid until about 32 items, and it saves only 0 to 48 bytes for short lists. For larger lists the difference in time is within the noise, and growing overallocates by at most the growth factor: 800 bytes for 1000 items and 449 KiB for 1000000 items.

   #8635 implemented a fourth variant, retrying without preallocation if the allocation fails, but this only helps in the case of an immediate failure.