--- On Tue, 1/26/10, Cameron Simpson <c...@zip.com.au> wrote: > From: Cameron Simpson <c...@zip.com.au> > | The idea that CPython should not be improved because it > would spoil > | programmers strikes me as a thin, even desparate > objection. > > Hey, I even used the word "thin" to describe my concern! > > My point was that I look on python builtins like list and > dict as highly > optimised, highly efficient facilities. That means that I > expect a "list" > to be very very much like a linear array as one would find > in C-like > languages, with realloc() managment behind the scenes to > handle the > resizing requirements on append/extend. > > It also means that the O() cost of operations should be > pretty obvious. > pop(0) "obviously" involves shuffling everything down one > slot.
In my previous posting, though, I mention another plausible metaphor that programmers would have about lists--ordinary to-do lists where you can cross out or erase the first item in the list in O(1) time. > > 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? > The patch advances the pointer itself during prepops, so accesses continue to work as quickly as before. The offset between the originally allocated pointer and the pointer to the new first element of the list only gets calculated and used during list_resize and list_dealloc. List_resize gets called by any operation that changes the size of the list, including inserts, deletes, pops, etc. Because I have to increase the size of PyListObject, you could argue that I even affect the performance of access to the extent that the greater size of PyListObject increases the likelihood of cache misses. I would consider that also to be a very "thin" objection, although not completely implausible. > > Yes, optimisation is nice. Higher seed is nice. But there > are > optimisations that simple fix inefficiencies or provide a > special case > for a common operation, and there are those with side > effects elsewhere > in the implementation (i.e. the base offset this pop(0) opt > would incur, > which adds a (small) cost to everything). > Your general point about optimizations having tradeoffs is valid, but I am not making the particular tradeoff that you mention. > The other aspect, mentioned elsewhere in this thread, is > that > programmers should know the O() cost of these operations. > The tutorial does mention that the current list implementation has to move all the elements forward when you remove off the top. (Cameron: Quick aside, for some reason your emails keep going to my spam folder. I am sure it's just my mail client being stupid, but I thought I'd let you know in case it's something on your side.) _______________________________________________ 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
