list.pop(0) vs. collections.dequeue

[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