Thursday, March 3, 2016

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 of DictionaryIndex point to the storage itself. This allows us to have two separate reference counts. One of the refcounts tracks just the live Dictionary 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.

Comments RSS · Twitter

Leave a Comment