memory recycling/garbage collecting problem

[Tim Wintle]

On Tue, 2009-02-17 at 17:04 +0100, Christian Heimes wrote:
> 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);

Sorry, I think I didn't phrase myself very well - I was trying to
explain that de-allocation of memory follows different scaling behaviour
to allocation - so a large list that's shrunk is likely to take more
memory than a small list that's grown i.e. the part just above your
quote:


/* 
Bypass realloc() when a previous overallocation is large enough
to accommodate the newsize.  If the newsize falls lower than half
the allocated size, then proceed with the realloc() to shrink the list.
*/
if (allocated >= newsize && newsize >= (allocated >> 1)) {
	assert(self->ob_item != NULL || newsize == 0);
	Py_SIZE(self) = newsize;
	return 0;
}


it's all very clever stuff btw.