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

[Tim Peters]

[Isaac To Kar Keung]
> That means, when size is below 500, a list size will always be
> multiple of 10.  When size is larger, it is always multiple of
> 100.  Of course, if the object is already of the right size, the
> system resize() does nothing.
>
> Seems like magic to me... I run the following program and I
> didn't see *any* slowdown, when each of the lists is as large
> as 8M, eating up 60M memory...
> <snip>
> (Will it be the system realloc which actually do the geometric
> scaling, or is it really that geometric scaling is unnecessary?)

[Ben Hutchings]
> As the list buffer grows, realloc() will at some point find that the
> only place to put it is at the top of the heap.  Once it's there,
> further realloc() calls will grow the heap and will not need to move
> the buffer.

Ah, but Isaac (To?  Kar?  what do you call a man with four names <wink>?)
anticipated that (which is indeed "the usual" dodge).  Look at his test
program again:

  a = []
  b = []
  i = 0
  while 1:
    i = i + 1
    if i % 100000 == 0:
      print i
    a.append(0)
    b.append(0)

He's appending to *two* lists, and if realloc moves one to "the top of the
heap", how do you account for the other not slowing things down?

My assumption was that he's running on a box where realloc eventually puts
giant things into their own mmap'ed segment.  This kind of programming can
definitely kill you across platforms, though, and, e.g., Win95 isn't so slick
with just one list growing forever.