"Tim Peters" <tim.one@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 start. -- KBK