[Python-Dev] collections module

[Tim Peters]

[Guido]
> Just in case nobody had thought of it before, couldn't the realloc()
> call be avoided when roundupsize(oldsize) == roundupsize(newsize)???

I had thought of it before, but never acted on it <wink>.  roundupsize() has
gotten more expensive over the years too, and it may vary across boxes
whether it's cheaper to call that a second time than it is to make the
system realloc deduce that nothing needs to be done.  roundupsize() is
certainly cheaper than Microsoft's realloc() in the do-nothing case.

Note that there's an endcase glitch here when oldsize==0 and newsize==1.
roundupsize() returns 8 for both, but it doesn't follow that ob_item isn't
NULL.  realloc(p, n) special-cases the snot out of p==NULL to avoid crashing
then.

Note in passing that roundupsize() is expensive *because* lists don't
remember the amount of overallocated space too:  roundupsize() has to
arrange to deliver the same result for many consecutive inputs, to prevent
asking the platform for non-trivial reallocs() ("trivial realloc" ==
"do-nothing realloc" == realloc(p, n) called with fixed p and n multiple
successive times).  If we knew the point at which the "excess" slots were
exhausted, then, e.g., doing realloc(oldsize + (oldsize >> 4)) at that point
would give similar behavior with a much cheaper "new size" function (if we
only computed a new size when a new size was actually needed, the "new size"
function wouldn't have to arrange to remain constant over (eventually)
unboundedly long stretches of consecutive inputs).