deque vs list: performance notes

[Courageous]

> Wouldn't FIFO be the correct term?

Err, yes. Egg on my face. :) I find myself doing that
again and again. last first first last, gives a guy
a headache. How about: "that data structure that works
like grocery store shelves." :)-

> More results (code attached):

I reran your results on my hardware and in my configuration
(you must have some nice hardware, by the way). Anyway:

#        c-deque(tottime)   py-queue(tottime)       list(tottime)

10                  .004       .004           .004
100                 .004       .004           .004
1,000              *.014*      .050           .24
10,000              .12        .549          1.18
100,000            1.14       5.44         129.01

When benching your code, I was surprised for a moment that
your 1000 entry test was so much faster than mine (I ran
the test a half dozen times), but then discovered that my
original reported result in that category was a typo. Whoops.
This does make a very compelling case for the deque in
deque implementations likely to hold 1,000 or so objects
(rare, probably).

>Your C extension is not much faster than a 5 minute Python hack.
>Conclusion?  Don't write C unless you have to. :)

The better question is what is a good metric for "when you
have to." While in some cases the code here is 4x faster or
so, it would, as I noted earlier, appear in some cases that
you won't be seeing that benefit as a matter of practice.

Off the cuff, I'd probably say one good rule of thumb would
be that if you're call to an external module involves a
great number of operations which can be conducted outside
of python, that might be a particularly compelling case.

Ergo...

	mymodule.do_lots_of_stuff()

... is much more of a compelling case than...

	for i in xrange(0,10000)
		mymodule.do_a_little_bit()

... and so on ...


C/