Cameron Simpson wrote: > The proposed change to make pop(0) O(1) involves adding a base offset > to the internal list implementation. Doesn't that incur a (small) > overhead to _every_ list operation? Doesn't that weaken "list" as the > "as efficient as possible" implementation of choice for "array"-like > things?
No, the implementation is smarter than that. The existing pointer in the PyList_* structure will continue to point to the first element of the list while an extra pointer is added that points to the beginning of the allocated memory. The difference between the two memory addresses will determine the number of "orphan" pointer slots that exist at the beginning of the list. Only operations that change the length of the list will be slowed down at all, since they will need to take the orphans into account when deciding whether or not to resize the allocated memory. The big practical concern is actually the memory cost of adding yet another pointer (potentially 8 bytes of data) to every list object, even empty ones. Cheers, Nick. -- Nick Coghlan | ncogh...@gmail.com | Brisbane, Australia --------------------------------------------------------------- _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
