[Python-Dev] list.append optimization Was: collections module (original) (raw)

Tim Peters tim.one at comcast.net
Tue Jan 13 14:34:17 EST 2004

[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.

More information about the Python-Dev mailing list