[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