[Python-Dev] Time for the yearly list.append() panic

[Tim Peters]

c.l.py has rediscovered the quadratic-time worst-case behavior of list.append().  That is, do list.append(x) in a long
loop.  Linux users don't see anything particularly bad no matter how big the loop.  WinNT eventually displays clear
quadratic-time behavior.  Win9x dies surprisingly early with a MemoryError, despite gobs of memory free:  turns out
Win9x allocates hundreds of virtual heaps, isn't able to coalesce them, and you actually run out of *address space* (the
whole 2GB user space gets fragmented beyond hope).  People on other platforms have reported other bad behaviors over the
years.

I don't want to argue about this again <wink>, I just want to know whether the patch below slows anything down on your
oddball box.  It increases the over-allocation amount in several more layers.  Also replaces integer * and / in the
over-allocation computation by bit operations (integer / in particular is very slow on *some* boxes).

Long-term we should teach PyMalloc about Python's realloc() abuses and craft a cooperative solution.

Index: Objects/listobject.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/listobject.c,v
retrieving revision 2.92
diff -c -r2.92 listobject.c
*** Objects/listobject.c	2001/02/12 22:06:02	2.92
--- Objects/listobject.c	2001/05/25 19:04:07
***************
*** 9,24 ****
  #include <sys/types.h>		/* For size_t */
  #endif

! #define ROUNDUP(n, PyTryBlock) \
! 	((((n)+(PyTryBlock)-1)/(PyTryBlock))*(PyTryBlock))

  static int
  roundupsize(int n)
  {
! 	if (n < 500)
  		return ROUNDUP(n, 10);
  	else
! 		return ROUNDUP(n, 100);
  }

  #define NRESIZE(var, type, nitems) PyMem_RESIZE(var, type, roundupsize(nitems))
--- 9,30 ----
  #include <sys/types.h>		/* For size_t */
  #endif

! #define ROUNDUP(n, nbits) \
! 	( ((n) + (1<<(nbits)) - 1) >> (nbits) << (nbits) )

  static int
  roundupsize(int n)
  {
! 	if ((n >> 9) == 0)
! 		return ROUNDUP(n, 3);
! 	else if ((n >> 13) == 0)
! 		return ROUNDUP(n, 7);
! 	else if ((n >> 17) == 0)
  		return ROUNDUP(n, 10);
+ 	else if ((n >> 20) == 0)
+ 		return ROUNDUP(n, 13);
  	else
! 		return ROUNDUP(n, 18);
  }

  #define NRESIZE(var, type, nitems) PyMem_RESIZE(var, type, roundupsize(nitems))