list.pop(0) vs. collections.dequeue

[Steve Howell]

Why would you do that? I can think of at least eight different
implementations of the abstract list data structure:

constant-size array
variable-size array
variable-size array with amortised O(1) appends
singly-linked list
singly-linked list with CDR coding
doubly-linked list
skip list
indexable skip list

One can reasonably disregard constant-sized arrays as a possibility,
given that Python lists aren't fixed size (pity the poor Pascal and
Fortran coders who are stuck with static arrays!), but the rest are all
reasonable possibilities. Why assume one specific implementation in the
absence of documentation promising certain performance characteristics?


Exactly


There are quite a few problems with having the documentation specify cost:

(1) Who is going to do it? Any volunteers?

(2) Big-oh notation can be misleading, especially for naive users, or
those whose intuition for what's fast has been shaped by other languages.
Big-oh doesn't tell you whether something is fast or slow, only how it
scales -- and sometimes not even then.

(3) Having documented a particular performance, that discourages
implementation changes. Any would-be patch or new implementation not only
has to consider that the functional behaviour doesn't change, but that
the performance doesn't either.

In practice the Python developers are unlikely to make an implementation
change which leads to radically worse performance, particularly for
critical types like list and dict. But in other cases, they might choose
to change big-oh behaviour, and not wish to be tied down by documentation
of the cost of operations.

(4) How much detail is necessary? What about degenerate cases? E.g. dict
lookup in CPython is typically O(1) amortised, but if all the keys hash
to the same value, it falls to O(N).

(5) Should the language guarantee such degenerate behaviour? Who decides
which costs are guaranteed and which are not?

(6) Such performance guarantees should be implementation specific, not
language specific. CPython is only one implementation of the language out
of many.

Bringing this thread full circle, does it make sense to strike this
passage from the tutorial?:

'''
It is also possible to use a list as a queue, where the first element
added is the first element retrieved (“first-in, first-out”); however,
lists are not efficient for this purpose. While appends and pops from
the end of list are fast, doing inserts or pops from the beginning of
a list is slow (because all of the other elements have to be shifted
by one).
'''

I think points #3 and #6 possibly apply. Regarding points #2 and #4,
the tutorial is at least not overly technical or specific; it just
explains the requirement to shift other elements one by one in simple
layman's terms.

 

[Aahz]

Here is a benchmark of O(N*N) vs. O(N) for two C programs. One does
memmove; the other simply advances the pointer.

You should provide pybench numbers and probably also use the benchmarks
produced by the Unladen Swallow project. The next step is to file a
patch on bugs.python.org and request review.

 

[Roy Smith]

The page you should probably be looking at is
http://wiki.python.org/moin/TimeComplexity

I was not aware of this page; thanks for pointing it out.

 

[Terry Reedy]

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.

The approach you outlined in your other response to me is, I believe,
what was considered, investigated, and then rejected (by Guido, with
agreement). The discussion may have been on the now-closed and
(misspelled) pyk3 (?), or maybe on python-ideas, but my memory is more
likely the former. I am sure that Raymond H. was involved also.

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.

I am not opposed to a possible change, just hasty, ill-informed
criticism. If there is not a PEP on this issue, it would be good to have
one that recorded the proposal and the pros and cons, regardless of the
outcome, so there would be something to refer people to. If that had
been already done, it would have shortened this thread considerably.

Terry Jan Reedy

 

[Terry Reedy]

I was not aware of this page; thanks for pointing it out.

Perhaps you could suggest on the tracker a place or places in the doc
where this relatively new wiki page could be referred to. Perhaps in the
introductory paragraphs of the Built-in Type section of the lib ref.
Where would you have like to have found it?

The page was added in response to threads like this one, but it
obviously is more obscure than it should be.

Terry Jan Reedy

 

[Roy Smith]

I was not aware of this page; thanks for pointing it out.

Perhaps you could suggest on the tracker a place or places in the doc
where this relatively new wiki page could be referred to. Perhaps in the
introductory paragraphs of the Built-in Type section of the lib ref.
Where would you have like to have found it?[/QUOTE]

I think the most logical place would have been right at the table of
operations (http://tinyurl.com/cdbwog).

 

[Raymond Hettinger]

[Steve Howell]

Why wouldn't you get a competent C programmer simply make
list_ass_slice smart enough to make list.pop(0) O(1)?

When this suggestion was discussed on python-dev years ago,
it was rejected. One reason is that it was somewhat
common for C code to access the list data structure directly
(bypassing API accessor functions). Changing the list to have
a starting offset would break existing C extensions.

Another reason is that Guido is non-tolerant of space or time
trade-offs for lists and tuples because they pervade the language
and are heavily used internally. Any additional space or time
requirement however small would impact the language performance
as a whole. FWIW, that is also the reason that lists are not
weak-referenceable (it would cost one extra pointer field per
instance and that wasn't deemed to be worth it).

The brilliant computer scientist, Christian Heimes, provides the
answers, and I am paraphrasing here, of course:

IMHO, Christian IS a brilliant computer scientist, so I'll ignore
the rude intention and take the sentence literally.

  1) You can save 64 bits for every list by not storing an extra
pointer!
  2) You can simplify the CPython implementation!
  3) You can avoid the oh-so-expensive check "if ilow == 1" for all
operations that don't need this optimization!

Sounds like two micro-optimizations to me (and a copout to boot).

Micro or not, these reasons were part of Guido's rationale.
Tim Peters and I also participated in the conversation and did not
disagree.

So, collections.deque() was born and the problem stopped being an
issue.
Also, Daniel Stuzbach has published a blist implementation that offers
high performance insertions and deletions and fast handling of sparse
lists.


Raymond

 

[Steve Howell]

[Steve Howell]

Why wouldn't you get a competent C programmer simply make
list_ass_slice smart enough to make list.pop(0) O(1)?

When this suggestion was discussed on python-dev years ago,
it was rejected.  One reason is that it was somewhat
common for C code to access the list data structure directly
(bypassing API accessor functions).  Changing the list to have
a starting offset would break existing C extensions.

Another reason is that Guido is non-tolerant of space or time
trade-offs for lists and tuples because they pervade the language
and are heavily used internally.  Any additional space or time
requirement however small would impact the language performance
as a whole.  FWIW, that is also the reason that lists are not
weak-referenceable (it would cost one extra pointer field per
instance and that wasn't deemed to be worth it).

The brilliant computer scientist, Christian Heimes, provides the
answers, and I am paraphrasing here, of course:

IMHO, Christian IS a brilliant computer scientist, so I'll ignore
the rude intention and take the sentence literally.

You are also a brilliant computer scientist, despite the fact that you
are defending a list implemenation that can't pop the first element
off the list in O(1) time.

 

[Steven D'Aprano]

You are also a brilliant computer scientist, despite the fact that you
are defending a list implemenation that can't pop the first element off
the list in O(1) time.

You say that like it's a bad thing.

It's very simple: the trade-offs that the Python development team have
deliberately chosen aren't the same trade-offs that you prefer. That
doesn't make your trade-offs right and Python's wrong. They're just
different, and if Python lists had your preferred implementation, I
guarantee that somebody would be complaining about it right now.

If you're serious about wanting O(1) pops from the start of the list,
write your own list implementation and use it. You might even like to
make it public, so others can use it as well. But please stop with the
snide remarks and poorly disguised insults and back-handed compliments,
it's getting tedious.

Or just change your algorithm slightly -- it's not hard to turn an
algorithm that pops from the start of a list to one that pops from the
end of the list.

 

[Steve Howell]

You say that like it's a bad thing.

It is.

It's very simple: the trade-offs that the Python development team have
deliberately chosen aren't the same trade-offs that you prefer. That
doesn't make your trade-offs right and Python's wrong. They're just
different, and if Python lists had your preferred implementation, I
guarantee that somebody would be complaining about it right now.

If you're serious about wanting O(1) pops from the start of the list,
write your own list implementation and use it. You might even like to
make it public, so others can use it as well. But please stop with the
snide remarks and poorly disguised insults and back-handed compliments,
it's getting tedious.

I will stop being snide, but I will be blunt, and if anybody
interprets my criticism as an insult, so be it.

The current algorithm is broken. It's a 20th century implementation
of lists built on top of a 20th century memory manager. It's at least
ten years behind the times.

Or just change your algorithm slightly -- it's not hard to turn an
algorithm that pops from the start of a list to one that pops from the
end of the list.

The fact that you are proposing to reverse a list to work around its
performance deficiencies just confirms to me that the algorithm is
broken. I will concede the fact that most of CPython's tradeoffs are
driven by the limitations of the underlying memory manager. If realloc
() allowed you to easily release memory from the front of a previously
allocated block, we'd be talking about maybe a 10-line patch here, and
it wouldn't impact even list_resize() in a meaningful way.

Even with realloc()'s brokenness, you could improve pop(0) in a way
that does not impact list access at all, and the patch would not
change the time complexity of any operation; it would just add
negligible extract bookkeeping within list_resize() and a few other
places.

The objection that the extra pointer would increase the size of list
objects is totally 20th century thinking. It would be totally
negligible for any real world program.

 

[Steve Howell]

The approach you outlined in your other response to me is, I believe,
what was considered, investigated, and then rejected (by Guido, with
agreement). The discussion may have been on the now-closed and
(misspelled) pyk3 (?), or maybe on python-ideas, but my memory is more
likely the former. I am sure that Raymond H. was involved also.


I am not opposed to a possible change, just hasty, ill-informed
criticism. If there is not a PEP on this issue, it would be good to have
one that recorded the proposal and the pros and cons, regardless of the
outcome, so there would be something to refer people to. If that had
been already done, it would have shortened this thread considerably.

I think it's a good idea to write a PEP on this issue, and I will
attempt a first draft. I think I should submit the first draft to
python-ideas, correct?

I expect the PEP to be at least initially, if not permanently,
rejected, but it would not be an exercise in futility, as I agree it's
good to record pros and cons of the proposal in one place. The PEP
probably would not include a proposed patch until there was a little
bit of consensus behind it, but it would not take me a lot of time to
present the basic argument.

Here is my sketch of what the PEP would look like.

Proposal: Improve list's implementation so that deleting elements from
the front of the list does not require an O(N) memmove operation.

Rationale: Some Python programs that process lists have multiple
methods that consume the first element of the list and pop it off.
The pattern comes up with parsers in particular, but there are other
examples. 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.

Specification: Improving CPython's performance does not affect the
language itself, so there are no bikeshed arguments to be had with
respect to syntax, etc. Any patch would, of course, affect the
performance of nearly every Python program in existence, so any patch
would have to, at a bare minimum:

1) Not increase the time or memory complexity of any other list
operation.
2) Not affect list access at all.
3) Minimally affect list operations that mutate the list.
4) Be reasonably simple within CPython itself.
5) Not be grossly wasteful of memory.

Backwards Compatibility:

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.

Implementation:

There are two ways to make deleting the first item of the list run
more efficiently.

The most ambitious proposal is to fix the memory manager itself to
allow the release of memory from the start of the chunk. The
advantage of this proposal is that it would simplify the changes to
list itself, and possibly have collateral benefits for other CPython
internal data structures. The disadvantage of the proposal is that
there is a strong tradition in CPython to use native memory
management, particularly with respect to the fact that it runs on many
platforms.

The less ambitious proposal is to change the memory management scheme
within list itself. There is already precedent in list_resize() to
optimistically allocate memory, so it is not a great break from
tradition to optimistically defer the release of memory. But it would
complicate things.

References:

I would refer to this thread on comp.lang.python for discussion, and I
would also try to dig up older threads on python-dev or elsewhere.

 

[Aahz]

Even with realloc()'s brokenness, you could improve pop(0) in a way
that does not impact list access at all, and the patch would not change
the time complexity of any operation; it would just add negligible
extract bookkeeping within list_resize() and a few other places.

Again, your responsibility is to provide a patch and a spectrum of
benchmarking tests to prove it. Then you would still have to deal with
the objection that extensions use the list internals -- that might be an
okay sell given the effort otherwise required to port extensions to
Python 3, but that's not the way to bet.

Have you actually read the discussions you were pointed at?

 

[Steve Howell]

Again, your responsibility is to provide a patch and a spectrum of
benchmarking tests to prove it.  Then you would still have to deal with
the objection that extensions use the list internals -- that might be an
okay sell given the effort otherwise required to port extensions to
Python 3, but that's not the way to bet.
Ok.

Have you actually read the discussions you were pointed at?

I don't think anybody provided an actual link, but please correct me
if I overlooked it.

 

[Terry Reedy]

I think it's a good idea to write a PEP on this issue, and I will
attempt a first draft. I think I should submit the first draft to
python-ideas, correct?

That is not a *requirement* for drafts in general, but it is a good idea
for a community or community-person generated proposal, such as this one.

I expect the PEP to be at least initially, if not permanently,
rejected,

Guido sometimes rejects 'no-chance' proposals without waiting to be
asked, but he usually waits until the PEP author feels the issue is ripe
and asks for a pronouncement.

tjr

 

[Paul Rubin]

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.

 

[Daniel Stutzbach]

I don't think anybody provided an actual link, but please correct me
if I overlooked it.

I have to wonder if my messages are all ending up in your spam folder
for some reason.

PEP 3128 (which solves your problem, but not using the implementation
you suggest)
http://www.python.org/dev/peps/pep-3128/

Implementation as an extension module:
http://pypi.python.org/pypi/blist/

Related discussion:
http://mail.python.org/pipermail/python-3000/2007-April/006757.html
http://mail.python.org/pipermail/python-3000/2007-May/007491.html

Detailed performance comparison:
http://stutzbachenterprises.com/performance-blist

I maintain a private fork of Python 3 with the blist replacing the
regular list, as a way of rigorously testing the blist implementation.

Although I originally proposed a PEP, I am content to have the blist
exist as a third-party module.

 

[Steve Howell]

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?

There is nothing wrong with deque, at least as far as I know, if the
data strucure actually applies to your use case. It does not apply to
my use case.

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.

For EVERY list, you are not only allocating memory for the list
itself, but you are also allocating memory for the objects within the
list. So the extra one or two words are NEGLIGIBLE.

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

Bullshit. Memory managers consolidate free memory chunks all the
time. That's their job.

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.  

Wrong. Many programs delete the first element of the list.

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.  

Please provide evidence of that. I am pretty sure that everybody who
chooses alternatives to Python would disagree.

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.  

Again...I am not looking to improve deque, which is a perfectly valid
data structure for a limited set of problems.

And when discussing performance in this contextc
additive constants do matter.

Wrong again. Operations that mutate lists are already expensive, and
a few checks to see if unreleased memory can be reclaimed are totally
NEGLIGIBLE.

 

[Steven D'Aprano]

Bullshit. Memory managers consolidate free memory chunks all the time.
That's their job.

So let me get this straight...

You've complained that Python's list.pop(0) is lame because it moves
memory around. And your solution to that is to have the memory manager
move the memory around instead?

Perhaps I'm missing something, but I don't see the advantage here. At
best, you consolidate all those moves you wanted to avoid and do them all
at once instead of a few at a time. At worst, you get a situation where
the application periodically, and unpredictably, grinds to a halt while
the memory manager tries to defrag all those lists.

Wrong. Many programs delete the first element of the list.

I'm sure they do. Many programs do all sorts of things, of varying
sensibleness. But I'm pretty sure I've never written a program that
deleted the first element of a list. Even if I have, it's a vanishingly
small use-case for me. YMMV.

Please provide evidence of that. I am pretty sure that everybody who
chooses alternatives to Python would disagree.

Do you honestly believe that "everybody" who prefers another language
over Python does so because they dislike the performance of list.pop(0)?

Again...I am not looking to improve deque, which is a perfectly valid
data structure for a limited set of problems.


Wrong again. Operations that mutate lists are already expensive, and a
few checks to see if unreleased memory can be reclaimed are totally
NEGLIGIBLE.

Popping from the end of the list isn't expensive. Reversing lists is
relatively cheap. In-place modifications are very cheap.

 

[Paul Rubin]

There is nothing wrong with deque, at least as far as I know, if the
data strucure actually applies to your use case. It does not apply to
my use case.

You haven't explained why deque doesn't apply to your use case. Until a
convincing explanation emerges, the sentiment you're creating seems to
be "what's wrong with that guy and why doesn't he just use deque?". So,
why aren't you using deque? If deque somehow isn't adequate for your
use case, maybe it can be improved.

Please provide evidence of that. I am pretty sure that everybody who
chooses alternatives to Python would disagree.

I've heard of many reasons to choose alternatives to Python, and have
chosen alternatives to Python in various situations myself. The
list.pop(0) issue has never been one of those reasons for me or anyone
else I know of to choose an alternative until you came along. Anyway,
you're welcome to switch to another language; nobody's heart will be
broken if you do that. I'd be interested to know which languages handle
list.pop(0) the way you're proposing for Python.

Wrong again. Operations that mutate lists are already expensive

I'm talking about memory consumption, which is part of Python's concept
of performance. You're proposing adding a word or two to every list,
with insufficient justification presented so far. Any such
justification would have to include a clear and detailed explanation of
why using deque is insufficient, so that would be a good place to start.

On another note: the idea you're suggesting, while not yet 100%
convincing, is not crazy, which is why people are willing to discuss it
with you reasonably. But your confrontational style is making
discussion unpleasant. Can you dial it back a little? Your current
approach is perhaps leading you towards people's ignore lists.

 

[Antoine Pitrou]

Le Sun, 24 Jan 2010 11:28:53 -0800, Aahz a écrit :

Again, your responsibility is to provide a patch and a spectrum of
benchmarking tests to prove it. Then you would still have to deal with
the objection that extensions use the list internals -- that might be an
okay sell given the effort otherwise required to port extensions to
Python 3, but that's not the way to bet.

IMO, code accessing the list internals should be considered broken. The
macros (PyList_GET_ITEM, etc.) are there for a reason. We can't just
freeze every internal characteristic of the interpreter just because
someone might be messing around with it in unrecommended ways.