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

Tim Peters tim.one@home.com
Fri, 25 May 2001 15:06:16 -0400

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 , 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);

! return ROUNDUP(n, 18); }

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