Python 2.0b1 List comprehensions are slow

[Kevin O'Connor]

In article <cppum9bf62.fsf at cj20424-a.reston1.va.home.com> you write:
>Another way to look at this is: the list comprehension is a really
>nice notation to replace a for loop with a list.append() call, with
>currently only a slight optimization.
>
>Look at [x+12 for x in a] as a really nice way to spell
>
>    L = []
>    for x in a: L.append(x+12)
>
>and then using L.
>
>Ways to optimize this (in 2.1; as Tim explained 2.0 is too close to
>release) might include:

Well, it is your call, but the patch attached to this message speeds up
list comprehensions by as much as 30% for me.  The patch works by reducing
the number of calls to realloc() during repeated append() operations.  The
current code does preallocation of memory as the list grows (up to 10 items
on small lists, and up to 100 on big lists), but an append operation always
calls realloc even when the size of the list isn't going to be increased.
(In essence, it is just an expensive no-op.)

The patch makes the following three changes:
 - on a list size alteration, it will only call realloc() if the memory
 allocation is indeed going to be increased/decreased.
 - on a call to PyList_New() allocations are padded to the nearest 10 items
 (for small lists, 128 items on big lists).  This is done so the above can
 work.
 - I upped the padding size on big lists (> 500 items) to 128 from 100 - I
 believe this will help reduce memory fragmentation on big lists.

To be clear, though, even with this patch applied, map+lambda is still
faster than a list comprehension, but the margin is much smaller.  Also,
this patch improves all repeated append() calls - so for loops that use
append also benefit from it.

-Kevin

Patch follows, sorry if this isn't the right forum for sending patches.  It
is only 135 lines though..

--- Python-2.0b1/Objects/listobject.c.orig	Mon Sep 11 22:06:53 2000
+++ Python-2.0b1/Objects/listobject.c	Tue Sep 12 19:57:23 2000
@@ -15,30 +15,38 @@
 #define ROUNDUP(n, PyTryBlock) \
 	((((n)+(PyTryBlock)-1)/(PyTryBlock))*(PyTryBlock))
 
+#define roundupsize(n) (((n) < 500) ? ROUNDUP((n),10) : ROUNDUP((n),128))
+
 static int
-roundupsize(int n)
+listsetsize(PyListObject *l, int newsize)
 {
-	if (n < 500)
-		return ROUNDUP(n, 10);
-	else
-		return ROUNDUP(n, 100);
-}
+    int curpadsize, newpadsize;
 
-#define NRESIZE(var, type, nitems) PyMem_RESIZE(var, type, roundupsize(nitems))
+    curpadsize = roundupsize(l->ob_size);
+    newpadsize = roundupsize(newsize);
+    if (newpadsize != curpadsize) {
+	PyMem_RESIZE(l->ob_item, PyObject *, newpadsize);
+	if (l->ob_item == NULL)
+	    return 0;
+    }
+    return 1;
+}
 
 PyObject *
 PyList_New(int size)
 {
 	int i;
+	int upsize;
 	PyListObject *op;
 	size_t nbytes;
 	if (size < 0) {
 		PyErr_BadInternalCall();
 		return NULL;
 	}
-	nbytes = size * sizeof(PyObject *);
+	upsize = roundupsize(size);
+	nbytes = upsize * sizeof(PyObject *);
 	/* Check for overflow */
-	if (nbytes / sizeof(PyObject *) != (size_t)size) {
+	if (nbytes / sizeof(PyObject *) != (size_t)upsize) {
 		return PyErr_NoMemory();
 	}
 	/* PyObject_NewVar is inlined */
@@ -133,12 +141,11 @@
 			"cannot add more objects to list");
 		return -1;
 	}
-	items = self->ob_item;
-	NRESIZE(items, PyObject *, self->ob_size+1);
-	if (items == NULL) {
+	if (! listsetsize(self, self->ob_size+1)) {
 		PyErr_NoMemory();
 		return -1;
 	}
+	items = self->ob_item;
 	if (where < 0)
 		where = 0;
 	if (where > self->ob_size)
@@ -147,7 +154,6 @@
 		items[i+1] = items[i];
 	Py_INCREF(v);
 	items[where] = v;
-	self->ob_item = items;
 	self->ob_size++;
 	return 0;
 }
@@ -443,24 +449,23 @@
 		if (d < 0) {
 			for (/*k = ihigh*/; k < a->ob_size; k++)
 				item[k+d] = item[k];
+			listsetsize(a, a->ob_size + d); /* Can't fail */
 			a->ob_size += d;
-			NRESIZE(item, PyObject *, a->ob_size); /* Can't fail */
-			a->ob_item = item;
+			item = a->ob_item;
 		}
 	}
 	else { /* Insert d items; recycle ihigh-ilow items */
-		NRESIZE(item, PyObject *, a->ob_size + d);
-		if (item == NULL) {
+		if (! listsetsize(a, a->ob_size + d)) {
 			if (recycle != NULL)
 				PyMem_DEL(recycle);
 			PyErr_NoMemory();
 			return -1;
 		}
+		item = a->ob_item;
 		for (k = a->ob_size; --k >= ihigh; )
 			item[k+d] = item[k];
 		for (/*k = ihigh-1*/; k >= ilow; --k)
 			*p++ = item[k];
-		a->ob_item = item;
 		a->ob_size += d;
 	}
 	for (k = 0; k < n; k++, ilow++) {
@@ -512,12 +517,11 @@
 		return (PyObject *)self;
 	}
 
-	NRESIZE(items, PyObject*, size*n);
-	if (items == NULL) {
+	if (! listsetsize(self, size*n)) {
 		PyErr_NoMemory();
 		goto finally;
 	}
-	self->ob_item = items;
+	items = self->ob_item;
 	for (i = 1; i < n; i++) { /* Start counting at 1, not 0 */
 		for (j = 0; j < size; j++) {
 			PyObject *o = PyList_GET_ITEM(self, j);
@@ -624,15 +628,12 @@
 	blen = PyObject_Size(b);
 
 	/* resize a using idiom */
-	items = self->ob_item;
-	NRESIZE(items, PyObject*, selflen + blen);
-	if (items == NULL) {
+	if (! listsetsize(self, selflen + blen)) {
 		PyErr_NoMemory();
 		Py_DECREF(b);
 		return -1;
 	}
-
-	self->ob_item = items;
+	items = self->ob_item;
 
 	/* populate the end of self with b's items */
 	for (i = 0; i < blen; i++) {


-- 
 ------------------------------------------------------------------------
 | Kevin O'Connor                     "BTW, IMHO we need a FAQ for      |
 | koconnor at cse.buffalo.edu            'IMHO', 'FAQ', 'BTW', etc. !"    |
 ------------------------------------------------------------------------