The REALLY bad thing about Python lists ..

[Russell Turpin]

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

It turns out that it doesn't so much optimize, as happen
to be doubly lucky. On Linux, the realloc() procedure
does the smart thing. 

There really is NO excuse for constant space allocation.
It does not save significant space, and it costs 
considerable time. Here is what happens when creating an 
array of length n:

                           Space          Time
                           -----          ----
Extend by K elements:       O(n)        O(n^2)
Extend by factor of F:      O(n)          O(n)

The second strategy wins hands down. If you want to 
argue for the first strategy on the grounds that it
saves space, keep in mind (a) that the space savings 
is only in the proportionality factor, not in the 
complexity, and (b) this factor can be made as small
as desired by choosing a smaller expansion factor, F. 

If you want to argue for the first strategy on the 
grounds that it doesn't matter for small n, well .. 
that is true for almost all algorithms, and would 
really inhibit the use of Python for real applications,
where n gets to be large. If Python behaved this way
for my applications, I would have ditched it already.

Python doesn't behave that way for my applications 
only because they run under Linux. On Linux, memory
blocks come in exponential increments, and realloc()
does nothing if the new request fits into the block
already allocated. This turns the first strategy into
the second strategy, and most of the memory extensions
Python performs on Linux are turned into no-ops!  On
Windows, Python's choice of the first strategy shines
through, making it inappropriate for some real 
applications. So really the issue is:

  Should Python lists be as fast on other platforms
  as they are on Linux, where good OS memory
  management turned the second strategy into the
  first?

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!

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

Grateful-to-develop-on-a-real-OS'ly yrs,
Russell