[Python-checkins] python/dist/src/Modules arraymodule.c,2.83,2.84

[nnorwitz@users.sourceforge.net]

Update of /cvsroot/python/python/dist/src/Modules
In directory sc8-pr-cvs1:/tmp/cvs-serv6249/Modules

Modified Files:
	arraymodule.c 
Log Message:
SF patch #687598, array.append is sloooow

This improves speed by about 5.6% for me.


Index: arraymodule.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Modules/arraymodule.c,v
retrieving revision 2.83
retrieving revision 2.84
diff -C2 -d -r2.83 -r2.84
*** arraymodule.c	10 Feb 2003 20:45:47 -0000	2.83
--- arraymodule.c	24 Feb 2003 02:08:42 -0000	2.84
***************
*** 14,17 ****
--- 14,63 ----
  #endif /* !STDC_HEADERS */
  
+ /* Shamelessy stolen from listobject.c */
+ 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
+ 	 * 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).
+ 	 */
+ 	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)
+ /* END SHAMELESSLY STOLEN CODE */
+ 
  struct arrayobject; /* Forward */
  
***************
*** 420,425 ****
  		return -1;
  	items = self->ob_item;
! 	PyMem_RESIZE(items, char,
! 		     (self->ob_size+1) * self->ob_descr->itemsize);
  	if (items == NULL) {
  		PyErr_NoMemory();
--- 466,470 ----
  		return -1;
  	items = self->ob_item;
! 	NRESIZE(items, char, (self->ob_size+1) * self->ob_descr->itemsize);
  	if (items == NULL) {
  		PyErr_NoMemory();