Proposed New Swift Collections Model
Dmitri Gribenko et. al.:
We are proposing a new model for collections, where indices can only be advanced forward or backward by the corresponding collection instance. Indices become opaque tokens representing collection positions, that can be produced and consumed by collection APIs. This allows us to reduce the amount of data stored in indices to the bare minimum.
[…]
Instances of
Dictionary
point to an indirection, while instances ofDictionaryIndex
point to the storage itself. This allows us to have two separate reference counts. One of the refcounts tracks just the liveDictionary
instances, which allows us to perform precise uniqueness checks.The issue that we were previously unaware of is that this scheme is not thread-safe. When uniquely-referenced storage is being mutated in place, indices can be concurrently being incremented (on a different thread). This would be a read/write data race.