Abstract

Operations on lists that insert/delete elements at the end of the list are not symmetric in CPython. Inserting/deleting from the end is O(1); inserting/deleting at the beginning is O(N). This proposal attempts to improve performance for remove operations at the front of the list to an O(1) operation by lazily releasing memory. Insertions are still tricky to make O(1), but they can be made to at least reclaim space from lazy removes.

Motivation

The author of the patch discovered the admonition against using pop(0) in the tutorial and had used it in some of his own programs, notably parsers.

Here are the proposed benefits:

Rationale

The rationale for improving the speed of list removes should be fairly self-evident; the merits of the proposal then need to be measured against the tradeoffs required to gain that speed.

Many objections have been presented:

The objection on grounds of simplicity is the hardest to counter, except to say that the proposed patch is fairly small and non-invasive.

The objection that Python programmers will be "spoiled" by a fast implementation is a rather thin objection.

The alternatives to list, deque and blist, do not replicate all the features of list. Both come pretty close, though. Of course, the existence of alternatives to list does not justify keeping list itself crippled, as list is a data structure that many Python programmers naturally pick, without regard to performance, only to find out down the road that they are using list on larger and larger sets of data.

Postponing the release of memory after popping the first element off the list is wasteful, but in the alternative scenario, users would be avoiding pop(0) in the first place and needlessly tying up memory not only for the list pointers, but the list elements themselves (although they could set elements to None). The patch does limit the number of orphan pointers, and it does reclaim orphans when new elements gets inserted to the front of the list.

The changes to PyList_new and list_dealloc are small, and those methods only get called once during the lifetime of a list. The changes to list_resize would be the most likely to counteract other speedup gains.

Although memmove() is rarely the largest bottleneck in a Python program, every little speedup counts.

The assertion that current large Python programs today do not tend to pop elements off the top of the list is hard to verify for sure.

The patch does not break the public interface for third party extensions.

Implementation

SteveHowell submitted the first draft of a fix, which you can find here.

http://codereview.appspot.com/194083/show

For a small test program the patch produces a 100X speedup.

ProposalToSpeedUpListOperations (last edited 2010-01-27 21:28:19 by 71-22-158-98)

Unable to edit the page? See the FrontPage for instructions.