list.pop(0) vs. collections.dequeue

[Terry Reedy]

On 1/23/2010 3:23 AM, Steve Howell wrote:
> On Jan 23, 12:13 am, Terry Reedy<tjre... at udel.edu>  wrote:
>>
>> Challenge yes, mock no.
>>
>> Part of writing good basic data structures is not adding needless
>> complication from featuritis and not penalizing 99.99% of access to
>> satify a .01% need better satisfied another way.
>>
>
> I would like to challenge your assertion that advancing ob_item
> instead of doing memmove during list_ass_slice would impact the
> performance of list accesses in any way.  It would only slow down
> operations that add/insert items into the list by, and then only by a
> single conditional statement, and those add/insert operations are
> already O(N) to begin with.

If you try writing a full patch, as I believe someone did, or at least a 
prototype thereof, when the idea was discussed, you might have a better 
idea of what the tradeoffs are and why it was rejected.

For instance, when you append to a full list, it is resized. I believe 
it is now doubled, but the policy has varied over the years. If you turn 
list from essentially a stack to a deque, you complicate the resizing 
policy and have to consider the addition of a shift policy. Do you split 
the over-allocated fore and aft or increase the overallocation from 
double to, say, triple? If the former, then for normal usage that never 
uses the fore part, the over-allocation has been effectively reduced 
from 2x to 1.5x (which is about what it once was, I believe). This means 
more frequent resizings and copyings, which means slower operation for 
most use cases. Adding extra usually wasted space is also a nuisance.

Terry Jan Reedy