[Python-Dev] list.append optimization Was: collections module
tim.one at comcast.net
Tue Jan 13 14:34:17 EST 2004
> I'll look at the this this weekend.
> The improvement is awesome. Hope it has doesn't muck-up anything
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 
is true. So, calling ob_size "n" for brevity, if we ever reach a point
roundupsize(n) == n+1
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