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.
--
http://mail.python.org/mailman/listinfo/python-list
