[Python-Dev] list.append optimization Was: collections module

[Tim Peters]

[Raymond Hettinger]
> I'll look at the this this weekend.
>
> The improvement is awesome.  Hope it has doesn't muck-up anything
> else.

It probably does.  It introduces a deep assumption that a list is *never*
allocated, or resized, to hold ob_size slots, but always to hold (at lesat)
roundupsize(ob_size) slots.  If that's ever wrong, the "after" code may not
call realloc() when a realloc is needed (for example, leave out the part
that patched PyList_New(), and watch Python crash all over the place).

One of the standard tests crashed, but I didn't have time to figure out why.
It seemed odd because it died in some sorting test.

A note about why it "should be" correct:  for all i >= 0

    roundupsize(i) > i     [1]

is true.  So, calling ob_size "n" for brevity, if we ever reach a point
where

    roundupsize(n) == n+1

then since

    roundupsize(n+1) > n+1   (by #1, letting i = n+1)

it follows that

    roundupsize(n+1) > n+1 == roundupsize(n)

Or, IOW, when roundupsize(n)==n+1, we're exactly at a boundary where
roundupsize(n+1) grows, so that's a point at which adding a new element
requires calling realloc.  Otherwise

    roundupsize(n) > n+1

(since roundupsize(n) > n by #1, it's not possible that roundupsize(n) <
n+1), so there's room enough already for an additional element, and
realloc() doesn't need to be called.