Looking for info on Python's memory allocation
jepler at unpythonic.net
jepler at unpythonic.net
Mon Oct 10 23:01:40 EDT 2005
While there may be a discussion somewhere in the archives,
the comments in listobject.c are enlightening too.
/* Ensure ob_item has room for at least newsize elements, and set
* ob_size to newsize. If newsize > ob_size on entry, the content
* of the new slots at exit is undefined heap trash; it's the caller's
* responsiblity to overwrite them with sane values.
* The number of allocated elements may grow, shrink, or stay the same.
* Failure is impossible if newsize <= self.allocated on entry, although
* that partly relies on an assumption that the system realloc() never
* fails when passed a number of bytes <= the number of bytes last
* allocated (the C standard doesn't guarantee this, but it's hard to
* imagine a realloc implementation where it wouldn't be true).
* Note that self->ob_item may change, and even if newsize is less
* than ob_size on entry.
*/
[...]
/* 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, ...
*/
"linear-time amortized behavior" (i.e., that list.append() is O(1) on average)
is the important characteristic you're probably looking for.
CVS source for listobject.c can be seen here:
http://cvs.sourceforge.net/viewcvs.py/python/python/dist/src/Objects/listobject.c?rev=2.227&view=markup
Jeff
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 196 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/python-list/attachments/20051010/6f46ab04/attachment.sig>
More information about the Python-list
mailing list