Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!feeder.erje.net!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <c7452db1-5b78-4d54-81a1-1c8683631d6e@googlegroups.com>
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>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Mon, 27 Aug 2012 13:17:12 -0600
Subject: Re: set and dict iteration
To: Python <python-list@python.org>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.3883.1346095064.4697.python-list@python.org>
Lines: 47
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:27996

On Thu, Aug 23, 2012 at 10:49 AM, Aaron Brady <castironpi@gmail.com> wrote:
> The patch for the above is only 40-60 lines.  However it introduces two n=
ew concepts.

Is there a link to the patch?

> The first is a "linked list", a classic dynamic data structure, first dev=
eloped in 1955, cf. http://en.wikipedia.org/wiki/Linked_list .  Linked list=
s are absent in Python, including the standard library and CPython implemen=
tation, beyond the weak reference mechanism and garbage collector.  The "co=
llections.deque" structure shares some of the linked list interface but use=
s arrays.
>
> The second is "uncounted references".  The uncounted references are refer=
ences to "set iterators" exclusively, exist only internally to "set" object=
s, and are invisible to the rest of the program.  The reason for the except=
ion is that iterators are unique in the Python Data Model; iterators consis=
t of a single immutable reference, unlike both immutable types such as stri=
ngs and numbers, as well as container types.  Counted references could be u=
sed instead, but would be consistently wasted work for the garbage collecto=
r, though the benefit to programmers' peace of mind could be significant.
>
> Please share your opinion!  Do you agree that the internal list resolves =
the inconsistency?  Do you agree with the strategy?  Do you agree that unco=
unted references are justified to introduce, or are counted references pref=
erable?

This feature is a hard sell as it is; I think that adding uncounted
references into the mix is only going to make that worse.  May I
suggest an alternate approach?  Internally tag each set or dict with a
"version", which is just a C int.  Every time the hash table is
modified, increment the version.  When an iterator is created, store
the current version on the iterator.  When the iterator is advanced,
check that the iterator version matches the dict/set version.  If
they're not equal, raise an error.

This should add less overhead than the linked list without any
concerns about reference counting.  It does introduce a small bug in
that an error condition could be "missed", if the version is
incremented a multiple of 2**32 or 2**64 times between iterations --
but how often is that really likely to occur?  Bearing in mind that
this error is meant for debugging and not production error handling,
you could even make the version a single byte and I'd still be fine
with that.

Cheers,
Ian