Surprising (for me) benchmark results...

[Tim Peters]

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

[Daniel Berlin]
> Are you sure? ...

Python's list.append() is quadratic-time in theory, and in practice on
Windows variants once a list gets "big enough" (although different flavors of
Windows degrade in distinctly different ways).  If the preallocation were
proportional to the current list size, it wouldn't be, but preallocation is
capped independent of list size.

People have historically had a *much* harder time provoking bad append
behavior on Unix variants, presumably because a growing list realloc'ed often
enough migrates to "the end" of the address space, where further reallocs are
satisfied internally by a mere sbrk (and with no physical data movement), or
by asking the OS to boost the size of an mmap'ed segment (mostly ditto).

don't-push-it-and-it-won't-bite-ly y'rs  - tim