[swift-evolution] [Proposal Draft] Provide Custom Collections for Dictionary Keys and Values
T.J. Usiyan
griotspeak at gmail.com
Wed Oct 12 06:52:57 CDT 2016
+1 from me. Seems like a solid change.
On Wed, Oct 12, 2016 at 12:39 AM, Jacob Bandes-Storch via swift-evolution <
swift-evolution at swift.org> wrote:
> +1. Haven't hit this issue personally, but I agree it's important and the
> proposed solution seems like the right fix.
>
> On Tue, Oct 11, 2016 at 2:28 PM, 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.
>>
>> <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:
>>
>> // Performantif 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 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/44ad4638/attachment.html>
More information about the swift-evolution
mailing list