[Python-Dev] Do we need __length_hint__ at all? (Was PEP 0424: A method for exposing a length hint)
mark at hotpy.org
Mon Jul 16 10:37:33 CEST 2012
To quote from PEP 424:
> 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.
More information about the Python-Dev