The REALLY bad thing about Python lists ..

[Tim Peters]

[Moshe Zadka]
> In other words, Python optimizes for the common
> case (lists of <10,000 elements) pretty well. ..

[Russell Turpin]
> It turns out that it doesn't so much optimize, as happen
> to be doubly lucky.

Python deliberately overallocates by a small amount; this is a deliberate
optimization for the cases Moshe identified; it works very well.

> ...
> Python doesn't behave that way for my applications
> only because they run under Linux. On Linux, memory
> blocks come in exponential increments,

I've seen no evidence of that in this thread, and it certainly isn't true of
any real malloc implementation I've seen.  In an earlier post you
*speculated* about this, after failing to construct a program that displayed
the bad behavior you fear.  Now you're claiming it as a fact, but it's
unclear on what basis.  As another poster said, my understanding is that
Linux reallocs typically avoid these bad cases by using mremap() when a
block grows very large (e.g., this is what Doug Lea's widely used malloc
implementation does when mremap is available -- and, no, his realloc doesn't
request any more bytes than the minimum needed to cover the requested space,
alignment, and malloc bookkeeping info).

> and realloc() does nothing if the new request fits into the
> block already allocated.

That's likely true of all realloc implementations, but is more likely to pay
off more often if, e.g., malloc uses a first-fit rather than best-fit
strategy.

> ...
> Personally, I think those who have to develop under
> Windows suffer enough already, and they should at
> least enjoy the same reasonably fast Python as the
> rest of us!

Actually, malloc under Linux "overcommits":  it's possible for malloc to
return a non-NULL value, yet when you reference the memory later, it blows
up.  You're unlikely to bump into that unless you've got a small-platform
Linux without a swap file -- but, if you do, it makes WinCE look like a real
OS <0.6 wink>.

> This raises an interesting Linux question: Does it
> use a buddy-list algorithm for memory management?

Not malloc, no.

i'm-told-the-source-code-is-free-ly y'rs  - tim