[Python-checkins] python/dist/src/Objects listobject.c,2.180,2.181

Sat Feb 14 13:34:49 EST 2004

Update of /cvsroot/python/python/dist/src/Objects
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv945/Objects
Modified Files:
	listobject.c 
Log Message:
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.
Index: listobject.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/listobject.c,v
retrieving revision 2.180
retrieving revision 2.181
diff -C2 -d -r2.180 -r2.181
*** listobject.c	14 Feb 2004 03:07:21 -0000	2.180
--- listobject.c	14 Feb 2004 18:34:46 -0000	2.181
***************
*** 31,41 ****
 	 * 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).
 	 */
! 	_new_size = (newsize >> 3) + (self->ob_size < 3 ? 1 : 6) + newsize;
 	items = self->ob_item;
 	if (_new_size <= ((~(size_t)0) / sizeof(PyObject *)))
--- 31,38 ----
 	 * 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, 35, 46, 58, 72, 88, ...
 	 */
! 	_new_size = (newsize >> 3) + (self->ob_size < 8 ? 3 : 6) + newsize;
 	items = self->ob_item;
 	if (_new_size <= ((~(size_t)0) / sizeof(PyObject *)))
***************
*** 317,322 ****
 }
 
- 
- 
 static int
 list_contains(PyListObject *a, PyObject *el)
--- 314,317 ----