list.pop(0) vs. collections.dequeue

[Steve Howell]

On Jan 22, 11:10 pm, a... at pythoncraft.com (Aahz) wrote:
>
> >I know Python's number one concern will never be speed, but if Python
> >makes an O(1) operation into an unnecessarily O(N) operation for no
> >good reasons other than "it's too complicated, " or it "adds another
> >pointer to the structure," or "it adds another conditional check to
> >list_ass_slice for operations that aren't popping off the top," I
> >think it's reasonable to challenge the design philosophy.
>
> "Rough consensus and running code."
>
> You have a good point, but nobody will ever give your idea serious
> attention until there's a patch and benchmarks.

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

    showell at showell-laptop:~$ time ./slow

    real    0m1.446s
    user    0m1.444s
    sys 0m0.004s
    showell at showell-laptop:~$ time ./fast

    real    0m0.003s
    user    0m0.004s
    sys 0m0.000s
    showell at showell-laptop:~$ diff slow.c fast.c
    23,24c23
    <     lst.size -= 1;
    <     memmove(lst.p, lst.p + 1, lst.size);
    ---
    >     lst.p += 1;
    showell at showell-laptop:~$ cat slow.c
    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>

    struct ob_item {
        int whatever;
    };

    struct list {
        struct ob_item *p;
        int size;
    };

    struct list make_list(int n)
    {
        struct list lst;
        lst.p = malloc(n);
        lst.size = n;
        return lst;
    }

    void list_pop_left(struct list lst) {
        lst.size -= 1;
        memmove(lst.p, lst.p + 1, lst.size);
    }

    int main() {
        struct list lst;
        int i;
        int n = 40000;
        int t;

        lst = make_list(n);
        for (i = 0; i < n; ++i) {
            list_pop_left(lst);
        }
    }