[Python-Dev] Optimization of the Year

[Oren Tirosh]

On Wed, Feb 11, 2004 at 02:06:50AM +0900, Hye-Shik Chang wrote:
> On Tue, Feb 10, 2004 at 11:04:02AM -0500, Tim Peters wrote:
> > [Raymond]
> > > Hey, hey!  After looking at this on and off for months, I finally
> > > found a safe way to dramatically improve the speed of building lists:
> > >
> > > 	http://users.rcn.com/python/download/list.diff
> > 
> > Cool!
> > 
> 
> I made an updated patch very slightly modified from Raymond's.
> Dropped use of track_* member variables and applied simpler extra
> size calculation suggested by Tim.
> 
>  http://people.freebsd.org/~perky/list-r2.diff.txt

It would be nice if this could be combined with the pop(0) speedup for
the idiomatic use of lists as queues.

How about this:

If op->allocated is positive it indicates the amount of memory allocated
to avoid unnecessary realloc() calls. If negative it indicates how far the
list's ob_item pointer has been bumped by popping (i.e. the actual
malloced block is ob_item+allocated). When it's negative any appends to
the list will have to trust the performance of realloc, but this seems a
reasonable tradeoff because it's saving O(N) behavior. The common case
(append to a list whose pointer has not been bumped by popping) should not
be slowed down at all - the test for negativity is only in the branch
taken when a resize is required.

Yes, it's a little convoluted, but it the impact of this change seems to
be restricted in its scope: assignments to ob_item need to make sure that
allocated is also updated (just like your patch) and calls to PyMem need
the real allocated pointer: ob_item + (allocated<0 ? allocated : 0)

    Oren