list.pop(0) vs. collections.dequeue

[Alf P. Steinbach]

* Steve Howell:
> 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.

I'm sorry, no, the last part is incorrect.

Appending to a 'list' can currently be constant time, if OS reallocation is 
constant time (as the string '+' optimization relies on).

With the pop optimization it can no longer be constant time without risking an 
accumulation of unused memory, a memory leak, although it can be amortized 
constant time, at the cost of wasting some percentage of memory.


Cheers & hth.,

- Alf