[swift-evolution] [Proposal Draft] Provide Custom Collections for Dictionary Keys and Values

Wed Oct 12 18:01:08 CDT 2016

I agree that at least for stdlib purposes there’s something that looks like an explicit choice to make in-place mutation *available*. 

What I was trying to explain is whether or not in-place mutation *happens* is a bit implicit. It’s one thing to say that the difference here is just an idiom to know:

  var foo = [0, 1, 2, 3, 4, 5]

  // not in place:
  var slice = foo[1…3]
  slice.reverse() // `foo` not mutated

  // in place:
  foo[1…3].reverse() // `foo` mutated 

…but whether or not this function triggers an in-place mutation:

  func reverse<T>(_ slice: inout ArraySlice<T>) { 
   slice.reverse() 
  }

…depends on how it’s being called:

  var slice = foo[1…3]
  reverse(&slice) // `foo` unchanged

  reverse(&foo[1…3]) // `foo` mutated in-place

This seems consistent with the “in-place…or not?” behavior being largely just the usual COW, + the compiler eliding the typical retain/release on any sufficiently-transient slices; e.g. as if:

  // in place:
  foo[1…3].reverse() // `foo` mutated 

  // is treated as the equivalent of:
  @noretain var slice = foo[1…3]
  slice.reverse()

…where the @noretain is some (fictional) attribute suppressing the retain/release you’d otherwise trigger when `foo[1…3]` is stored into `slice`.

That’s the mental model it suggests, at least…and it just seemed unlikely that the compiler would be able to propagate something like `@noretain` onto a specific instance variable in a specific instance of a class-based view that captured a reference to the viewed collection’s underlying storage…whence the comment about class-based views. But I’ve been very wrong already today and probably am here as well.

As this is getting off-topic for something that seems like it’ll get postponed until later anyways I’d just like to say thanks again for taking the time to propose this, for correcting my misunderstandings…and that I’m eagerly looking forward to any improvements into COW visibility and any steps towards having more-explicit control over the COW mechanism.

> On Oct 12, 2016, at 1:11 PM, Károly Lőrentey <karoly at lorentey.hu> wrote:
> 
> I believe the implementation of efficient in-place mutation is very explicit in the code -- it is done by implementing DictionaryValue’s subscript using a special “mutableAddressWithNativeOwner” addressor instead of a normal setter. 
> 
> https://github.com/natecook1000/swift/blob/ed95aec4a20589a3b9c131f43444aa33705343cc/stdlib/public/core/HashedCollections.swift.gyb#L2169-L2173 <https://github.com/natecook1000/swift/blob/ed95aec4a20589a3b9c131f43444aa33705343cc/stdlib/public/core/HashedCollections.swift.gyb#L2169-L2173>
> 
> AFAICU this would also work if DictionaryValue was a reference type. 
> 
> Unfortunately, as far as I know, these addressors aren’t available outside stdlib, so custom collections cannot currently implement such mutable views (including mutable ranges) in a similarly efficient way. 
> 
> We can, however, approximate a similar effect outside of stdlib by designing closure-based APIs like `mydict.withValues { values in values[i] = 42 }`, in which the collection moves its storage to the view while the closure is executing (temporarily making its own contents disappear / appear invalid). The syntax and underlying mental model is perhaps not as nice, but (assuming the compiler is able to optimize away the nonescaping closure) we can achieve some of the performance benefits. 
> 
>> On 2016-10-12, at 19:17, plx via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
>> 
>> Thanks for the quick reply; given that I’m quite wrong about the important mechanics I rescind my criticisms.
>> 
>> I will say I care about this enough to reply because the inability to do in-place mutation of dictionary values has been an incredibly frustrating limitation and I’d just assumed the situation with slices/views would necessarily have similar issues for similar reasons…but glad to learn it’s not what I thought!
>> 
>> That said, I think efficient in-place mutation is too important to only expose so implicitly (seemingly due to the compiler eliding the otherwise-expected retain increments when the view is sufficiently “transient”…which seems like you perhaps can’t have an "in-place capable" view that’s implemented as a class, I’d think).
>> 
>> But none of this impacts my change to being in support for the proposal.
>> 
>>> On Oct 12, 2016, at 10:07 AM, Nate Cook <natecook at gmail.com <mailto:natecook at gmail.com>> wrote:
>>> 
>>> 
>>>> On Oct 12, 2016, at 9:32 AM, plx via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
>>>> 
>>>> The issue addressed is real; I’m not sure this is the best approach. 
>>>> 
>>>> In particular, unless I’m missing something obvious, the ownership strategy here would have to be:
>>>> 
>>>> - `DictionaryKeys` and `DictionaryValues` would each induce the expected +1 retain on the underlying storage
>>>> - `DictionaryValues`’s mutations avoid triggering COW on the underlying storage by skipping the usual ownership check
>>>> 
>>>> …as otherwise it’s unclear how you’d do those in-place mutations (and this seems to be how the implementation works...is that correct?).
>>> 
>>> That's not quite right—when you access these views through the dictionary, they do not increment the storage retain count. This is the way slicing and views currently work on other mutable types. For example, when you reverse a slice of an array in-place, the slice doesn't get its own duplicate storage:
>>> 
>>> var a = Array(1...10)
>>> a[0..<5].reverse()
>>> a == [5, 4, 3, 2, 1, 6, 7, 8, 9, 10]
>>> 
>>> However, if you create a new variable out of the slice and reverse that, the slice does get its own storage:
>>> 
>>> var b = Array(1...10)
>>> var bSlice = b[0..<5]
>>> bSlice.reverse()
>>> bSlice == [5, 4, 3, 2, 1]
>>> b == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> 
>>> Strings and their views work the same way:
>>> 
>>> var s = "abcdefg"
>>> s.characters.append("H")   // storage updated in place
>>> s == "abcdefgH"
>>> 
>>> var sChars = s.characters  // no copy yet
>>> sChars.removeLast()     // sChars gets its own copy before the mutation
>>> s == "abcdefgH"
>>> String(sChars) == "abcdefg"
>>> 
>>> var t = s   // no copy yet
>>> t.characters.removeLast()  // t gets a new copy here
>>> s == "abcdefgH"
>>> t == "abcdefg"
>>> 
>>> I don't know the name of the compiler feature that enables this, but it's a critical part of the way views and slices work.
>>> 
>>>> With that design, it seems like you’d wind up allowing things like the below:
>>>> 
>>>>   // example A
>>>>   let foo = [ “abc”: [1,2,3], “efg”: [4,5,6] ]
>>>>   let bar = foo // shared storage, no COW
>>>>   foo.values[foo.index(of: “abc”)!].append(789) // update shared storage, no COW
>>>> 
>>>>   // shared storage mutated,
>>>>   // despite (a) both being `let` and (b) only foo.values getting touched
>>>>   foo[“abc”] // [1, 2, 3, 789]
>>>>   bar[“abc”] // [1, 2, 3, 789]
>>> 
>>> Example A isn't allowed—if foo and bar are both immutable, both of their `values` collections are also immutable, so there's no way to modify their shared storage.
>>> 
>>>>   // example B
>>>>   var foo = [ “abc”: [1,2,3], “efg”: [4,5,6] ]
>>>>   var bar = foo // shared storage, no COW
>>>>   foo.values[foo.index(of: “abc”)!].append(789)
>>>> 
>>>>   // shared storage mutated only foo.values getting touched
>>>>   foo[“abc”] // [1, 2, 3, 789]
>>>>   bar[“abc”] // [1, 2, 3, 789]
>>> 
>>> Example B is incorrect—the mutation at `foo.values[...].append(789)` triggers a copy of the entire dictionary's underlying storage before allowing the mutation, since it knows that storage isn't uniquely referenced.
>>> 
>>>>   // example C
>>>>   var foo = [ “abc”: [1,2,3], “efg”: [4,5,6] ]
>>>>   var bar = foo 
>>>>   bar[“abc”] = [1, 2, 3, 4] // COW triggered here, no shared storage
>>>>   foo.values[foo.index(of: “abc”)!].append(789)
>>>> 
>>>>   // only `foo`’s storage mutated, b/c change to `bar` triggered COW
>>>>   foo[“abc”] // [1, 2, 3, 789]
>>>>   bar[“abc”] // [1, 2, 3, 4]
>>> 
>>> This is the current behavior and would remain the same after the proposed the changes.
>>> 
>>>> …where both A (by itself) and the B/C contrast seem very unwelcome.
>>>> 
>>>> Also, even if we assume we only ever make *responsible* use, having the stdlib include such directly-mutating views would seem likely to complicate any future concurrency plans.
>>>> 
>>>> To reiterate, I think the issue being addressed here is extremely important…I just don’t think I can get behind this type of solution (unless I’m grossly misunderstanding its mechanics).
>>> 
>>> Nate
>>> 
>> 
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org <mailto: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/a7d6fef2/attachment.html>