O(n^2) is bad - can it be fixed?

[Tim Peters]

[Bruce Dawson]
> ...
> Now obviously I can fix this problem - switch from list to array,

No, array doesn't even do as much as lists used to do to avoid quadratic
behavior.  Your test case simply didn't try arrays big enough for this to
show up.  The difference is that array.array('c').append(ch) adds one byte
at a time but list.append(x) adds 4 bytes at a time (on a 32-bit box), so
you need 4x the # of array elements before seeing the same bad Windows
behaviors.

> ...

[Tim]
>> In the meantime, I did check in a change (for 2.2) that continues
>> to do mild over-allocation, but on a sliding scale that doesn't
>> think the world ends at 500 elements.  This speeds real-life
>> appends, but mostly because it gets rid of the current integer
>> multiplication and division in favor of simple bit shifts.  For
>> Bruce's kind of test, it delays the point at which one-at-a-time
>> list.append(x) exhausts Win9x VM from about 2 million elements
>> to about 35 million.  I have higher hopes for NT/Win2K, but haven't
>> yet tested it there.

I've tested it now, and on Win2K it remains flat and fast until the list
exhausts physical RAM, at which point there are long hiccups at resize
points.  Linux was always well-behaved, and still is, and the hiccups are
much shorter there.

[Bruce]
> Cool! I just saw this one. That will definitely help. A factor of
> 16 improvement

Maybe.  As I mentioned in another msg, when I did a straight C realloc
double-the-size test (no Python) and put it in a loop, the end result was
that Win98SE froze on about the 6th iteration.  If you haven't noticed yet
in other contexts, take the hint <wink>:  Win9x is not a robust platform.

> in maximum size (and similar improvement in performance) will make any
> remaining issues increasingly theoretical. Can you post your new
> code snippet?

It's checked in.  Go to

    http://cvs.sf.net/cgi-bin/viewcvs.cgi/python/python/dist/src/

and navigate to Objects/listobject.c, revision 2.93.

> I guess my only (slightly wrinkled nose?) comment would be that
> it seems like Python lists are acquiring an exponential growth
> factor

But a very mild one.  It had a very mild one before too, but stopped
increasing it after 500 elements.  Now there's no bound.

> (which is  a good thing, it solves the quadratic performance) the
> Rube Goldberg way - one special case at a time.

Not sure I follow.  list.append() specifically was "the problem".  What
other behavior are you trying to address?

> If I have a better solution I'll post it.

Sure, but next time please try it first <wink>.