list.pop(0) vs. collections.dequeue

[Paul Rubin]

Steve Howell <showell30 at yahoo.com> writes:
> Proposal: Improve list's implementation so that deleting elements from
> the front of the list does not require an O(N) memmove operation. ...
> It is possible now, of course, to use a data structure in
> Python that has O(1) for deleting off the top of the list, but none of
> the alternatives fully replicate the benefits of list itself.

I think you are mostly referring to deque.  Why don't you instead
say what you think is wrong with using deque, and how deque can
be improved?

> See above.  An implementation of this PEP would not change the
> definition of the language in any way, but it would have to minimally
> impact the performance of lists for the normal use cases.

But you're talking about adding one or two words to EVERY list, and many
normal use cases allocate a LOT of lists.  Those use cases are likely
more common than use cases that pop from the front of the list but for
some reason can't use deque.

> The most ambitious proposal is to fix the memory manager itself to
> allow the release of memory from the start of the chunk. 

That's inappropriate given the memory fragmentation it would cause.

Really, you're describing a problem that arises in a few programs but up
til now, as far as I know, everyone has found deque to be an adequate
solution.  Your approach of snarling against list is not persuading
anyone that list needs to be changed, because most everyone is satisfied
with the existing solution.  You might change approaches and discuss
deque, what's wrong with it, and whether it can be fixed.  Getting a
change approved for deque is probably much easier than getting one
approved for list, just because nowhere near as many things depend on
deque's performance.  And when discussing performance in this context,
additive constants do matter.