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

[Taylor Swift]

On Wed, Aug 9, 2017 at 10:43 AM, Daryle Walker via swift-evolution <
swift-evolution at swift.org> wrote:

>
> On Aug 8, 2017, at 6:45 PM, Geordie Jay <geojay at gmail.com> wrote:
>
>
> Daryle Walker via swift-evolution <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>
>> 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
>
>
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170809/49102121/attachment.html>