list.pop(0) vs. collections.dequeue

[Steve Howell]

On Jan 22, 6:20 pm, Steven D'Aprano <st... at REMOVE-THIS-
cybersource.com.au> wrote:
> On Fri, 22 Jan 2010 14:38:18 -0800, Steve Howell wrote:
> > I know the Python programmer could simply iterate through the list
> > rather than popping off unused elements, but that just means that you
> > not only tie up the memory for the pointers just as long, but you also
> > prevent the objects themselves from being garbage collected.
>
> > In my case I'm not really concerned about giving the memory back right
> > away, it's more about keeping my code simple.  Once I'm done with an
> > element, I do just want to pop it off and keep all the simplicity of the
> > lists, but I am just concerned enough speed that for a 1000 element
> > list, I don't want to be doing 1000 memmoves for an average of 500
> > pointers, which effectively moves about a million bytes around for no
> > reason.
>
> > I suppose the solution is to either give up the sugar of lists, or try
> > to wrap something like deque or list-with-offset into a sequence.
>
> I don't understand what the actual problem you're trying to solve is.
> Despite your disclaimer about not being concerned about reclaiming the
> memory, it sounds like you're trying to micro-optimize memory usage.

My discussion of memory probably distracted you from the fact that I'm
not proposing a micro-optimization of memory; I am proposing a mega-
optimization of CPU.

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)?

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

  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).

>  That
> is, you give me the impression that you prefer this:
>
> while alist:
>     x = alist.pop(0)
>     process(x)
>
> over this:
>
> for x in alist:
>     process(x)
> # allow alist to be garbage collected when it goes out of scope
>

No, to be more precise, I prefer this implementation of a recursive
parser (using lists) to one that would have to use deque's because of
the lameness of Python's list implementation:

https://bitbucket.org/showell/shpaml_website/src/tip/shpaml.py