[Python-Dev] collections module

[Tim Peters]

[Kurt B. Kaiser]
> ...
> If the overall slowdown of lists to get fast queues was 5%, that would
> no doubt be unacceptable.  If it was 0.5%, I imagine it would be
> acceptable?

Probably not -- it's too much the tail wagging the dog, as Python lists,
used for what they're best at, are core language workhorses already.  Timing
changes under 10% are very hard to establish convincingly, though,
especially because the relative performance of Python features varies so
widely across platforms (some mix of the code the platform C compiler
generates, the quality of the platform C libraries, and pure accidents, like
whether the top of the main eval loop happens to end up fighting severe
I-cache conflicts with other high-frequency code).

> Note that if no pop(0)'s are ever done on the list there is no wrap
> around and the slowdown is limited to the access of blocksize plus a
> test; no modulo arithmetic is necessary.  This is also the case if the
> list doesn't grow and items are only removed, including list[0].  And
> in the latter case, the memmoves associated with internal deletions
> will dominate the performance in all implementations.

Neither case holds for a queue; the question that started this was whether
to provide a fancy queue implementation in C, and (of course) Guido would
rather see Python lists efficiently usable for that purpose too.  I
suspected that might not be a realistic hope, and now I'm starting to
*think* it too <wink>.