Path: csiph.com!usenet.pasdenom.info!gegeweb.org!de-l.enfer-du-nord.net!feeder1.enfer-du-nord.net!feeds.phibee-telecom.net!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Newsgroups: comp.lang.python
Date: Mon, 3 Sep 2012 17:24:02 -0700 (PDT)
In-Reply-To: <mailman.156.1346704107.27098.python-list@python.org>
Complaints-To: groups-abuse@google.com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=67.184.78.189; posting-account=MQ3pigoAAACeFzUFjVAePnOjOJMNlvq9
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> <mailman.156.1346704107.27098.python-list@python.org>
User-Agent: G2/1.0
MIME-Version: 1.0
Subject: Re: set and dict iteration
From: Aaron Brady <castironpi@gmail.com>
To: comp.lang.python@googlegroups.com
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Cc: python-list@python.org
Precedence: list
Message-ID: <mailman.160.1346718245.27098.python-list@python.org>
Lines: 88
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:28376

On Monday, September 3, 2012 3:28:28 PM UTC-5, Dave Angel wrote:
> On 09/03/2012 04:04 PM, Aaron Brady wrote:
>=20
> > On Monday, September 3, 2012 2:30:24 PM UTC-5, Ian wrote:
>=20
> >> On Sun, Sep 2, 2012 at 11:43 AM, Aaron Brady <castironpi@gmail.com> wr=
ote:
>=20
> >>
>=20
> >>> We could use a Python long object for the version index to prevent ov=
erflow.  Combined with P. Rubin's idea to count the number of open iterator=
s, most use cases still wouldn't exceed a single word comparison; we could =
reset the counter when there weren't any.
>=20
> >>
>=20
> >>
>=20
> >> We could use a Python long; I just don't think the extra overhead is
>=20
> >>
>=20
> >> justified in a data structure that is already highly optimized for
>=20
> >>
>=20
> >> speed.  Incrementing and testing a C int is *much* faster than doing
>=20
> >>
>=20
> >> the same with a Python long.
>=20
> > I think the technique would require two python longs and a bool in the =
set, and a python long in the iterator.
>=20
> >
>=20
> > One long counts the number of existing (open) iterators.  Another count=
s the version.  The bool keeps track of whether an iterator has been create=
d since the last modification, in which case the next modification requires=
 incrementing the version and resetting the flag.
>=20
>=20
>=20
> I think you're over-engineering the problem.  it's a bug if an iterator
>=20
> is used after some change is made to the set it's iterating over.  We
>=20
> don't need to catch every possible instance of the bug, that's what
>=20
> testing is for.  The point is to "probably" detect it, and for that, all
>=20
> we need is a counter in the set and a counter in the open iterator.=20
>=20
> Whenever changing the set, increment its count.  And whenever iterating,
>=20
> check the two counters.  if they don't agree, throw an exception, and
>=20
> destroy the iterator.  i suppose that could be done with a flag, but it
>=20
> could just as easily be done by zeroing the pointer to the set.
>=20
>=20
>=20
> I'd figure a byte or two would be good enough for the counts, but a C
>=20
> uint would be somewhat faster, and wouldn't wrap as quickly.
>=20
>=20
>=20
> --=20
>=20
>=20
>=20
> DaveA

Hi D. Angel,

The serial index constantly reminds me of upper limits.  I have the same pr=
oblem with PHP arrays, though it's not a problem with the language itself.

The linked list doesn't have a counter, it invalidates iterators when a mod=
ification is made, therefore it's the "correct" structure in my interpretat=
ion.  But it does seem more precarious comparatively, IMHO.

Both strategies solve the problem I posed originally, they both involve tra=
de-offs, and it's too late to include either in 3.3.0.