> On Oct 11, 2016, at 5:06 PM, Braeden Profile <jhaezhy...@gmail.com> wrote: > > Awesome; +1. Does this address the lack of .init(keys:values:)? Would it > make that addition easier?
No, I don't think this has any bearing on that question. There's a separate proposal for that sort of initializer that was deferred from the Swift 3 evolution process (probably until stage 2 of Swift 4 since it's additive): https://github.com/apple/swift-evolution/blob/master/proposals/0100-add-sequence-based-init-and-merge-to-dictionary.md Nate >> On Oct 11, 2016, at 3:38 PM, Xiaodi Wu via swift-evolution >> <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote: >> >> Very elegant solution. Strong +1; no other feedback comes to mind atm. >> >> >> On Tue, Oct 11, 2016 at 4:28 PM, Nate Cook via swift-evolution >> <swift-evolution@swift.org <mailto: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. >> >> >> <https://gist.github.com/natecook1000/473720ba072fa5a0cd5e6c913de75fe1#motivation>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]] >> >> <https://gist.github.com/natecook1000/473720ba072fa5a0cd5e6c913de75fe1#inefficient-dictkeys-search>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:). >> >> >> <https://gist.github.com/natecook1000/473720ba072fa5a0cd5e6c913de75fe1#inefficient-value-mutation>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. >> >> >> <https://gist.github.com/natecook1000/473720ba072fa5a0cd5e6c913de75fe1#proposed-solution>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] >> } >> >> <https://gist.github.com/natecook1000/473720ba072fa5a0cd5e6c913de75fe1#detailed-design>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 >> <https://github.com/natecook1000/swift/tree/nc-dictionary>. >> >> >> <https://gist.github.com/natecook1000/473720ba072fa5a0cd5e6c913de75fe1#impact-on-existing-code>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. >> >> >> <https://gist.github.com/natecook1000/473720ba072fa5a0cd5e6c913de75fe1#alternatives-considered>Alternatives >> considered >> >> The Generics Manifesto >> <https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md> 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 <mailto:swift-evolution@swift.org> >> https://lists.swift.org/mailman/listinfo/swift-evolution >> <https://lists.swift.org/mailman/listinfo/swift-evolution> >> >> >> _______________________________________________ >> swift-evolution mailing list >> swift-evolution@swift.org <mailto: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
