Surprising (for me) benchmark results...

[Fredrik Lundh]

Martin von Loewis wrote:
>
> > list.append() appends items to a dynamic array in O(1)+k
> > constant amortized time. It does this by using a liberal preallocation
> > strategy, and leaving empty slots into which new elements can
> > be placed. The occasional realloc() amortizes away quite readily.
>
> No, it doesn't. See listobject.c:ins1, in particular the line
>
> NRESIZE(items, PyObject *, self->ob_size+1);

did you look at the NRESIZE macro?  (I'm pretty sure Joe did)

Cheers /F