[Python-Dev] collections module

[Raymond Hettinger]

> > The memory manager is called once every for 50 queue insertions and
> > memory is freed after every 50 pops.  Outside of that, every push
and
> > pop just a fast array access and pointer increment.  Long queues
incur
> > about a 15-20% space overhead as compared to a straight-list
> > implementation.  Speedwise, this beats the socks off of the current
> > approach.
> 
> Meaning pairing append() and pop(0)?  Sure -- it would be hard not to
beat
> that <wink>. 

No, I meant that it is *much* faster to do an indexed write to a
pre-allocated list than to use anything relying on PyList_Append() or
ins1().  All of those individual calls to realloc are expensive.  The 50
to 1 dilution of that expense is how it beats Knuth's two stack trick.

Guess which of these two statements is faster and by how much:

     list(itertools.repeat(None, 5000))
     list(tuple(itertools.repeat(None, 5000)))

The answer is important because it points the way to faster list
comprehensions and other list building applications.

> I've never needed a queue in Python where "the standard" two-list
trick
> (as
> shown in Josiah's Cookbook comment) wasn't more than good enough, so
my
> interest in this is really limited to whether Python's native list
type
> can
> (realistically) be made efficient for general deque operation.

And my interest is in a collections module which should probably
published elsewhere (too much negativity on the subject here).  

I am frankly surprised that so many here think that a collections module
would be bad for the language.  Go figure.  It's not like these are new,
untried ideas -- the goal was supposed be improving productivity by
providing higher level tools.  A fast underlying implementation was just
icing on the cake.


Raymond Hettinger


#################################################################
#################################################################
#################################################################
#####
#####
#####
#################################################################
#################################################################
#################################################################