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

[Isaac To Kar Keung]

>>>>> "Helen" == Helen Dawson <helend at accessone.com> writes:

    Helen> After discoverting that lists actually are O(n^2), and after
    Helen> hearing a rumour that they behaved badly on Win9x, I decided to
    Helen> investigate.

Actually I don't think that the mmap argument hold a lot of water, and I do
think that the behaviour should be quadratic unless the realloc of Linux do
quadratic allocation.  The problem is that even if it is mmap'ed, it is
still in the same address space, and thus eventually the address spaces of
the two arrays would touch each other, leading to an actual reallocation.
Yes, we can save the copy of the content, but then we need to copy the VM
tables.

    Helen> why not this:

    Helen> static int roundupsize(int n) { if (n < 500) return ROUNDUP(n,
    Helen> 10); else return n + n / 10; }

But that won't even get close to work.  Currently, Python calls PyMem_RESIZE
everytime a resize is needed, but on the other hand there is no member
within the structure to store something like the STL capacity.  If you
really change Python to the above, everything would be the same (or,
actually, worse) than before.  Instead of allocation of size 10, 10, 10,
..., 20, 20, 20, ..., 30, 30, ..., 500, 500, ..., 600, ...; the system will
make allocation like 10, 10, 10, ..., 20, 20, 20, ..., 30, ..., 490, 550,
551, 552, 553, 554, 555, 556, 557, 558, 559, 561, ...  You'll get a huge
number of reallocation and copying this way. ;p

I don't actually see a good solution, actually, short of storing the
capacity somewhere.  The problem is that whatever the mapping, there is a
possible case in which copying and reallocation is done basically everytime.
For example, the current scheme cannot guarantee that the memory system will
be happy with the following code:

  a = [None] * 497    # 12 byte header + 497 pointers = 2000 bytes
  while 1:
    a.append(None)    # Allocate 2100 bytes
    # do some more interesting thing here
    a[-1:] = []       # Become 2000 bytes

Everytime PyMem_RESIZE is called with a different size, and we now have to
hope that the memory system of the OS do the right thing.

There are two possible attutides for this problem.  We can say that this is
a flaw in the C library, and realloc should really deal with the problem
because it happens so often.  Or we can say that this is a Python problem,
that it should always make sure that it runs right in whatever C library.
Perhaps we have to accept that the latter is the answer, given that Win98 is
not doing it right but nobody is going to give you another Win98.

There are two places where we can add the capacity field.  PyObject_VAR_HEAD
is my choice.  Adding 4 bytes of current capacity to the currently 12 bytes
header storing the reference count, type and size.  This has the additional
benefit to get the whole thing to align on 16-byte boundary whereever it is
benefitial.

But there is another solution that does not need the 4-bytes space overhead.
The C library should know the size of allocation anyway, so we can actually
reuse that information.  This ends up that we need to have a library
dependent PyCore_REALLOC_FUNC.  I don't really think that is a good idea,
though.

Regards,
Isaac.