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

[Helen Dawson]

Just for the interest of those who are interested in the original Win9x
behaviour and want to see what it does to the memory map, I have
posted a text memory map of the Win98 address space of Python.exe
after running my append script. This is the script that kept appending
characters to a Python list until Win98 ran out of address space,
but not memory.

http://www.cygnus-software.com/papers/pythonmemorymap.txt

You can see the heaps, starting at 4088K and getting bigger by 4K
until memory is filled. Completely understanding the memory map
requires understanding MMUs and the Win32 allocator system, but the
rough idea should be clear. Reserved means that address space is
reserved but not memory. Committed means that memory is reserved
also.

Address space is allocated in 64K chunks, which is why there are
reserved blocks that are 4K to 60K at the end of heaps.

"Amiguous Ambiguous Unkown" means that that block has multiple
"states" and "protection" flags and that the type of the memory is not
known. But trust me, the 4Gbyte+ chunks are mostly heaps.

Bruce/Helen Dawson

Helen Dawson wrote:

> Tim Peters wrote:
>
> > [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
>
> Darn.
>
> > 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.
>
> Oooohhhh yeah. I've managed to avoid doing any significant development
> on Win9x - I've run NT variants for seven years - but my code still needs
> to run on Win9x. Such a pity.
>
> As further proof of how bizarre the Win9x behavior is, I hypothesized that
> if I went:
>
> range(4000000)
>
> in the PythonWin interactive window before running my script that I might
> get better performance. Indeed I do. Win9x will then run my script to
> completion, and *much* faster also.
>
> The range(4000000) statement creates a list with four million elements
> (obviously) which forces a large heap to be created. Since the list is
> immediately destroyed, the heap is empty and available. Then, all
> subsequent growing of my other lists run quite nicely because the
> allocations all fit in the large heap, so realloc() works without any
> copying.
>
> A truly gross hack, mentioned purely for amusement purposes.