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

Mark Shannon mark at hotpy.org
Mon Jul 16 10:37:33 CEST 2012

To quote from PEP 424:

Rationale =========

Being able to pre-allocate lists based on the expected size, as estimated by _lengthhint_, 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.

More information about the Python-Dev mailing list