Ah, I see plx has already brought this up. So this is a bug in the 
implementation, and (presumably) DictionaryValue’s mutable subscript addressor 
is supposed to take care of COW semantics without introducing needless copying.

(It’s too bad we aren’t supposed to use these magical addressors outside 
stdlib; the same issues tend to come up in custom collections, too.) :-(


> On 2016-10-12, at 17:58, Károly Lőrentey via swift-evolution 
> <swift-evolution@swift.org> wrote:
> 
> I think this is a lovely approach to solving this API design problem.
> 
> One thing I don’t quite understand yet is how these kinds of mutable views 
> interact with copy on write semantics. COW rules can be subtle, and these 
> views seem to put an extra twist on top that seems hard to understand/explain.
> 
> I would expect DictionaryValues to behave like a separate copy of the 
> dictionary:
> 
>    var dict = [“foo”: 1, “bar”: 2]
>    let i = dict.keys.index(of: “foo”)!
>    var values = dict.values
>    values[i] = 42         // COW copy
>    print(dict[“foo”])     // => 1
>    dict.values = values   // Original storage is released
>    print(dict[“foo”])     // => 42
> 
> Given that `values` contains a strong reference to the storage, I was curious 
> to find out how this copy is elided when we write `dict.values[i] = 42`. So I 
> tried building your branch, and I found that mutating `values` has an 
> immediate effect on the dictionary as well:
> 
>    let dict = [“foo”: 1, “bar”: 2]     // Note let, not var
>    let copy = dict
>    let i = dict.keys.index(of: “foo”)!
>    var values = dict.values
>    values[i] = 42         
>    print(dict[“foo”])     // => 42 (?!)
>    print(copy[“foo”])     // => 42 (?!?!)
> 
> This is not the intended behavior, right?
> 
> Károly
> 
>> On 2016-10-11, at 23:28, 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
> 
> _______________________________________________
> 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

Reply via email to