[Python-Dev] Do we need __length_hint__ at all? (Was PEP 0424: A method for exposing a length hint)

[Mark Shannon]

To quote from PEP 424:

> Rationale
> =========
> 
> Being able to pre-allocate lists based on the expected size, as estimated by 
> ``__length_hint__``, can be a significant optimization. CPython has been
> observed to run some code faster than PyPy, purely because of this optimization
> being present.
> 

Why is it a significant optimisation?

How much slower is it?
Where is the data?

*If* resizing list is so slow, then why not make it faster?

To quote wikipedia (http://en.wikipedia.org/wiki/Dynamic_array)

"""
As n elements are inserted, the capacities form a geometric progression.
Expanding the array by any constant proportion ensures that inserting n elements
takes O(n) time overall, meaning that each insertion takes amortized constant time.
The value of this proportion a leads to a time-space tradeoff: the average time per
insertion operation is about a/(a-1), while the number of wasted cells is bounded
above by (a-1)n. The choice of a depends on the library or application: some textbooks
use a = 2, but Java's ArrayList implementation uses a = 3/2 and the C implementation
of Python's list data structure uses a = 9/8.
"""

If resizing of lists is too slow, then we should reconsider the 9/8 factor
and/or look to tweak the resizing code.

Cheers,
Mark.