Populating huge data structures from disk
hniksic at xemacs.org
Wed Nov 7 08:41:04 CET 2007
"Chris Mellon" <arkanes at gmail.com> writes:
> It is a little annoying that there's no way to pre-allocate an
> array. It doesn't over-allocate, either, so building on a few bytes
> at a time is pretty much worst case behavior.
The fine source says:
array_resize(arrayobject *self, Py_ssize_t newsize)
/* This over-allocates proportional to the array 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, 34, 46, 56, 67, 79, ...
* Note, the pattern starts out the same as for lists but then
* grows at a smaller rate so that larger arrays only overallocate
* by about 1/16th -- this is done because arrays are presumed to be more
* memory critical.
_new_size = (newsize >> 4) + (self->ob_size < 8 ? 3 : 7) + newsize;
More information about the Python-list