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))
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4