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

[Dave Abrahams]

on Wed Oct 12 2016, Nate Cook <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.


> 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