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

[Tim Peters]

[Tim]
> It can be *delayed*, but Win9x VM management is such that address
> space will still get fragmented beyond hope unless Python also
> takes over allocating heaps.  This gets absurd.

[Isaac To Kar Keung]
> Disclaimer: I don't run a WinXX OS, so I've got no way to test whatever
> I say here.
>
> I'm actually wondering how it can be this bad in WinXX.

Bruce explained it in detail a few msgs back:

    http://groups.google.com/groups?hl=en&lr=&safe=off&
        ic=1&th=8fb1dd7dabf75024,41&seekm=
        3B0DED72.41317BCE%40accessone.com#p

(Yikes!  There's gotta be a better way to get a Google URL than that!)

> If it can make it more than say 50% of the space unusable due to
> fragmentation,

No, most of the memory remains available, but spread out over hundreds of
system-allocated heaps that the OS and/or C runtime seem unable to
recombine, and there's no *contiguous* chunk of address space remaining big
enough to satisfy the request.  The entire VM address space gets turned into
Swiss cheese.  Bruce seemed to think that array.array('c').append behavior
was better, but that's only because the limit on his test was too small (the
array version adds 1 byte per element, the list version 4, and that's why
the list version fails sooner).  No matter what growth strategy you use
(heck, overallocate by a factor of 10), this still bites:  every time
growing the array ends up allocating a new system heap, the heap it's copied
from appears to be lost forever.  This isn't a guess -- I wrote the code,
tried it, and watched the heap trace go to hell.

> then I agree that it is so hopelessly broken that Python shouldn't
> deal with it at all.  Yes, at all.  Python, as an application, don't
> have the VM tools to do this efficiently.

It could, but, again, it's absurd:  Python could do its own heap mgmt on
Win32, using the Win32 API heap mgmt functions instead of MS's libc's.
They're adequate to the task.  But I'm not adding gobs of delicate
platform-specific code to worm around a problem nobody has <0.9 wink>.

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.