memory recycling/garbage collecting problem

[Christian Heimes]

Tim Wintle wrote:
> Basically malloc() and free() are computationally expensive, so Python
> tries to call them as little as possible - but it's quite clever at
> knowing what to do - e.g. if a list has already grown large then python
> assumes it might grow large again and keeps hold of a percentage of the
> memory.

You are almost right. Python's mutable container types like have a
non-linear growth rate.

>From the file listobject.c

/*
This over-allocates proportional to the list size, making room
for additional growth.  The over-allocation is mild, but is
enough to give linear-time amortized behavior over a long
sequence of appends() in the presence of a poorly-performing
system realloc().
The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
*/

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);