Surprising (for me) benchmark results...

Mon May 7 07:14:34 EDT 2001

Courageous <jkraska1 at san.rr.com> writes:

> NO.
> 
> 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);

Regards,
Martin