[Python-checkins] python/dist/src/Objects listobject.c,2.177,2.178
rhettinger at users.sourceforge.net
rhettinger at users.sourceforge.net
Fri Feb 13 06:36:41 EST 2004
Update of /cvsroot/python/python/dist/src/Objects
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv8586/Objects
Modified Files:
listobject.c
Log Message:
* Optimized list appends and pops by making fewer calls the underlying system
realloc(). This is achieved by tracking the overallocation size in a new
field and using that information to skip calls to realloc() whenever
possible.
* Simplified and tightened the amount of overallocation. For larger lists,
this overallocates by 1/8th (compared to the previous scheme which ranged
between 1/4th to 1/32nd over-allocation). For smaller lists (n<6), the
maximum overallocation is one byte (formerly it could be upto eight bytes).
This saves memory in applications with large numbers of small lists.
* Eliminated the NRESIZE macro in favor of a new, static list_resize function
that encapsulates the resizing logic. Coverting this back to macro would
give a small (under 1%) speed-up. This was too small to warrant the loss
of readability, maintainability, and de-coupling.
* Some functions using NRESIZE had grown unnecessarily complex in their
efforts to bend to the macro's calling pattern. With the new list_resize
function in place, those other functions could be simplified. That is
being saved for a separate patch.
* The ob_item==NULL check could be eliminated from the new list_resize
function. This would entail finding each piece of code that sets ob_item
to NULL and adding a new line to invalidate the overallocation tracking
field. Rather than impose a new requirement on other pieces of list code,
it was preferred to leave the NULL check in place and retain the benefits
of decoupling, maintainability and information hiding (only PyList_New()
and list_sort() need to know about the new field). This approach also
reduces the odds of breaking an extension module.
(Collaborative effort by Raymond Hettinger, Hye-Shik Chang, Tim Peters,
and Armin Rigo.)
Index: listobject.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/listobject.c,v
retrieving revision 2.177
retrieving revision 2.178
diff -C2 -d -r2.177 -r2.178
*** listobject.c 18 Jan 2004 20:31:02 -0000 2.177
--- listobject.c 13 Feb 2004 11:36:39 -0000 2.178
***************
*** 10,31 ****
static int
! roundupsize(int n)
{
! unsigned int nbits = 0;
! unsigned int n2 = (unsigned int)n >> 5;
! /* Round up:
! * If n < 256, to a multiple of 8.
! * If n < 2048, to a multiple of 64.
! * If n < 16384, to a multiple of 512.
! * If n < 131072, to a multiple of 4096.
! * If n < 1048576, to a multiple of 32768.
! * If n < 8388608, to a multiple of 262144.
! * If n < 67108864, to a multiple of 2097152.
! * If n < 536870912, to a multiple of 16777216.
! * ...
! * If n < 2**(5+3*i), to a multiple of 2**(3*i).
! *
! * 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
--- 10,31 ----
static int
! list_resize(PyListObject *self, int newsize)
{
! PyObject **items;
! size_t _new_size;
! /* Bypass realloc() when a previous overallocation is large enough
! to accommodate the newsize. If the newsize is 16 smaller than the
! current size, then proceed with the realloc() to shrink the list.
! */
!
! if (self->allocated >= newsize &&
! self->ob_size < newsize + 16 &&
! self->ob_item != NULL) {
! self->ob_size = newsize;
! return 0;
! }
!
! /* 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
***************
*** 37,55 ****
* provoke them than it used to).
*/
! do {
! n2 >>= 3;
! nbits += 3;
! } while (n2);
! return ((n >> nbits) + 1) << nbits;
! }
!
! #define NRESIZE(var, type, nitems) \
! do { \
! size_t _new_size = roundupsize(nitems); \
! if (_new_size <= ((~(size_t)0) / sizeof(type))) \
! PyMem_RESIZE(var, type, _new_size); \
! else \
! var = NULL; \
! } while (0)
PyObject *
--- 37,55 ----
* provoke them than it used to).
*/
! _new_size = (newsize >> 3) + (self->ob_size < 3 ? 1 : 6) + newsize;
! items = self->ob_item;
! if (_new_size <= ((~(size_t)0) / sizeof(PyObject *)))
! PyMem_RESIZE(items, PyObject *, _new_size);
! else
! items = NULL;
! if (items == NULL) {
! PyErr_NoMemory();
! return -1;
! }
! self->ob_item = items;
! self->ob_size = newsize;
! self->allocated = _new_size;
! return 0;
! }
PyObject *
***************
*** 82,85 ****
--- 82,86 ----
}
op->ob_size = size;
+ op->allocated = size;
_PyObject_GC_TRACK(op);
return (PyObject *) op;
***************
*** 143,147 ****
ins1(PyListObject *self, int where, PyObject *v)
{
! int i;
PyObject **items;
if (v == NULL) {
--- 144,148 ----
ins1(PyListObject *self, int where, PyObject *v)
{
! int i, n = self->ob_size;
PyObject **items;
if (v == NULL) {
***************
*** 149,176 ****
return -1;
}
! if (self->ob_size == INT_MAX) {
PyErr_SetString(PyExc_OverflowError,
"cannot add more objects to list");
return -1;
}
! items = self->ob_item;
! NRESIZE(items, PyObject *, self->ob_size+1);
! if (items == NULL) {
! PyErr_NoMemory();
return -1;
! }
if (where < 0) {
! where += self->ob_size;
if (where < 0)
where = 0;
}
! if (where > self->ob_size)
! where = self->ob_size;
! for (i = self->ob_size; --i >= where; )
items[i+1] = items[i];
Py_INCREF(v);
items[where] = v;
- self->ob_item = items;
- self->ob_size++;
return 0;
}
--- 150,174 ----
return -1;
}
! if (n == INT_MAX) {
PyErr_SetString(PyExc_OverflowError,
"cannot add more objects to list");
return -1;
}
!
! if (list_resize(self, n+1) == -1)
return -1;
!
if (where < 0) {
! where += n;
if (where < 0)
where = 0;
}
! if (where > n)
! where = n;
! items = self->ob_item;
! for (i = n; --i >= where; )
items[i+1] = items[i];
Py_INCREF(v);
items[where] = v;
return 0;
}
***************
*** 468,471 ****
--- 466,470 ----
int d; /* Change in size */
int k; /* Loop index */
+ int s;
#define b ((PyListObject *)v)
if (v == NULL)
***************
*** 518,540 ****
for (/*k = ihigh*/; k < a->ob_size; k++)
item[k+d] = item[k];
! a->ob_size += d;
! NRESIZE(item, PyObject *, a->ob_size); /* Can't fail */
! a->ob_item = item;
}
}
else { /* Insert d items; recycle ihigh-ilow items */
! NRESIZE(item, PyObject *, a->ob_size + d);
! if (item == NULL) {
if (recycle != NULL)
PyMem_DEL(recycle);
- PyErr_NoMemory();
- return -1;
}
! for (k = a->ob_size; --k >= ihigh; )
item[k+d] = item[k];
for (/*k = ihigh-1*/; k >= ilow; --k)
*p++ = item[k];
- a->ob_item = item;
- a->ob_size += d;
}
for (k = 0; k < n; k++, ilow++) {
--- 517,535 ----
for (/*k = ihigh*/; k < a->ob_size; k++)
item[k+d] = item[k];
! list_resize(a, a->ob_size + d);
! item = a->ob_item;
}
}
else { /* Insert d items; recycle ihigh-ilow items */
! s = a->ob_size;
! if (list_resize(a, s+d) == -1) {
if (recycle != NULL)
PyMem_DEL(recycle);
}
! item = a->ob_item;
! for (k = s; --k >= ihigh; )
item[k+d] = item[k];
for (/*k = ihigh-1*/; k >= ilow; --k)
*p++ = item[k];
}
for (k = 0; k < n; k++, ilow++) {
***************
*** 571,575 ****
{
PyObject **items;
! int size, i, j;
--- 566,570 ----
{
PyObject **items;
! int size, i, j, p;
***************
*** 580,586 ****
}
- items = self->ob_item;
-
if (n < 1) {
self->ob_item = NULL;
self->ob_size = 0;
--- 575,580 ----
}
if (n < 1) {
+ items = self->ob_item;
self->ob_item = NULL;
self->ob_size = 0;
***************
*** 592,612 ****
}
! NRESIZE(items, PyObject*, size*n);
! if (items == NULL) {
! PyErr_NoMemory();
! goto finally;
! }
! self->ob_item = items;
for (i = 1; i < n; i++) { /* Start counting at 1, not 0 */
for (j = 0; j < size; j++) {
PyObject *o = PyList_GET_ITEM(self, j);
Py_INCREF(o);
! PyList_SET_ITEM(self, self->ob_size++, o);
}
}
Py_INCREF(self);
return (PyObject *)self;
- finally:
- return NULL;
}
--- 586,602 ----
}
! if (list_resize(self, size*n) == -1)
! return NULL;
!
! p = size;
for (i = 1; i < n; i++) { /* Start counting at 1, not 0 */
for (j = 0; j < size; j++) {
PyObject *o = PyList_GET_ITEM(self, j);
Py_INCREF(o);
! PyList_SET_ITEM(self, p++, o);
}
}
Py_INCREF(self);
return (PyObject *)self;
}
***************
*** 657,662 ****
listextend_internal(PyListObject *self, PyObject *b)
{
! PyObject **items;
! int selflen = PyList_GET_SIZE(self);
int blen;
register int i;
--- 647,651 ----
listextend_internal(PyListObject *self, PyObject *b)
{
! register int selflen = PyList_GET_SIZE(self);
int blen;
register int i;
***************
*** 687,707 ****
blen = PyObject_Size(b);
!
! /* resize a using idiom */
! items = self->ob_item;
! NRESIZE(items, PyObject*, selflen + blen);
! if (items == NULL) {
! PyErr_NoMemory();
Py_DECREF(b);
return -1;
}
- self->ob_item = items;
-
/* populate the end of self with b's items */
for (i = 0; i < blen; i++) {
PyObject *o = PySequence_Fast_GET_ITEM(b, i);
Py_INCREF(o);
! PyList_SET_ITEM(self, self->ob_size++, o);
}
Py_DECREF(b);
--- 676,689 ----
blen = PyObject_Size(b);
! if (list_resize(self, selflen + blen) == -1) {
Py_DECREF(b);
return -1;
}
/* populate the end of self with b's items */
for (i = 0; i < blen; i++) {
PyObject *o = PySequence_Fast_GET_ITEM(b, i);
Py_INCREF(o);
! PyList_SET_ITEM(self, i+selflen, o);
}
Py_DECREF(b);
***************
*** 1842,1846 ****
int nremaining;
int minrun;
! int saved_ob_size;
PyObject **saved_ob_item;
PyObject **empty_ob_item;
--- 1824,1828 ----
int nremaining;
int minrun;
! int saved_ob_size, saved_allocated;
PyObject **saved_ob_item;
PyObject **empty_ob_item;
***************
*** 1878,1883 ****
--- 1860,1867 ----
saved_ob_size = self->ob_size;
saved_ob_item = self->ob_item;
+ saved_allocated = self->allocated;
self->ob_size = 0;
self->ob_item = empty_ob_item = PyMem_NEW(PyObject *, 0);
+ self->allocated = 0;
if (keyfunc != NULL) {
***************
*** 2000,2003 ****
--- 1984,1988 ----
self->ob_size = saved_ob_size;
self->ob_item = saved_ob_item;
+ self->allocated = saved_allocated;
Py_XDECREF(compare);
Py_XINCREF(result);
***************
*** 2272,2282 ****
n = 8; /* arbitrary */
}
! NRESIZE(result->ob_item, PyObject*, n);
! if (result->ob_item == NULL) {
! PyErr_NoMemory();
goto error;
- }
memset(result->ob_item, 0, sizeof(*result->ob_item) * n);
- result->ob_size = n;
/* Run iterator to exhaustion. */
--- 2257,2263 ----
n = 8; /* arbitrary */
}
! if (list_resize(result, n) == -1)
goto error;
memset(result->ob_item, 0, sizeof(*result->ob_item) * n);
/* Run iterator to exhaustion. */
***************
*** 2476,2480 ****
if (value == NULL) {
/* delete slice */
! PyObject **garbage, **it;
int cur, i, j;
--- 2457,2461 ----
if (value == NULL) {
/* delete slice */
! PyObject **garbage;
int cur, i, j;
***************
*** 2516,2522 ****
}
self->ob_size -= slicelength;
! it = self->ob_item;
! NRESIZE(it, PyObject*, self->ob_size);
! self->ob_item = it;
for (i = 0; i < slicelength; i++) {
--- 2497,2501 ----
}
self->ob_size -= slicelength;
! list_resize(self, self->ob_size);
for (i = 0; i < slicelength; i++) {
More information about the Python-checkins
mailing list