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

[Nate Cook]

> On Oct 13, 2016, at 1:28 AM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
> 
> on Wed Oct 12 2016, Nate Cook <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
> 
>>> On Oct 12, 2016, at 9:32 AM, plx via swift-evolution <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]
> 
> Oh, yes it certainly does.  This is currently inefficient because
> pinning is tied to addressors and addressors can only return pointers to
> things that actually exist in memory somewhere.  The slice doesn't.

Ack, sorry everyone! Listen to Dave. 

I got carried away with examples that went further than my proposal. As far as I can tell from my testing, the examples in the proposal are still accurate.

>> 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]
> 
> This doesn't demonstrate anything; you're just showing the effects of
> value semantics.  If you go
> 
> b[0..<5] = bSlice
> 
> you'll then have
> 
> b == [5, 4, 3, 2, 1, 6, 7, 8, 9, 10]
> 
> And that is exactly what happens in the first example.
> 
> This is a major flaw that prevents Swift's collection model from being
> fully general and efficient.  I think we will be fixing it, by fixing
> the way inout works, as a consequence of the work on ownership, for
> Swift 4.  But as noted elsewhere, that's a wild-ass guess at the moment.
> 
>> 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.
> 
> I wish :-)

😳

>>> 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
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>> 
> 
> -- 
> -Dave
> 
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org <mailto:swift-evolution at swift.org>
> https://lists.swift.org/mailman/listinfo/swift-evolution <https://lists.swift.org/mailman/listinfo/swift-evolution>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20161014/dc62b1d8/attachment.html>