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

[Raymond Hettinger]

On Jul 16, 2012, at 1:37 AM, Mark Shannon wrote:

> 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?

Unless pre-sized by with a length prediction, a growing list
periodically needs to call realloc() which can move all the
data to a new location in memory.    Pre-sizing avoids that entirely.

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

A great deal of thought and care went into the current design.
It has already been "tweaked".


Raymond


P.S.  The dictionary code also uses presizing for copies, updates, set conversion, etc.
It is a perfectly reasonable technique to pre-allocate the correct size container
when the ultimate length is knowable in advance.