[Python-Dev] collections module

Kurt B. Kaiser kbk at shore.net
Sun Jan 11 21:07:47 EST 2004

"Tim Peters" <tim.one at comcast.net> writes:

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

Certainly true.

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

If 0.5% is too much, and if the impact can't be measured reliably at
20x that level it's Catch 22.

>> 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; 

I was trying to make the point that in a non-queue situation the
impact would be minimized.

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

Well, the speculative gimmick appears to put almost the whole load on
the queues and would surely get a significant improvement over Queue
without (apparently) unduly affecting other list operations.

Interesting discussion!  If I need a queue extension I know where to


More information about the Python-Dev mailing list