[swift-evolution] How does "Sequence.joined" work?

[Daryle Walker]

> On Aug 9, 2017, at 12:19 PM, Taylor Swift <kelvin13ma at gmail.com> wrote:
> 
> On Wed, Aug 9, 2017 at 10:43 AM, Daryle Walker via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
> 
>> On Aug 8, 2017, at 6:45 PM, Geordie Jay <geojay at gmail.com <mailto:geojay at gmail.com>> wrote:
>> 
>> Daryle Walker via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> schrieb am Di. 8. Aug. 2017 um 21:25:
>>> On Aug 8, 2017, at 12:35 AM, Félix Cloutier <felixcloutier at icloud.com <mailto:felixcloutier at icloud.com>> wrote:
>>> 
>>> All this means is that `joined()` does not create an array that contains the new result. It's only as magic as the COW semantics on arrays.
>> 
>> So you’re saying the COW semantics for Array and other standard library types have secret references/pointers that work even for “let”-mode objects, and the Sequence variants the various forms of “joined” need use a Sequence/Collection of those secret references?
>> 
>> I know nothing about this specific type under the hood and your question stumped me when I first saw it as well, so take this with a grain of salt:
>> 
>> I think it's basically just storing the arrays internally (as let) and when you iterate through the collection it just goes through the subsequences one by one, when the last index of the first is reached it begins with the next subsequence.
>> 
>> As for how it avoids creating new storage, simple. As someone else mentioned, this is no more magic than Copy On Write for normal arrays.
>> 
>> let a = [1,2,3]
>> let b = a // this doesn't produce a copy of the underlying buffer.. I.e. value semantics but only one buffer needed
>> 
>> ^^^ This is the take-home message. And your intuition about COW is correct: its internal storage is a reference type containing a buffer pointer. When (and only when) a mutation occurs, the buffer is copied and the new storage becomes the backing for the resulting struct. Any existing copies remain unchanged (and truly immutable) because they keep their original storage.
>> 
>> https://github.com/apple/swift/blob/master/stdlib/public/core/ContiguousArrayBuffer.swift <https://github.com/apple/swift/blob/master/stdlib/public/core/ContiguousArrayBuffer.swift>
>> 
>> 
>> So with that understanding of COW, it becomes easy to imagine all sorts of containers that don't require additional storage for their contents:
>> 
>> struct JoinedSequenceOfThreeArrays<T> {
>>   let array1: [T]
>>   let array2: [T]
>>   let array3: [T]
>> }
>> 
>> // still only one array buffer storage is required for all of this:
>> let c = JoinedSequenceOfThreeArrays(array1: a, array2: a, array3: b)
>> 
>> Does that make sense?
> 
> Mostly, then I realized a flaw with this explanation. Your theory implies that “joined” avoids creating new storage by betraying that and actually copying the containers, but said containers use-COW/reference-remote-storage themselves. Then what happens when a Sequence uses scoped storage for its items? (Example: the mythical “just slap Collection on a tuple and call it an array” type.) Either “joined” uses a different no-copy technique or it’s lying about saving on storage (and the lack of scoped-storage Sequences means no one has called them on it yet).
> 
> I don’t see any contradiction here. A tuple is a value type; it has no concept of copy-on-write because it’s copy-on-read. So JoinedSequence will store a copy of the tuple instead of a buffer reference

Besides meaning the explanation for “joined” is lying, what if the value type is large enough that copies should be minimized?

Hmm, it seems that there’s a hole in the language in that value-type “let”-mode instances cannot be aliased/referenced.

— 
Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170809/51eb2620/attachment.html>