On 1/23/2010 3:23 AM, Steve Howell wrote:
On Jan 23, 12:13 am, Terry Reedy<tjre...@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

--
http://mail.python.org/mailman/listinfo/python-list

Reply via email to