Looks very nice. +1 here as well. > On Oct 11, 2016, at 4:28 PM, 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. > > > <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 > https://lists.swift.org/mailman/listinfo/swift-evolution
_______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution
