The REALLY bad thing about Python lists ..

[Russell Turpin]

Thomas Wouters wrote:
> Perhaps your test was just realistic ? Have you seen 
> *real-life* performance problems because of the low 
> overallocation yet ?

I've written MANY real-life programs that built up 
two or more large arrays. Large, meaning over 100,000
elements. An O(n^2) cost to doing this would make
Python unusable for quite a few real-life applications.

HOWEVER .. it may be that Python is twice lucky.  I
suspect that the realloc() on Linux does the smart
thing: allocating exponentially increasing blocks, as
needed, and expanding within the block if possible.
I have not been able to demonstrate O(n^2) behavior
for list allocation in test programs. If anyone can
do this, I would be interested in seeing the test
program.

Russell