On Jan 27, 2010, at 11:38 AM, Martin v. Löwis wrote: >> Lists are indeed used *everywhere* and *vast* quantities, which is >> why optimizations on list operations are worthwhile to pursue. > > Unfortunately, the proposed change is a pessimisation, not an > optimisation. We probably shouldn't discuss it further, at least not > until a PEP gets written by its proponents. >
I concur (on both points). AFAICT, the performance of the proposal: * increases space requirements by a small fixed amount * s.append() performance slightly degraded. * the s.insert(0, value) case isn't helped -- still O(n) * repeated s.pop(0) have amortized O(1) but either needs to waste space indefinitely (likely not what the programmer intended by popping off values) or needs to do occasional memmoves (which isn't as good as a deque which never moves the data). * the resize performance doesn't work well with the memory allocator -- while a series of appends can often resize in-place without a need to do an O(n) memmove, but a series of pop(0) calls doesn't have a resize in-place option. What currently unknown is the effect on third-party extensions and debugging tools that access the structure directly. Also, am not sure if this affects psyco or the other implementations such as Jython which may implement lists in terms of existing Java containers. ISTM, the *only* benefit is that an occasional s.pop(0) will perform better than it does now but not as well as a deque which never has to move data). Raymond _______________________________________________ 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
