Path: csiph.com!usenet.pasdenom.info!aioe.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed5.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Date: Mon, 03 Sep 2012 16:27:38 -0400
From: Dave Angel <d@davea.name>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:14.0) Gecko/20120714 Thunderbird/14.0
MIME-Version: 1.0
To: Aaron Brady <castironpi@gmail.com>
Subject: Re: set and dict iteration
References: <b8dd3aca-2a87-4124-ad6e-66a8720af99a@googlegroups.com> <mailman.3389.1345146609.4697.python-list@python.org> <7xy5le7cli.fsf@ruckus.brouhaha.com> <mailman.3404.1345158704.4697.python-list@python.org> <502dab6c$0$29978$c3e8da3$5496439d@news.astraweb.com> <fe95c29c-2289-4e9c-870e-e3c475f13459@googlegroups.com> <mailman.3435.1345240665.4697.python-list@python.org> <d4708687-2925-421a-b755-969d6dac731a@googlegroups.com> <mailman.3476.1345328046.4697.python-list@python.org> <mailman.3480.1345343315.4697.python-list@python.org> <c7452db1-5b78-4d54-81a1-1c8683631d6e@googlegroups.com> <mailman.3883.1346095064.4697.python-list@python.org> <1567e8c7-a2bb-41f4-9be8-18e9f4d063cb@googlegroups.com> <mailman.154.1346700607.27098.python-list@python.org> <ed8c3b7a-f9ff-45fe-9e2c-a225764da7ae@googlegroups.com>
In-Reply-To: <ed8c3b7a-f9ff-45fe-9e2c-a225764da7ae@googlegroups.com>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Cc: python-list@python.org
Precedence: list
Reply-To: d@davea.name
Newsgroups: comp.lang.python
Message-ID: <mailman.156.1346704107.27098.python-list@python.org>
Lines: 35
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:28370

On 09/03/2012 04:04 PM, Aaron Brady wrote:
> On Monday, September 3, 2012 2:30:24 PM UTC-5, Ian wrote:
>> On Sun, Sep 2, 2012 at 11:43 AM, Aaron Brady <castironpi@gmail.com> wrote:
>>
>>> We could use a Python long object for the version index to prevent overflow.  Combined with P. Rubin's idea to count the number of open iterators, most use cases still wouldn't exceed a single word comparison; we could reset the counter when there weren't any.
>>
>>
>> We could use a Python long; I just don't think the extra overhead is
>>
>> justified in a data structure that is already highly optimized for
>>
>> speed.  Incrementing and testing a C int is *much* faster than doing
>>
>> the same with a Python long.
> I think the technique would require two python longs and a bool in the set, and a python long in the iterator.
>
> One long counts the number of existing (open) iterators.  Another counts the version.  The bool keeps track of whether an iterator has been created since the last modification, in which case the next modification requires incrementing the version and resetting the flag.

I think you're over-engineering the problem.  it's a bug if an iterator
is used after some change is made to the set it's iterating over.  We
don't need to catch every possible instance of the bug, that's what
testing is for.  The point is to "probably" detect it, and for that, all
we need is a counter in the set and a counter in the open iterator. 
Whenever changing the set, increment its count.  And whenever iterating,
check the two counters.  if they don't agree, throw an exception, and
destroy the iterator.  i suppose that could be done with a flag, but it
could just as easily be done by zeroing the pointer to the set.

I'd figure a byte or two would be good enough for the counts, but a C
uint would be somewhat faster, and wouldn't wrap as quickly.

-- 

DaveA