list.pop(0) vs. collections.dequeue

[Steve Howell]

On Jan 25, 1:32 pm, Arnaud Delobelle <arno... at googlemail.com> wrote:
> Steve Howell <showel... at yahoo.com> writes:
>
> [...]
>
> > My algorithm does exactly N pops and roughly N list accesses, so I
> > would be going from N*N + N to N + N log N if switched to blist.
>
> Can you post your algorithm?  It would be interesting to have a concrete
> use case to base this discussion on.
>

It is essentially this, in list_ass_slice:

    if (d < 0) { /* Delete -d items */
        if (ilow == 0) {
            a->popped -= d;
            a->ob_item -= d * sizeof(PyObject *);
            list_resize(a, Py_SIZE(a));
        }
        else {
            memmove(&item[ihigh+d], &item[ihigh],
                (Py_SIZE(a) - ihigh)*sizeof(PyObject *));
            list_resize(a, Py_SIZE(a) + d);
        }
        item = a->ob_item;
    }

I am still working through the memory management issues, but when I
have a complete working patch, I will give more detail.