diff options
| author | Raymond Hettinger <python@rcn.com> | 2004-02-14 18:34:46 (GMT) |
|---|---|---|
| committer | Raymond Hettinger <python@rcn.com> | 2004-02-14 18:34:46 (GMT) |
| commit | ab517d2eacba7fec5f31dd25b8e43dca678cda53 (patch) | |
| tree | 9c5c5930186f315128c6979e9159426b2825f7b2 /Objects/listobject.c | |
| parent | 2731ae4d6dbf887c698ba7e62590a4f27df62bb9 (diff) | |
| download | cpython-ab517d2eacba7fec5f31dd25b8e43dca678cda53.zip cpython-ab517d2eacba7fec5f31dd25b8e43dca678cda53.tar.gz cpython-ab517d2eacba7fec5f31dd25b8e43dca678cda53.tar.bz2 | |
Fine tune the speed/space trade-off for overallocating small lists.
The Py2.3 approach overallocated small lists by up to 8 elements.
The last checkin would limited this to one but slowed down (by 20 to 30%)
the creation of small lists between 3 to 8 elements.
This tune-up balances the two, limiting overallocation to 3 elements
(significantly reducing space consumption from Py2.3) and running faster
than the previous checkin.
The first part of the growth pattern (0, 4, 8, 16) neatly meshes with
allocators that trigger data movement only when crossing a power of two
boundary. Also, then even numbers mesh well with common data alignments.
Diffstat (limited to 'Objects/listobject.c')
| -rw-r--r-- | Objects/listobject.c | 11 |
1 files changed, 3 insertions, 8 deletions
diff --git a/Objects/listobject.c b/Objects/listobject.c index 3a84229..a34810e 100644 --- a/Objects/listobject.c +++ b/Objects/listobject.c @@ -30,13 +30,10 @@ list_resize(PyListObject *self, int newsize) * 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() (which is a reality, e.g., across all flavors - * of Windows, with Win9x behavior being particularly bad -- and - * we've still got address space fragmentation problems on Win9x - * even with this scheme, although it requires much longer lists to - * provoke them than it used to). + * system realloc(). + * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ... */ - _new_size = (newsize >> 3) + (self->ob_size < 3 ? 1 : 6) + newsize; + _new_size = (newsize >> 3) + (self->ob_size < 8 ? 3 : 6) + newsize; items = self->ob_item; if (_new_size <= ((~(size_t)0) / sizeof(PyObject *))) PyMem_RESIZE(items, PyObject *, _new_size); @@ -316,8 +313,6 @@ list_length(PyListObject *a) return a->ob_size; } - - static int list_contains(PyListObject *a, PyObject *el) { |