The REALLY bad thing about Python lists ..

[Tim Peters]

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

On some flavors of Unix, this is more than just luck:  realloc will
eventually move the vector to "the end" of the address space, after which
further growth is just a mix of boosting the VM high-water mark and the
occasional sbrk.  Under all flavors of Windoes, though, it appears to be
luck (and can't be counted on when a single list gets very large (> about
100K elements)).

> But if you're allocating other stuff while building your list, or
> building two lists in parallel, realloc() doesn't get so lucky
> and growing the list is O(N^2).

Python does *some* over-allocation, though -- most lists in practice are
really quite small, and show no measurable dependence on length.  Most
modern chips are very good at moving contiguous chunks of memory.  For lists
up to several thousand elements, I've never seen non-linear list growth
behavior regardless of platform or number of lists.

> I'd consider this a bug in Python.

Na, it's functioning as designed.  That doesn't mean it couldn't be
improved, but Python runs on small platforms too, where people can't
*afford* significantly more over-allocation than Python currently uses
(either because they're using many thousands of tiny lists, or just one or
two at the limit of their physical RAM).

in-a-tradeoff-somebody-usually-loses-and-python-assumes-
    the-big-boys-are-better-able-to-cope-ly y'rs  - tim