Populating huge data structures from disk

[Hrvoje Niksic]

"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;