[swift-evolution] [Proposal Draft] Provide Custom Collections for Dictionary Keys and Values

[Stephan Knitelius]

+1

On Wed, 12 Oct 2016 at 09:09 Said Sikira via swift-evolution <
swift-evolution at swift.org> wrote:

> +1
>
>
> On October 12, 2016 at 8:54:45 AM, Rien via swift-evolution (
> swift-evolution at swift.org) wrote:
>
> Beautiful, +1
>
> Rien
>
> > On 11 Oct 2016, at 23:28, Nate Cook via swift-evolution <
> swift-evolution at swift.org> wrote:
> >
> > Introduction
> >
> > This proposal addresses significant unexpected performance gaps when
> using dictionaries. It introduces type-specific collections for a
> Dictionary instance's keys and values properties.
> >
> > New DictionaryKeys and DictionaryValues collections provide efficient
> key lookup and mutable access to dictionary values, enabling updates to be
> performed in-place and allowing copy-on-write optimization of stored values.
> >
> > Motivation
> >
> > This proposal address two problems:
> >
> > • The Dictionary type keys implementation is inefficient, because
> LazyMapCollection doesn't know how to forward lookups to the underlying
> dictionary storage.
> > • Dictionaries do not offer value-mutating APIs. The mutating key-based
> subscript wraps values in an Optional. This prevents types with
> copy-on-write optimizations from recognizing they are singly referenced.
> > This proposal uses the following [String: [Int]] dictionary to
> demonstrate these problems:
> >
> > var dict = ["one": [1], "two": [2, 2], "three": [3, 3, 3]]
> > Inefficient dict.keys Search
> >
> > Swift coders normally test key membership using nil checks or
> underscored optional bindings:
> >
> > if dict["one"] != nil
> > {
> >
> > // ...
> >
> > }
> >
> > if let _ = dict["one"
> > ] {
> >
> > // ...
> >
> > }
> >
> > These approaches provide the expected performance of a dictionary lookup
> but they read neither well nor "Swifty". Checking keys reads much better
> but introduces a serious performance penalty: this approach requires a
> linear search through a dictionary's keys to find a match.
> >
> > if dict.keys.contains("one") {
> > // ...
> > }
> >
> > A similar dynamic plays out when comparing dict.index(forKey:) and
> dict.keys.index(of:).
> >
> > Inefficient Value Mutation
> >
> > Dictionary values can be modified through the keyed subscript by direct
> reassignment or by using optional chaining. Both of these statements append
> 1 to the array stored by the key "one":
> >
> > // Direct re-assignment
> >
> > dict[
> > "one"] = (dict["one"] ?? []) + [1
> > ]
> >
> >
> > // Optional chaining
> >
> > dict[
> > "one"]?.append(1)
> > Both approaches present problems. The first is complex and hard to read.
> The second ignores the case where "one" is not a key in the dictionary. It
> forces its check into a higher branch and encourages forced unwrapping.
> Furthermore, neither approach allows the array to grow in place. They
> introduce an unnecessary copy of the array's contents even though dict is
> the sole holder of its storage.
> >
> > Adding mutation to a dictionary's index-based subscripting isn't
> possible. Changing a key stored at a particular index would almost
> certainly modify its hash value, rendering the index incorrect. This
> violates the requirements of the MutableCollection protocol.
> >
> > Proposed Solution
> >
> > This proposal adds a custom collection for the keys and values
> dictionary properties. This follows the example set by String, which
> presents multiple views of its contents. A new DictionaryKeys collection
> introduces efficient key lookup, while a new DictionaryValues collection
> provides a mutable collection interface to dictionary values.
> >
> > These changes introduce a simple and efficient way of checking whether a
> dictionary includes a key:
> >
> > // Performant
> > if dict.keys.contains("one"
> > ) {
> >
> > // ...
> >
> > }
> >
> > As a mutable collection, values enables modification without copies or
> clumsy code:
> >
> > if let i = dict.index(forKey: "one"
> > ) {
> > dict
> > .values[i].append(1) // no copy here
> >
> > }
> > else
> > {
> > dict[
> > "one"] = [1
> > ]
> > }
> >
> > Both the keys and values collections share the same index type as
> Dictionary. This allows the above sample to be rewritten as:
> >
> > // Using `dict.keys.index(of:)`
> > if let i = dict.keys.index(of: "one"
> > ) {
> > dict
> > .values[i].append(1
> > )
> > }
> > else
> > {
> > dict[
> > "one"] = [1
> > ]
> > }
> >
> > Detailed design
> >
> > • The standard library introduces two new collection types:
> DictionaryKeys and DictionaryValues.
> > • A Dictionary's keys and values property types change from
> LazyMapCollection to these new types.
> > • The new collection types are not directly constructable. They are
> presented only as views into a dictionary.
> > struct Dictionary<Key: Hashable, Value>: ...
> > {
> >
> > var keys: DictionaryKeys<Key, Value> { get
> > }
> >
> > var values: DictionaryValues<Key, Value> { get set
> > }
> >
> >
> > // Remaining declarations
> >
> > }
> >
> >
> > /// A collection view of a dictionary's keys.
> > struct DictionaryKeys<Key: Hashable, Value>
> > : Collection {
> >
> > typealias Index = DictionaryIndex<Key, Value>
> >
> >
> > subscript(i: Index) -> Key { get
> > }
> >
> >
> > // Other `Collection` requirements
> >
> > }
> >
> >
> > /// A mutable collection view of a dictionary's values.
> > struct DictionaryValues<Key: Hashable, Value>
> > : MutableCollection {
> >
> > typealias Index = DictionaryIndex<Key, Value>
> >
> >
> > subscript(i: Index) -> Value { get set
> > }
> >
> >
> > // Other `Collection` requirements
> >
> > }
> >
> > A sample implementation of this proposal can be found in this branch.
> >
> > Impact on existing code
> >
> > The performance improvements of using the new DictionaryKeys type and
> the mutability of the DictionaryValuescollection are both additive in
> nature.
> >
> > Most uses of these properties are transitory in nature. Adopting this
> proposal should not produce a major impact on existing code. The only
> impact on existing code exists where a program explicitly specifies the
> type of a dictionary's keysor values property. The fix is to change the
> specified type.
> >
> > Alternatives considered
> >
> > The Generics Manifesto lists nested generics as a goal. This could
> impact the naming and structure of these new collection types.
> >
> > Instead of DictionaryKeys<Key, Value> and DictionaryValues<Key, Value>,
> these types could be Dictionary<Key, Value>.Keys and Dictionary<Key,
> Value>.Values. However, because many types in the standard library may be
> revisited once such a feature is available (indices, iterators, etc.), the
> current lack of nesting shouldn't prevent consideration of this proposal.
> >
> > It could be possible to add additional compiler features that manage
> mutation through existing key-based subscripting without the copy-on-write
> problems of the current implementation. I don't know enough about how that
> would be implemented to speak to its feasibility or level of effort. Such a
> feature would reduce the need for a mutable DictionaryValues collection.
> > _______________________________________________
> > swift-evolution mailing list
> > swift-evolution at swift.org
> > https://lists.swift.org/mailman/listinfo/swift-evolution
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20161012/f237e0a5/attachment-0001.html>