Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #27194 > unrolled thread

set and dict iteration

Back to article view | Back to comp.lang.python

Contents

  set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-08-16 11:00 -0700
    Re: set and dict iteration Dave Angel <d@davea.name> - 2012-08-16 15:49 -0400
      Re: set and dict iteration Paul Rubin <no.email@nospam.invalid> - 2012-08-16 14:26 -0700
        Re: set and dict iteration Dave Angel <davea@dejaviewphoto.com> - 2012-08-16 19:11 -0400
          Re: set and dict iteration Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-08-17 02:24 +0000
            Re: set and dict iteration Paul Rubin <no.email@nospam.invalid> - 2012-08-16 19:30 -0700
              Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-08-17 11:11 -0700
            Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-08-17 11:37 -0700
              Re: set and dict iteration Chris Angelico <rosuav@gmail.com> - 2012-08-18 07:57 +1000
                Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-08-18 13:29 -0700
                Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-08-18 13:29 -0700
                  Re: set and dict iteration MRAB <python@mrabarnett.plus.com> - 2012-08-18 23:14 +0100
                    Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-08-18 19:28 -0700
                      Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-08-23 09:49 -0700
                        Re: set and dict iteration Ian Kelly <ian.g.kelly@gmail.com> - 2012-08-27 13:17 -0600
                          Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-09-02 10:43 -0700
                            Re: set and dict iteration Ian Kelly <ian.g.kelly@gmail.com> - 2012-09-03 13:29 -0600
                              Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-09-03 13:04 -0700
                                Re: set and dict iteration Dave Angel <d@davea.name> - 2012-09-03 16:27 -0400
                                  Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-09-03 17:24 -0700
                                  Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-09-03 17:24 -0700
                              Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-09-03 13:04 -0700
                                Re: set and dict iteration Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-09-04 01:26 +0000
                                  Re: set and dict iteration Dave Angel <d@davea.name> - 2012-09-03 21:50 -0400
                                    Re: set and dict iteration Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-09-04 01:59 +0000
                                      Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-09-08 08:42 -0700
                          Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-09-02 10:43 -0700
                        Re: set and dict iteration Serhiy Storchaka <storchaka@gmail.com> - 2012-09-04 00:46 +0300
                      Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-08-23 09:49 -0700
                        Re: set and dict iteration Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-08-23 18:11 +0000
                          Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-08-27 11:10 -0700
                          Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-09-08 15:07 -0700
                    Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-08-18 19:28 -0700
                    Re: set and dict iteration Thomas Rachel <nutznetz-0c1b6768-bfa9-48d5-a470-7603bd3aa915@spamschutz.glglgl.de> - 2012-09-08 22:06 +0200
                      Re: set and dict iteration Hans Mulder <hansmu@xs4all.nl> - 2012-09-08 23:18 +0200
                      Re: set and dict iteration MRAB <python@mrabarnett.plus.com> - 2012-09-08 22:22 +0100
        Re: set and dict iteration Ian Kelly <ian.g.kelly@gmail.com> - 2012-08-16 17:43 -0600
          Re: set and dict iteration Paul Rubin <no.email@nospam.invalid> - 2012-08-16 18:01 -0700
            Re: set and dict iteration Ulrich Eckhardt <ulrich.eckhardt@dominolaser.com> - 2012-08-17 13:16 +0200
            Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-08-17 11:03 -0700
            Re: set and dict iteration 88888 Dihedral <dihedral88888@googlemail.com> - 2012-09-10 13:14 -0700
    Re: set and dict iteration Ian Kelly <ian.g.kelly@gmail.com> - 2012-08-16 16:55 -0600
    Re: set and dict iteration Ian Kelly <ian.g.kelly@gmail.com> - 2012-08-16 17:07 -0600
      Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-08-17 10:47 -0700
      Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-08-17 10:47 -0700

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#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:
> 
> > 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

Hi D. Angel,

The serial index constantly reminds me of upper limits.  I have the same problem 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 modification is made, therefore it's the "correct" structure in my interpretation.  But it does seem more precarious comparatively, IMHO.

Both strategies solve the problem I posed originally, they both involve trade-offs, and it's too late to include either in 3.3.0.

[toc] | [prev] | [next] | [standalone]

#28369

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.

[toc] | [prev] | [next] | [standalone]

#28379

On Mon, 03 Sep 2012 13:04:23 -0700, 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 that is over-engineered and could be the difference between 
having the patch accepted and having it rejected. After all, many people 
will argue that the existing solution to the problem is good enough.

Dicts are extremely common, and your patch increases both the memory 
usage of every dict, and the overhead of every write operation 
(__setitem__, __delitem__, update). Only a very few dicts will actually 
need this overhead, for the rest it is waste. It is important to keep 
that waste to a minimum or risk having the patch rejected.

An unsigned C int can count up to 4,294,967,295. I propose that you say 
that is enough iterators for anyone, and use a single, simple, version 
counter in the dict and the iterator. If somebody exceeds that many 
iterators to a single dict or set, and the version field overflows by 
exactly 2**32 versions, the results are no worse than they are now. You 
won't be introducing any new bugs.

Complicating the solution is, in my opinion, unnecessary. Why should 
every set and dict carry the cost of incrementing TWO Python longs and a 
flag when just a single C int is sufficient for all realistic use-cases?

The opportunity for failure is extremely narrow:

- I must have an iterator over a dict or set;
- and I must have paused the iteration in some way;
- and then I must create exactly 2**32 other iterators to the 
  same dict or set;
- and at some point modify the dict or set
- and then restart the first iterator

at which point some items returned by the iterator *may* be duplicated or 
skipped (depends on the nature of the modifications).


-- 
Steven

[toc] | [prev] | [next] | [standalone]

#28381

On 09/03/2012 09:26 PM, Steven D'Aprano wrote:
> On Mon, 03 Sep 2012 13:04:23 -0700, Aaron Brady wrote:
>
>> <snip>
>>
>> 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 that is over-engineered and could be the difference between 
> having the patch accepted and having it rejected. After all, many people 
> will argue that the existing solution to the problem is good enough.
>
> Dicts are extremely common, and your patch increases both the memory 
> usage of every dict, and the overhead of every write operation 
> (__setitem__, __delitem__, update). Only a very few dicts will actually 
> need this overhead, for the rest it is waste. It is important to keep 
> that waste to a minimum or risk having the patch rejected.
>
> An unsigned C int can count up to 4,294,967,295. I propose that you say 
> that is enough iterators for anyone, and use a single, simple, version 
> counter in the dict and the iterator. If somebody exceeds that many 
> iterators to a single dict or set, 

I think you have the count confused.  it has to be a count of how many
changes have been made to the dict or set, not how many iterators exist.

> and the version field overflows by 
> exactly 2**32 versions, the results are no worse than they are now. You 
> won't be introducing any new bugs.
>
> Complicating the solution is, in my opinion, unnecessary. Why should 
> every set and dict carry the cost of incrementing TWO Python longs and a 
> flag when just a single C int is sufficient for all realistic use-cases?
>
> The opportunity for failure is extremely narrow:
>
> - I must have an iterator over a dict or set;
> - and I must have paused the iteration in some way;
> - and then I must create exactly 2**32 other iterators to the 
>   same dict or set;
> - and at some point modify the dict or set
> - and then restart the first iterator
>
> at which point some items returned by the iterator *may* be duplicated or 
> skipped (depends on the nature of the modifications).
>
>

I agree with almost your entire point, exact that the place where it
would fail to detect a bug is when somebody has modified the dict
exactly 2**32 times while an iterator is paused.  See my own response,
of 4:27pm. (my time).

-- 

DaveA

[toc] | [prev] | [next] | [standalone]

#28382

On Mon, 03 Sep 2012 21:50:57 -0400, Dave Angel wrote:

> On 09/03/2012 09:26 PM, Steven D'Aprano wrote:

>> An unsigned C int can count up to 4,294,967,295. I propose that you say
>> that is enough iterators for anyone, and use a single, simple, version
>> counter in the dict and the iterator. If somebody exceeds that many
>> iterators to a single dict or set,
> 
> I think you have the count confused.  it has to be a count of how many
> changes have been made to the dict or set, not how many iterators exist.

Oops, yes you are absolutely right. It's a version number, not a count of 
iterators.


-- 
Steven

[toc] | [prev] | [next] | [standalone]

#28726

On Monday, September 3, 2012 8:59:16 PM UTC-5, Steven D'Aprano wrote:
> On Mon, 03 Sep 2012 21:50:57 -0400, Dave Angel wrote:
> 
> 
> 
> > On 09/03/2012 09:26 PM, Steven D'Aprano wrote:
> 
> 
> 
> >> An unsigned C int can count up to 4,294,967,295. I propose that you say
> 
> >> that is enough iterators for anyone, and use a single, simple, version
> 
> >> counter in the dict and the iterator. If somebody exceeds that many
> 
> >> iterators to a single dict or set,
> 
> > 
> 
> > I think you have the count confused.  it has to be a count of how many
> 
> > changes have been made to the dict or set, not how many iterators exist.
> 
> 
> 
> Oops, yes you are absolutely right. It's a version number, not a count of 
> 
> iterators.
> 
> 
> 
> 
> 
> -- 
> 
> Steven

Hello.  We have a number of proposed solutions so far.

1) Collection of iterators
  a) Linked list
    i) Uncounted references
    ii) Counted references
    iii) Weak references
  b) Weak set
2) Serial index / timestamp
  a) No overflow - Python longs
  b) Overflow - C ints / shorts / chars
  c) Reset index if no iterators left
3) Iterator count
  - Raise exception on set modifications, not iteration

Note, "2b" still leaves the possibility of missing a case and letting an error pass silently, as the current behavior does.  The rest catch the error 100% of the time.

Anyway, I plan to develop the above patch for the 'dict' class.  Would anyone like to take over or help me do it?

[toc] | [prev] | [next] | [standalone]

#28281

On Monday, August 27, 2012 2:17:45 PM UTC-5, Ian wrote:
> 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 new concepts.
> 
> 
> 
> Is there a link to the patch?

Please see below.  It grew somewhat during development.

> > The first is a "linked list".
SNIP.
 
> > The second is "uncounted references".  The uncounted references are references to "set iterators" exclusively, exist only internally to "set" objects, and are invisible to the rest of the program.  The reason for the exception is that iterators are unique in the Python Data Model; iterators consist of a single immutable reference, unlike both immutable types such as strings and numbers, as well as container types.  Counted references could be used instead, but would be consistently wasted work for the garbage collector, 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 uncounted references are justified to introduce, or are counted references preferable?
> 
> 
> 
> 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


Hi Ian,

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.  Using the linked list collection, modification operations are expensive in rare cases.  Using the version index, iteration is expensive in rare cases.

I was more interested in the linked list for conceptual reasons, so I developed it further.  Changelog, diff file, test suite, and links are below.  The devs should be aware that a competing patch might be developed.  I would be pleased to hear what everybody thinks of it!

Linked list with uncounted references implementation for Win32.

Added:
- 'set_clear_ex' and 'set_clear_internal_ex' methods, differ in invalidation and conditional invalidation behavior and return type..  The 'set.clear()' method and 'tp_clear' type field both called the same method.
- 'set_invalidate_iter_linked' method.  Iterate over the iterators of a set, mark them invalid, and clear the list.
- 'setiter_unlink_internal' method.  Remove the iterator from the set's linked list of iterators.
- 'IterationError', global.
- New fields:
-- PySetObject: setiterobject *iter_linked.  Pointer to the first element of the linked list of the iterators of the set.
-- setiterobject: setiterobject *linked_pred, *linked_succ.  Predecessor and successor nodes in the linked list of iterators of the same set.
-- setiterobject: char ob_valid.  Validation status of the iterator.
- Result is compared with original in 'set_intersection_update' and '_multi' to determine whether to invalidate the list of iterators.  Asymptotic running time is unchanged.
- Pending: add 'tp_clear' field to 'PySetIter_Type'?
- Test script included, 'large numbers' test pending.

6 files changed: { setobject.h, setobject.c, exceptions.c, pyerrors.h, python3.def, python33stub.def }.  Test script 'set_iterator_test.py' new.  Linked list interface and pseudocode 'patch_pseudocode.txt'.
Zip file:
http://home.comcast.net/~castironpi-misc/clpy-0062-set_iterator_patch.zip
Diff file of 3.3.0b2:
http://home.comcast.net/~castironpi-misc/clpy-0062-set_iterator_diff.txt

[toc] | [prev] | [next] | [standalone]

#28372

On 27.08.12 22:17, Ian Kelly wrote:
> 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.

Oh, I'm surprised that this strategy is not used yet. I was sure that it 
is used.

[toc] | [prev] | [next] | [standalone]

#27745

On Saturday, August 18, 2012 9:28:32 PM UTC-5, Aaron Brady wrote:
> On Saturday, August 18, 2012 5:14:05 PM UTC-5, MRAB wrote:
> 
> > On 18/08/2012 21:29, Aaron Brady wrote:
> 
> > > On Friday, August 17, 2012 4:57:41 PM UTC-5, Chris Angelico wrote:
> 
> > >> On Sat, Aug 18, 2012 at 4:37 AM, Aaron Brady <castironpi@gmail.com> wrote:
> 
> > >> > Is there a problem with hacking on the Beta?
> 
> > >> Nope. Hack on the beta, then when the release arrives, rebase your
> 
> > >> work onto it. I doubt that anything of this nature will be changed
> 
> > >> between now and then.
> 
> > >> ChrisA
> 
> > > Thanks Chris, your post was encouraging.
> 
> > > I have a question about involving the 'tp_clear' field of the types.
> 
> > > http://docs.python.org/dev/c-api/typeobj.html#PyTypeObject.tp_clear
> 
> > > '''
> 
> > > ...The tuple type does not implement a tp_clear function, because it’s possible to prove that no reference cycle can be composed entirely of tuples.
> 
> > > '''
> 
> > > I didn't follow the reasoning in the proof; the premise is necessary but IMHO not obviously sufficient.  Nevertheless, the earlier diagram contains an overt homogeneous reference cycle.
> 
> > > Reposting: http://home.comcast.net/~castironpi-misc/clpy-0062%20set%20iterators.png
> 
> > > In my estimate, the 'tp_traverse' and 'tp_clear' fields of the set doesn't need to visit the auxiliary collection; the same fields of the iterators don't need to visit the primary set or other iterators; and references in the linked list don't need to be included in the iterators' reference counts.
> 
> > > Can someone who is more familiar with the cycle detector and cycle breaker, help prove or disprove the above?
> 
> > In simple terms, when you create an immutable object it can contain
> 
> > only references to pre-existing objects, but in order to create a cycle
> 
> > you need to make an object refer to another which is created later, so
> 
> > it's not possible to create a cycle out of immutable objects.
> 
> > However, using Python's C API it _is_ possible to create such a cycle,
> 
> > by mutating an otherwise-immutable tuple (see PyTuple_SetItem and
> 
> > PyTuple_SET_ITEM).
> 
> Are there any precedents for storing uncounted references to PyObject's?
> 
> One apparent problematic case is creating an iterator to a set, then adding it to the set.  However the operation is a modification, and causes the iterator to be removed from the secondary list before the set is examined for collection.
> 
> Otherwise, the iterator keeps a counted reference to the set, but the set does not keep a counted reference to the iterator, so the iterator will always be freed first.  Therefore, the set's secondary list will be empty when the set is freed.
> 
> Concurrent addition and deletion of iterators should be disabled, and the iterators should remove themselves from the set's secondary list before they decrement their references to the set.
> 
> Please refresh the earlier diagram; counted references are distinguished separately.  Reposting: http://home.comcast.net/~castironpi-misc/clpy-0062%20set%20iterators.png

The patch for the above is only 40-60 lines.  However it introduces two new concepts.

The first is a "linked list", a classic dynamic data structure, first developed in 1955, cf. http://en.wikipedia.org/wiki/Linked_list .  Linked lists are absent in Python, including the standard library and CPython implementation, beyond the weak reference mechanism and garbage collector.  The "collections.deque" structure shares some of the linked list interface but uses arrays.

The second is "uncounted references".  The uncounted references are references to "set iterators" exclusively, exist only internally to "set" objects, and are invisible to the rest of the program.  The reason for the exception is that iterators are unique in the Python Data Model; iterators consist of a single immutable reference, unlike both immutable types such as strings and numbers, as well as container types.  Counted references could be used instead, but would be consistently wasted work for the garbage collector, 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 uncounted references are justified to introduce, or are counted references preferable?

[toc] | [prev] | [next] | [standalone]

#27754

On Thu, 23 Aug 2012 09:49:41 -0700, Aaron Brady wrote:

[...]
> The patch for the above is only 40-60 lines.  However it introduces two
> new concepts.
> 
> The first is a "linked list", a classic dynamic data structure, first
> developed in 1955, cf. http://en.wikipedia.org/wiki/Linked_list . 
> Linked lists are absent in Python

They certainly are not. There's merely no named "linked list" class.

Linked lists are used by collections.ChainMap, tracebacks, xml.dom, 
Abstract Syntax Trees, and probably many other places. (Well, technically 
some of these are trees rather than lists.) You can trivially create a 
linked list:

x = [a, [b, [c, [d, [e, None]]]]]

is equivalent to a singly-linked list with five nodes. Only less 
efficient.


> The second is "uncounted references".  The uncounted references are
> references to "set iterators" exclusively, exist only internally to
> "set" objects, and are invisible to the rest of the program.  The reason
> for the exception is that iterators are unique in the Python Data Model;
> iterators consist of a single immutable reference, unlike both immutable
> types such as strings and numbers, as well as container types.  Counted
> references could be used instead, but would be consistently wasted work
> for the garbage collector, though the benefit to programmers' peace of
> mind could be significant.

The usual way to implement "uncounted references" is by using weakrefs. 
Why invent yet another form of weakref?



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#27993

On Thursday, August 23, 2012 1:11:14 PM UTC-5, Steven D'Aprano wrote:
> On Thu, 23 Aug 2012 09:49:41 -0700, Aaron Brady wrote:
> 
> 
> 
> [...]
> 
> > The patch for the above is only 40-60 lines.  However it introduces two
> 
> > new concepts.
> 
> > 
> 
> > The first is a "linked list", a classic dynamic data structure, first
> 
> > developed in 1955, cf. http://en.wikipedia.org/wiki/Linked_list . 
> 
> > Linked lists are absent in Python
> 
> 
> 
> They certainly are not. There's merely no named "linked list" class.
> 
> 
> 
> Linked lists are used by collections.ChainMap, tracebacks, xml.dom, 
> 
> Abstract Syntax Trees, and probably many other places. (Well, technically 
> 
> some of these are trees rather than lists.) You can trivially create a 
> 
> linked list:
> 
> 
> 
> x = [a, [b, [c, [d, [e, None]]]]]
> 
> 
> 
> is equivalent to a singly-linked list with five nodes. Only less 
> 
> efficient.
> 
> 
> 
> 
> 
> > The second is "uncounted references".  The uncounted references are
> 
> > references to "set iterators" exclusively, exist only internally to
> 
> > "set" objects, and are invisible to the rest of the program.  The reason
> 
> > for the exception is that iterators are unique in the Python Data Model;
> 
> > iterators consist of a single immutable reference, unlike both immutable
> 
> > types such as strings and numbers, as well as container types.  Counted
> 
> > references could be used instead, but would be consistently wasted work
> 
> > for the garbage collector, though the benefit to programmers' peace of
> 
> > mind could be significant.
> 
> 
> 
> The usual way to implement "uncounted references" is by using weakrefs. 
> 
> Why invent yet another form of weakref?
> 
> 
> 
> 
> 
> 
> 
> -- 
> 
> Steven


Hello S. D'Aprano.  Thanks for your support as always.

The semantics of the second collection are equivalent to a WeakSet.  The space and time consumption of a WeakSet are higher in comparison to a linked list.  However, so long as we iterated over it using the C API instead of creating an iterator, it would be consistent.  If we dynamically create the WeakSet on demand and free it when empty, the space consumption would be lower.  Typical use cases don't involve creating thousands of iterators, or rapidly creating and destroying them, so the performance impact might not be severe.

Regarding the bare weakrefs, if the iterator's destructor hasn't been called, then the pointer is still valid.  If it has been called, then it's not present in the list.  Unlike Python classes, the destructors of C extension classes are guaranteed to be called.  Therefore there are no points during exection at which a node needs to check whether a reference to its neighbor is valid.

Are your concerns based on data integrity, future maintainability, or what?

[toc] | [prev] | [next] | [standalone]

#28749

On Thursday, August 23, 2012 1:11:14 PM UTC-5, Steven D'Aprano wrote:
> On Thu, 23 Aug 2012 09:49:41 -0700, Aaron Brady wrote:
> 
> 
> 
> [...]
> 
> > The patch for the above is only 40-60 lines.  However it introduces two
> 
> > new concepts.
> 
> > 
> 
> > The first is a "linked list", a classic dynamic data structure, first
> 
> > developed in 1955, cf. http://en.wikipedia.org/wiki/Linked_list . 
> 
> > Linked lists are absent in Python
> 
> 
> 
> They certainly are not. There's merely no named "linked list" class.
> 
> 
> 
> Linked lists are used by collections.ChainMap, tracebacks, xml.dom, 
> 
> Abstract Syntax Trees, and probably many other places. (Well, technically 
> 
> some of these are trees rather than lists.) You can trivially create a 
> 
> linked list:
> 
> 
> 
> x = [a, [b, [c, [d, [e, None]]]]]
> 
> 
> 
> is equivalent to a singly-linked list with five nodes. Only less 
> 
> efficient.
>
[snip.]
>
> -- 
> 
> Steven

That's not totally true.  Your formulation is equivalent to a single-linked list, but a double-linked list can't be represented as an expression because it contains reference cycles.

Single and double-linked lists have the same requirements for inserting a new node.  For instance:

[a, [b, [c, [d, [e, None]]]]]
[a, [a2, [b, [c, [d, [e, None]]]]]]

However, to remove a node, the single-linked list requires iterating over the entire list to find the predecessor of the target, whereas the double-linked list already contains that information.

[a, [b, [c, [d, [e, None]]]]]
[a, [b, [c, [e, None]]]]

The difference might be moot in some applications, such as if we only remove nodes when we're already iterating.

Memory constraints were more severe 50 years ago when the structure was developed.  The difference between one pointer and two in a structure could have a big impact in repetition.  The single-linked list admits more easily of recursive algorithms as well.

[toc] | [prev] | [next] | [standalone]

#27341

On Saturday, August 18, 2012 5:14:05 PM UTC-5, MRAB wrote:
> On 18/08/2012 21:29, Aaron Brady wrote:
> 
> > On Friday, August 17, 2012 4:57:41 PM UTC-5, Chris Angelico wrote:
> 
> >> On Sat, Aug 18, 2012 at 4:37 AM, Aaron Brady <castironpi@gmail.com> wrote:
> 
> >>
> 
> >> > Is there a problem with hacking on the Beta?
> 
> >>
> 
> >>
> 
> >>
> 
> >> Nope. Hack on the beta, then when the release arrives, rebase your
> 
> >>
> 
> >> work onto it. I doubt that anything of this nature will be changed
> 
> >>
> 
> >> between now and then.
> 
> >>
> 
> >>
> 
> >>
> 
> >> ChrisA
> 
> >
> 
> > Thanks Chris, your post was encouraging.
> 
> >
> 
> > I have a question about involving the 'tp_clear' field of the types.
> 
> >
> 
> > http://docs.python.org/dev/c-api/typeobj.html#PyTypeObject.tp_clear
> 
> >
> 
> > '''
> 
> > ...The tuple type does not implement a tp_clear function, because it’s possible to prove that no reference cycle can be composed entirely of tuples.
> 
> > '''
> 
> >
> 
> > I didn't follow the reasoning in the proof; the premise is necessary but IMHO not obviously sufficient.  Nevertheless, the earlier diagram contains an overt homogeneous reference cycle.
> 
> >
> 
> > Reposting: http://home.comcast.net/~castironpi-misc/clpy-0062%20set%20iterators.png
> 
> >
> 
> > In my estimate, the 'tp_traverse' and 'tp_clear' fields of the set doesn't need to visit the auxiliary collection; the same fields of the iterators don't need to visit the primary set or other iterators; and references in the linked list don't need to be included in the iterators' reference counts.
> 
> >
> 
> > Can someone who is more familiar with the cycle detector and cycle breaker, help prove or disprove the above?
> 
> >
> 
> In simple terms, when you create an immutable object it can contain
> 
> only references to pre-existing objects, but in order to create a cycle
> 
> you need to make an object refer to another which is created later, so
> 
> it's not possible to create a cycle out of immutable objects.
> 
> 
> 
> However, using Python's C API it _is_ possible to create such a cycle,
> 
> by mutating an otherwise-immutable tuple (see PyTuple_SetItem and
> 
> PyTuple_SET_ITEM).

Are there any precedents for storing uncounted references to PyObject's?

One apparent problematic case is creating an iterator to a set, then adding it to the set.  However the operation is a modification, and causes the iterator to be removed from the secondary list before the set is examined for collection.

Otherwise, the iterator keeps a counted reference to the set, but the set does not keep a counted reference to the iterator, so the iterator will always be freed first.  Therefore, the set's secondary list will be empty when the set is freed.

Concurrent addition and deletion of iterators should be disabled, and the iterators should remove themselves from the set's secondary list before they decrement their references to the set.

Please refresh the earlier diagram; counted references are distinguished separately.  Reposting: http://home.comcast.net/~castironpi-misc/clpy-0062%20set%20iterators.png

[toc] | [prev] | [next] | [standalone]

#28739

Am 19.08.2012 00:14 schrieb MRAB:

>> Can someone who is more familiar with the cycle detector and cycle
>> breaker, help prove or disprove the above?
>>
> In simple terms, when you create an immutable object it can contain
> only references to pre-existing objects, but in order to create a cycle
> you need to make an object refer to another which is created later, so
> it's not possible to create a cycle out of immutable objects.

Yes, but if I add a list in-between, I can create a refcycle:

a = []
b = (a,)
a.append(b)

So b is a tuple consisting of one list which in turn contains b.

It is not a direct cycle, but an indirect one.

Or would that be detected via the list?


Thomas

[toc] | [prev] | [next] | [standalone]

#28745

On 8/09/12 22:06:08, Thomas Rachel wrote:
> Am 19.08.2012 00:14 schrieb MRAB:
> 
>>> Can someone who is more familiar with the cycle detector and cycle
>>> breaker, help prove or disprove the above?
>>>
>> In simple terms, when you create an immutable object it can contain
>> only references to pre-existing objects, but in order to create a cycle
>> you need to make an object refer to another which is created later, so
>> it's not possible to create a cycle out of immutable objects.
> 
> Yes, but if I add a list in-between, I can create a refcycle:
> 
> a = []
> b = (a,)
> a.append(b)
> 
> So b is a tuple consisting of one list which in turn contains b.
> 
> It is not a direct cycle, but an indirect one.

It's a cycle and it contains an immutable object, but it's not
a cycle consisting of immutable objects only.

As MRAB was arguing: it is not possbible to create a cycle
consisting of immutable objects only (unless you do unspeakable
things at the C level).

-- HansM

[toc] | [prev] | [next] | [standalone]

#28746

On 08/09/2012 21:06, Thomas Rachel wrote:
> Am 19.08.2012 00:14 schrieb MRAB:
>
>>> Can someone who is more familiar with the cycle detector and cycle
>>> breaker, help prove or disprove the above?
>>>
>> In simple terms, when you create an immutable object it can contain
>> only references to pre-existing objects, but in order to create a cycle
>> you need to make an object refer to another which is created later, so
>> it's not possible to create a cycle out of immutable objects.
>
> Yes, but if I add a list in-between, I can create a refcycle:
>
> a = []
> b = (a,)
> a.append(b)
>
> So b is a tuple consisting of one list which in turn contains b.
>
> It is not a direct cycle, but an indirect one.
>
> Or would that be detected via the list?
>
The quote was:

'''
...The tuple type does not implement a tp_clear function, because it’s 
possible to prove that no reference cycle can be composed entirely of 
tuples.
'''

Note: "composed entirely of tuples".

Or, in general, composed entirely of immutables.

Lists are not immutable, therefore the proof does not apply.

[toc] | [prev] | [next] | [standalone]

#27214

On Thu, Aug 16, 2012 at 5:11 PM, Dave Angel <davea@dejaviewphoto.com> wrote:
> There's an enormous difference between type errors, which affect the low
> level dispatch, and checking for whether a dict has changed and may have
> invalidated the iterator.  If we were really going to keep track of what
> iterators are tracking a given dict or set, why stop there?  Why not
> check if another process has changed a file we're iterating through?  Or ...

How does this affect low-level dispatch (Python 2.7)?

>>> class Foo(object):
...     def bar(self):
...         return self
...
>>> Foo().bar()
<__main__.Foo object at 0x00CBEAB0>
>>> Foo.bar(Foo())
<__main__.Foo object at 0x00CC9390>
>>> Foo.bar(object())
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unbound method bar() must be called with Foo instance as
first argument (got object instance instead)

There is no low-level need for this TypeError -- it's purely a case of
not letting the developer shoot himself in the foot.  Although to be
honest the interpreter doesn't give quite enough rope (to mix
metaphors) in this case, and I'm glad for the sake of duck typing that
they removed this particular error in Python 3.

With regard to key insertion and deletion while iterating over a dict
or set, though, there is just no good reason to be doing that
(especially as the result is very implementation-specific), and I
wouldn't mind a more complete low-level check against it as long as
it's not too expensive (which is not clearly the case with the current
suggestion at all).

[toc] | [prev] | [next] | [standalone]

#27216

Ian Kelly <ian.g.kelly@gmail.com> writes:
> With regard to key insertion and deletion while iterating over a dict
> or set, though, there is just no good reason to be doing that
> (especially as the result is very implementation-specific), and I
> wouldn't mind a more complete low-level check against it as long as
> it's not too expensive (which is not clearly the case with the current
> suggestion at all).

One possible approach is to freeze the dictionary against modification
while any iterator is open on it.  You could keep a count of active
iterators in the dict structure, adjusting it whenever an iterator is
created or closed/destroyed.

[toc] | [prev] | [next] | [standalone]

#27234

Am 17.08.2012 03:01, schrieb Paul Rubin:
> Ian Kelly <ian.g.kelly@gmail.com> writes:
>> With regard to key insertion and deletion while iterating over a dict
>> or set, though, there is just no good reason to be doing that
>> (especially as the result is very implementation-specific), and I
>> wouldn't mind a more complete low-level check against it as long as
>> it's not too expensive (which is not clearly the case with the current
>> suggestion at all).
>
> One possible approach is to freeze the dictionary against modification
> while any iterator is open on it.  You could keep a count of active
> iterators in the dict structure, adjusting it whenever an iterator is
> created or closed/destroyed.

What if there is an iterator left over from a loop that was terminated 
early? That could block access to the sequence even though nothing is 
/really/ iterating over it.

I personally prefer a reliable error, at least when __debug__ is set. 
Someone suggested a timestamp or a list of active iterators, which both 
sound reasonable. The two should be O(1) and O(#iterators) in complexity 
on all mutating operations and O(1) on iteration, so they should be 
acceptable. With a C implementation it probably boils down to very few 
cycles (checking a pointer/incrementing an integer). I can't say if this 
is feasible without compromising performance though, at the very least 
it requires an additional member in all dicts and iterators.

Uli

[toc] | [prev] | [next] | [standalone]

#27252

On Thursday, August 16, 2012 8:01:39 PM UTC-5, Paul Rubin wrote:
> Ian Kelly <ian.g.kelly@gmail.com> writes:
> 
> > With regard to key insertion and deletion while iterating over a dict
> 
> > or set, though, there is just no good reason to be doing that
> 
> > (especially as the result is very implementation-specific), and I
> 
> > wouldn't mind a more complete low-level check against it as long as
> 
> > it's not too expensive (which is not clearly the case with the current
> 
> > suggestion at all).
> 
> 
> 
> One possible approach is to freeze the dictionary against modification
> 
> while any iterator is open on it.  You could keep a count of active
> 
> iterators in the dict structure, adjusting it whenever an iterator is
> 
> created or closed/destroyed.

Good point.  Your approach is another consistent solution.

The difference is in where the exception is raised.  Invalidating the iterators raises an exception when they're called.  Locking the set/dict raises an exception on 'add' and 'remove' calls.

The latter also forces additional statements to delete iterators before they leave scope in some cases.  We wouldn't be able to make modifications in a 'for' suite, even if followed by a 'break', which could be a problem for existing code.

[toc] | [prev] | [next] | [standalone]

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.lang.python

csiph-web