Beautiful, +1
Rien
> On 11 Oct 2016, at 23:28, Nate Cook via swift-evolution
> <swift-evolution@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@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution
