The REALLY bad thing about Python lists ..

[Jeff Petkau]

> [Jeff Petkau, on Python's conservative over-allocation when growing
>  a list]
> > I fiddled around with timing tests (1.5.2 on Windows) to see what
> > Python's actual behavior is. If you're adding to a single list, it
> > often is linear, because the list is grown with realloc() which
> > can get lucky and just extend the size of the allocated block
> > without having to move it.

Mea culpa. I tried to reproduce my own tests, so I could
post the code and timings here and get someone to compare
it on Linux, and I couldn't. I was doing this in my test loop:

...    list1 = []
...    list2 = []
...    for i in xrange(size):
...        list1.append(i)
...        list2.append(i)

Given the way integers are allocated, this biases the test
badly against long lists. Oops. With a fixed test (appending
0 instead of i) I could not get bad behavior for append, up
to 10M elements. I guess realloc on Windows is pretty
clever after all.

I still think exponential reallocation is the right way to do it,
but since I can't produce an actual problem case, I'll just
quietly shuffle away now.

--Jeff (jpet at eskimo.com)