list.pop(0) vs. collections.dequeue

[Steve Howell]

On Jan 23, 4:12 am, Steven D'Aprano <st... at REMOVE-THIS-
cybersource.com.au> wrote:
> On Fri, 22 Jan 2010 21:42:43 -0800, Steve Howell wrote:
> > This innocent program here literally moves about a million bytes of
> > memory around for no good reason:
>
> >     lst = []
> >     for i in range(2000):
> >         lst.append(i)
> >     while lst:
> >         print lst.pop(0)
>
> > Why?  Because list.pop(0) is implemented in O(N) instead of O(1).
>
> > Why wouldn't you get a competent C programmer simply make list_ass_slice
> > smart enough to make list.pop(0) O(1)?
>
> Because there are always trade-offs, and the competent C programmers who
> coded the implementation for lists choose different tradeoffs to the ones
> you would prefer.
>
> Seems to me that the simple solution to your problem is for you to
> implement your own data structure that makes whatever trade-offs you
> like. If it is good enough and popular enough, it might even replace the
> existing list implementation.
>

The data structure that would make the tradeoffs I want would be
implemented within CPython itself.  I give a sketch of the changes
elsewhere in this thread.

Terry Reedy said:

'''
If you try writing a full patch, as I believe someone did, or at least
a
prototype thereof, when the idea was discussed, you might have a
better
idea of what the tradeoffs are and why it was rejected.
'''

I have to run, but tomorrow I will try to dig through python-dev
archives and find the patch.  If anybody has hints on where to look
for it (anybody remember the author, for example?), it would be much
appreciated.

If the patch looks simple, I will try to pitch the idea that its time
has come.  Now that the specification of the language itself is
frozen, I think there might be more room for improving
implementations.  Also, I might be able to make the argument that
tradeoffs of memory vs. CPU vs. code complexity have different forces
in the 2010s.

Thanks for your reply.