[Python-checkins] python/dist/src/Objects listobject.c,2.222,2.223

[rhettinger at users.sourceforge.net]

Update of /cvsroot/python/python/dist/src/Objects
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv20608

Modified Files:
	listobject.c 
Log Message:
SF #1022910: Conserve memory with list.pop()

The list resizing scheme only downsized when more than 16 elements were
removed in a single step:  del a[100:120].   As a result, the list would
never shrink when popping elements off one at a time.

This patch makes it shrink whenever more than half of the space is unused.

Also, at Tim's suggestion, renamed _new_size to new_allocated.  This makes
the code easier to understand.



Index: listobject.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/listobject.c,v
retrieving revision 2.222
retrieving revision 2.223
diff -u -d -r2.222 -r2.223
--- listobject.c	10 Sep 2004 12:59:54 -0000	2.222
+++ listobject.c	12 Sep 2004 19:53:07 -0000	2.223
@@ -25,13 +25,14 @@
 list_resize(PyListObject *self, int newsize)
 {
 	PyObject **items;
-	size_t _new_size;
+	size_t new_allocated;
+	int allocated = self->allocated;
 
 	/* 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.
+	   to accommodate the newsize.  If the newsize falls lower than half
+	   the allocated size, then proceed with the realloc() to shrink the list.
 	*/
-	if (self->allocated >= newsize && self->ob_size < newsize + 16) {
+	if (allocated >= newsize && newsize >= (allocated >> 1)) {
 		assert(self->ob_item != NULL || newsize == 0);
 		self->ob_size = newsize;
 		return 0;
@@ -44,10 +45,12 @@
 	 * system realloc().
 	 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
 	 */
-	_new_size = (newsize >> 3) + (self->ob_size < 8 ? 3 : 6) + newsize;
+	new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6) + newsize;
+	if (newsize == 0)
+		new_allocated = 0;
 	items = self->ob_item;
-	if (_new_size <= ((~(size_t)0) / sizeof(PyObject *)))
-		PyMem_RESIZE(items, PyObject *, _new_size);
+	if (new_allocated <= ((~(size_t)0) / sizeof(PyObject *)))
+		PyMem_RESIZE(items, PyObject *, new_allocated);
 	else
 		items = NULL;
 	if (items == NULL) {
@@ -56,7 +59,7 @@
 	}
 	self->ob_item = items;
 	self->ob_size = newsize;
-	self->allocated = _new_size;
+	self->allocated = new_allocated;
 	return 0;
 }