list.pop(0) vs. collections.dequeue

Steve Howell showell30 at
Sat Jan 23 09:54:19 CET 2010

On Jan 23, 12:32 am, "Alf P. Steinbach" <al... at> wrote:
> * Steve Howell:
> > On Jan 23, 12:13 am, Terry Reedy <tjre... at> wrote:
> >> Challenge yes, mock no.
> >> Part of writing good basic data structures is not adding needless
> >> complication from featuritis and not penalizing 99.99% of access to
> >> satify a .01% need better satisfied another way.
> > I would like to challenge your assertion that advancing ob_item
> > instead of doing memmove during list_ass_slice would impact the
> > performance of list accesses in any way.  It would only slow down
> > operations that add/insert items into the list by, and then only by a
> > single conditional statement, and those add/insert operations are
> > already O(N) to begin with.
> I'm sorry, no, the last part is incorrect.
> Appending to a 'list' can currently be constant time, if OS reallocation is
> constant time (as the string '+' optimization relies on).

That's true, but it's also irrelevant, as the pop optimization would
happen in a branch of code that never gets executed during list

	if (d < 0) { /* Delete -d items */
                /* ADD CODE HERE TO AVOID memmove
                   when ilow == 0 (i.e. ihigh + d == 0)
		memmove(&item[ihigh+d], &item[ihigh],
			(Py_SIZE(a) - ihigh)*sizeof(PyObject *));
		list_resize(a, Py_SIZE(a) + d);
		item = a->ob_item;

> With the pop optimization it can no longer be constant time without risking an
> accumulation of unused memory, a memory leak, although it can be amortized
> constant time, at the cost of wasting some percentage of memory.

list_resize already overallocates memory to allow room for growth.
Whenever you did an append to the list that would force a realloc, you
could first check to see if there is unused stuff at the front and do
the memmove then and reclaim the unfreed memory.  So instead of doing
a paying for memmove on every pop, you only pay for it when the list
goes to size 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, etc.


More information about the Python-list mailing list