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

Isaac To kkto at csis.hku.hk
Sat May 26 12:21:27 CEST 2001


>>>>> "Tim" == Tim Peters <tim.one at home.com> writes:

    Tim> Bruce explained it in detail a few msgs back:

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

(My last disclaimer still holds.)

I do read messages of others.  What I don't understand is exactly what Bruce
didn't: why in the hell that "old heap" is not freed.  For this to happen,
there must be some "small chunks of memory" allocated for Python every other
4M space, and that is ridiculous if all we do is to append things into a
list, without creating a single more variable.  There is another way that
this can happen without the "small chunks of memory": the malloc subsystem
neglected to combine small chunks of contiguous freed memory.  "Perhaps it
is really so horribly broken."

Regards,
Isaac.



More information about the Python-list mailing list