[Python-Dev] RE: cloning iterators again

Guido van Rossum guido at python.org
Sun Oct 26 19:31:35 EST 2003


> > I've been thinking about various implementations of Andrew Koenig's
> > idea of "copyable iterator wrappers", which support a generalization
> > of Raymond Hettinger's tee(). 
> 
> I've re-read some of the old email on the subject but didn't see what
> this buys us that we don't already get with the current tee().

Performance-wise I don't know; we'd have to profile it I guess. :-(

With the current tee(), I was thinking that if the two iterators stay
close, you end up moving the in basket to the out basket rather
frequently, and the overhead of that might beat the simplicity of the
linked lists.  Also, *if* you need a lot of clones, using multiple
tee() calls ends up creating several queues, again causing more
overhead.  (These queues end up together containing all the items from
the oldest to the newest iterator.)

I also note that the current tee() doesn't let you use __copy__ easily
(it would be quite messy I think).  The linked-list version supports
__copy__ trivially.  This may be important if we execute (as I think
we should) on the idea of making selected iterators __copy__-able
(especially all the standard container iterators and xrange).

> When I wrote tee(), I had considered implementing it as a multi-way
> tee(it, n=2) so you could write a,b,c,d=tee(myiterable, 4).  Then, I
> wracked my brain for use cases and found nothing that warranted:
> 
> * the additional memory consumption (the current implementation consumes
> only one pointer per element and it stores them in contiguous memory); 
> 
> * the additional memory management utilization (the underlying list.pop
> and list.append have already been optimized to avoid excessive
> malloc/free calls); 
> 
> * or the impact on cache performance (using contiguous memory means that
> consecutive pops are in the L1 cache at least 90% of the time and using
> only one word per entry means that a long series of pops is less likely
> to blow everything else out of the cache).
> 
> With only two iterators, I can imagine use cases where the two iterators
> track each other fairly closely.  But with multiple iterators, one
> iterator typically lags far behind (meaning that list(it) is the best
> solution) or they track within a fixed number of elements of each other
> (meaning that windowing is the best solution).

Maybe Andrew has some use cases?  After all he implemented this once
for C++.  BTW in private mail he reminded me that (a) he'd already
suggested using a linked list to me before, and (b) his version had
several values per link node, which might address some of your
concerns above.

> The itertools example section shows the pure python code for windowing.
> AFAICT, that windowing code is unbeatable in terms of speed and memory
> consumption (nearly all the time is spent forming the result tuple).
> 
> 
> 
> > class Link(object):
> >     """Singly-linked list of (state, value) pairs.
> . . .
> >     __slots__ = ["state", "value", "next"]
> 
> One way to implement this is with a type which adds PyHEAD to the space
> consumption for the three fields.  An alternate approach is to use PyMem
> directly and request space for four fields (including a refcount field).

Or you could use Andrew's suggestion.

> 
> >         if state < 0:
> >             self.link = None
> >             raise value
> 
> Is it kosher to re-raise the exception long after something else make
> have handled it and the execution context has long since disappeared?

This isn't a re-raise; it's a raise of the exception object, which
doesn't depend on the context and can be raised as often as you want
to.  I agree that it might be worth it to do a bare raise (==
re-raise) *if* the exception was in fact caught in the current next()
invocation, to preserve the stack trace.  Or we could change the
meaning of value and store the sys.exc_info() triple in it -- but this
would probably keep too many stack frames and local variables alive
for too long.

> > def test():
> >     """A simple demonstration of the Wrapper class."""
> >     import random
> >     def gen():
> >         for i in range(10):
> >             yield i
> >     it = gen()
> >     a, b = tee(it)
> >     b, c = tee(b)
> >     c, d = tee(c)
> 
> This is very nice.  The current tee() increases memory consumption and
> workload when nested like this.

The question is, how often does one need this?  Have you seen real use
cases for tee() that aren't better served with list()?

--Guido van Rossum (home page: http://www.python.org/~guido/)



More information about the Python-Dev mailing list