[swift-evolution] [RFC] New collections model: collections advance indices

[Dmitri Gribenko]

On Thu, Mar 3, 2016 at 7:50 PM, Károly Lőrentey
<swift-evolution at swift.org> wrote:
> This reminds me that index invalidation rules are all over the place across
> the various collection types and not very well documented. Some ideas for
> improvements:

You're right on!  We have a document, but it is incomplete, and it is
not a part of the public documentation of the library.

https://github.com/apple/swift/blob/master/docs/IndexInvalidation.rst

> - From the sample code in its documentation, it looks like
>  `MutableCollection` requires subscript assignment to not invalidate
>  indices. Can we make this a formal requirement?

Yes, this is the intent.

> - What about range assignment in `MutableCollection`? E.g., what happens
>  to indices if it changes the element count? (Is supporting that a
> requirement?)

A MutableCollection is not required to support assigning a range of a
different length.

> - Does `RangeReplacableCollection` imply Array-like index invalidation?
>  I think it should.

It does.  Might not be documented though, but it is tested in
StdilbCollectionUnittest with minimal collections (see
stdlib/private/StdlibCollectionUnittest/MinimalCollections.swift.gyb).

> By the way, does the requirement for (amortized) constant complexity also
> apply to advancing an index? That's OK for trees, but it may not come cheap
> for hashed collections. Native dictionaries & sets currently have an
> index.successor() with O(n) complexity (if I'm not mistaken).

They only do because they don't shrink the storage on deletion.  If
they could shrink the storage to maintain the load factor, then
advancing an index once, amortized over advancing it through the
entire hashtable would be O(1).

> What about `Collection.indices`? Getting the first index will definitely
> take O(log(n)) for tree collections, and bridged dictionaries/sets have
> this at O(n).

For bridged dictionaries/sets, yes, but we are planning to fix that.
Our thought was that it was bidirectional indices that required to
store the array of keys, but we have downgraded the indices to be
forward-only, which can be implemented with NSFastEnumeration.  I
could be still overlooking some other reason why we need the array of
keys.

For trees though, it seems that you are right.

>>> - I'm using weak references inside the index, with a (seriously
>>> underdeveloped) index invalidation method that happens to be closer
>>> to #2b than #2a. I'm not happy about using weak references, but this
>>> seemed the most sensible thing to do. I'd love to replace them with
>>> `unowned(unsafe)`, and the mutation counter seems like a great idea.
>>> The ARC issue mentioned at the end of the proposal is rather scary,
>>> though -- I don't know how I would protect against that.
>>
>>
>> Hmm, Dmitri, I thought we decided that using unowned(unsafe) to manage
>> the "indices" collection was simply untenable.  Remember the
>> thread-safety issue, iterating indices on one thread while mutating the
>> collection on another?
>
>
> Hm, aren't multithreaded mutations supposed to use COW to get their own
> copy to mutate?

They can only do so if all independent values hold a strong reference
to the storage.

> Or is this about invalidation of the return value of `Collection.indices`?
> That's not supposed to survive (all) mutations, is it?

Sorry, I don't quite understand the second question, but yes, this is
related to `.indices`.

Dmitri

-- 
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr at gmail.com>*/