--- On Mon, 1/25/10, Christian Heimes <li...@cheimes.de> wrote: > From: Christian Heimes <li...@cheimes.de> > Michael Foord wrote: > > How great is the complication? Making list.pop(0) > efficient sounds like > > a worthy goal, particularly given that the reason you > don't use it is > > because you *know* it is inefficient (so the fact that > you don't use it > > isn't evidence that it isn't wanted - merely evidence > that you had to > > work around the known inefficiency). > > The implementation must be changed in at least four > places: > > * The PyListObject struct gets an additional pointer that > stores a > reference to the head. I would keep the head (element 0) of > the list in > **ob_item and the reference to the malloc()ed array in a > new pointer > *ob_allocated. > > * PyList_New() stores the pointer to the allocated memory > in > op->ob_allocated and sets op->ob_item = > op->ob_allocated > > * listpop() moves the op->ob_item pointer by one > for the special case > of pop(0) > > * list_resize() should occasionally compact the free space > before the > head with memcpy() if it gets too large. > > listinsert() could be optimized for 0 if the list has some > free space in > front of the header, too. > > I favor this approach over an integer offset because > doesn't change the > semantic of ob_item. >
The approach that Christian outlines is exactly what I intend to accomplish, even if the patch does get permanently or temporarily rejected. I am pretty confident about what needs to be done within list_ass_slice, including the listinsert() optimization. I also see where I need to add the new pointer (ob_allocated seems like a good name to me) within the PyListObject struct. Still wrestling with the other details, though. My C is pretty rusty, and of course I have the extreme versatility of Python to blame for that! :) _______________________________________________ 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
