Re: [swift-dev] copy-on-write proposal

[Erik Eckstein via swift-dev]

> On Oct 20, 2016, at 10:11 AM, Andrew Trick  wrote:
> 
> 
>> On Oct 20, 2016, at 8:41 AM, Erik Eckstein > > wrote:
>> 
>>> To clarify: I proposed an alternate approach in which the @sil_cow 
>>> reference is only mutable during the Array’s @inout scope—to be 
>>> automatically enforced by the compiler once @inout scopes are enforced. But 
>>> the text in question is not referring to that approach, so your comments 
>>> are on target.
>> 
>> After thinking about Joe’s suggestion (having the cow attribute on the class 
>> type and make a reference to that type move-only), I’m more inclined to go 
>> with the isUnique builtin. If such a reference can only be returned by 
>> isUnique, it is really guaranteed that only a uniquely referenced buffer can 
>> be mutated. With the inout approach, the programmer is not forced to make 
>> the uniqueness check before modifying the buffer.
> 
> 
> In my mind, relying on a move-only reference type is exactly what I was 
> advocating for, but relies on a language feature rather than a “special” 
> compiler verification.

Well, I think we are not blocked on this. We could just add a mandatory pass to 
check that there are no move-only violations. In the future a language feature 
might do this in a more elegant way in the type checker or whatever. But for 
now I believe we don’t need more than the attributes on the class type and the 
COW reference field.

> This all still needs to work with an ‘inout’ Array. The compiler will 
> effectively be doing the same verification that I was proposing but as a side 
> effect of move-only semantics (type system support makes it much easier). The 
> isUnique builtin would just be a mechanism to get the mutable type, and the 
> endUnique builtin is the mechanism to move the type back. As Dave pointed 
> out, we could provide additional mechanisms for mutation that don’t depend on 
> uniqueness. But the SIL optimizer doesn’t need to be explicitly taught about 
> any of those builtin mechanisms for correctness. More importantly, the user 
> is no longer responsible for some easy-to-violate, unverified property of the 
> data type as a whole.

I think we are more or less on the same page. All I’m saying is that the 
mutable reference can only be obtained by the isUnique/is_unique 
builtin/instruction (or by creating a new buffer).

> 
> -Andy

___
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev

Re: [swift-dev] copy-on-write proposal

[Andrew Trick via swift-dev]

> On Oct 20, 2016, at 8:41 AM, Erik Eckstein  wrote:
> 
>> To clarify: I proposed an alternate approach in which the @sil_cow reference 
>> is only mutable during the Array’s @inout scope—to be automatically enforced 
>> by the compiler once @inout scopes are enforced. But the text in question is 
>> not referring to that approach, so your comments are on target.
> 
> After thinking about Joe’s suggestion (having the cow attribute on the class 
> type and make a reference to that type move-only), I’m more inclined to go 
> with the isUnique builtin. If such a reference can only be returned by 
> isUnique, it is really guaranteed that only a uniquely referenced buffer can 
> be mutated. With the inout approach, the programmer is not forced to make the 
> uniqueness check before modifying the buffer.


In my mind, relying on a move-only reference type is exactly what I was 
advocating for, but relies on a language feature rather than a “special” 
compiler verification. This all still needs to work with an ‘inout’ Array. The 
compiler will effectively be doing the same verification that I was proposing 
but as a side effect of move-only semantics (type system support makes it much 
easier). The isUnique builtin would just be a mechanism to get the mutable 
type, and the endUnique builtin is the mechanism to move the type back. As Dave 
pointed out, we could provide additional mechanisms for mutation that don’t 
depend on uniqueness. But the SIL optimizer doesn’t need to be explicitly 
taught about any of those builtin mechanisms for correctness. More importantly, 
the user is no longer responsible for some easy-to-violate, unverified property 
of the data type as a whole.

-Andy___
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev

Re: [swift-dev] copy-on-write proposal

[Erik Eckstein via swift-dev]

> On Oct 20, 2016, at 8:51 AM, Dave Abrahams  wrote:
> 
> We might want to leave some room in the design for a shared atomic cache 
> reference to live in the buffer, FWIW. It would have to be mutable even when 
> the buffer was multiply-referenced 

Should be no problem with an attribute on that field. Like ‘mutable' in C++.
> 
> Sent from my moss-covered three-handled family gradunza
> 
> On Oct 20, 2016, at 8:41 AM, Erik Eckstein  > wrote:
> 
>> 
>>> On Oct 19, 2016, at 6:36 PM, Andrew Trick via swift-dev 
>>> > wrote:
>>> 
 
 On Oct 19, 2016, at 10:13 AM, Dave Abrahams via swift-dev 
 > wrote:
 
 
 on Tue Oct 18 2016, Erik Eckstein >>> > wrote:
 
>> On Oct 17, 2016, at 10:21 AM, Dave Abrahams > > wrote:
>> 
>> 
>> on Mon Oct 17 2016, Erik Eckstein > > wrote:
>> 
> 
>>> On Oct 16, 2016, at 2:05 PM, Dave Abrahams via swift-dev 
>>> > wrote:
>>> 
 on Thu Oct 13 2016, Joe Groff >>>  >> wrote:
 
>> On Oct 11, 2016, at 4:48 PM, Erik Eckstein via swift-dev 
>> > wrote:
>> 
>> This is a proposal for representing copy-on-write buffers in
>> SIL. Actually it’s still a draft for a proposal. It also heavily
>> depends on how we move forward with SIL ownership.
>> 
>> If you have any comments, please let me know.
> 
> The SIL-level design seems sensible to me at a glance. At the language
> level, I think it would make more sense to treat this as an attribute
> on class types rather than on properties in structs using the class. I
> don't think many people reuse class definitions as both shared
> reference types and as value type payloads, 
 
 Foundation does, or would if they could.
 
> but beyond that, I think that making it an attribute of classes would
> put us into a better position to leverage the borrow model to enforce
> the "mutable-only-when-unique" aspect of COW implementations. John
> alluded to this in the "SIL address types and borrowing" thread:
> 
>> I wonder if it would make more sense to make copy-on-write buffer
>> references a move-only type, so that as long as you were just
>> working with the raw reference (as opposed to the CoW aggregate,
>> which would remain copyable) it wouldn't get implicitly copied
>> anymore.  You could have mutable and immutable buffer reference
>> types, both move-only, and there could be a consuming checkUnique
>> operation on the immutable one that, I dunno, returned an Either of
>> the mutable and immutable versions.
>> 
>> For CoW aggregates, you'd need some @copied attribute on the field
>> to make sure that the CoW attribute was still copyable.  Within the
>> implementation of the type, though, you would be projecting out the
>> reference immediately, and thereafter you'd be certain that you were
>> borrowing / moving it around as appropriate.
> 
> If 'copy-on-write' were a trait on classes, then we could distinguish
> unique and nonunique references to the class. A unique reference would
> act like a move-only type to prevent accidental loss of uniqueness. 
 
 +1
 
> We can also allow a copy-on-write class to have "mutating" methods,
> and only allow mutation on unique references. It seems to me like,
> exploring this direction, we could also come up with a way for the
> high-level value-semantics operations on the struct to statically
> indicate which methods are known to leave the value's buffers in a
> unique state, or which return values that are uniquely owned, which
> would give the optimizer more ability to avoid uniqueness checks
> across calls without relying on inlining and IPO.
 
 That's pretty cool.  However, I think there's nothing to prevent any
 mutating method from storing a copy of self in a global, so I think 
 we'd
 need some participation from the programmer (either an agreement not to
 do that, or an explicit claim of uniqueness on exit) in order to
 identify operations that create/preserve uniqueness.
>>> 
>>> If a mutating reference (like self in a mutating method) is move-only
>>> then you would not 

Re: [swift-dev] copy-on-write proposal

[Dave Abrahams via swift-dev]

We might want to leave some room in the design for a shared atomic cache 
reference to live in the buffer, FWIW. It would have to be mutable even when 
the buffer was multiply-referenced 

Sent from my moss-covered three-handled family gradunza

> On Oct 20, 2016, at 8:41 AM, Erik Eckstein  wrote:
> 
> 
>>> On Oct 19, 2016, at 6:36 PM, Andrew Trick via swift-dev 
>>>  wrote:
>>> 
>>> 
>>> On Oct 19, 2016, at 10:13 AM, Dave Abrahams via swift-dev 
>>>  wrote:
>>> 
>>> 
>>> on Tue Oct 18 2016, Erik Eckstein  wrote:
>>> 
> On Oct 17, 2016, at 10:21 AM, Dave Abrahams  wrote:
> 
> 
> on Mon Oct 17 2016, Erik Eckstein  wrote:
> 
 
>>> On Oct 16, 2016, at 2:05 PM, Dave Abrahams via swift-dev 
>>>  wrote:
>>> 
>>> on Thu Oct 13 2016, Joe Groff >> > wrote:
>>> 
> On Oct 11, 2016, at 4:48 PM, Erik Eckstein via swift-dev 
>  wrote:
> 
> This is a proposal for representing copy-on-write buffers in
> SIL. Actually it’s still a draft for a proposal. It also heavily
> depends on how we move forward with SIL ownership.
> 
> If you have any comments, please let me know.
 
 The SIL-level design seems sensible to me at a glance. At the language
 level, I think it would make more sense to treat this as an attribute
 on class types rather than on properties in structs using the class. I
 don't think many people reuse class definitions as both shared
 reference types and as value type payloads, 
>>> 
>>> Foundation does, or would if they could.
>>> 
 but beyond that, I think that making it an attribute of classes would
 put us into a better position to leverage the borrow model to enforce
 the "mutable-only-when-unique" aspect of COW implementations. John
 alluded to this in the "SIL address types and borrowing" thread:
 
> I wonder if it would make more sense to make copy-on-write buffer
> references a move-only type, so that as long as you were just
> working with the raw reference (as opposed to the CoW aggregate,
> which would remain copyable) it wouldn't get implicitly copied
> anymore.  You could have mutable and immutable buffer reference
> types, both move-only, and there could be a consuming checkUnique
> operation on the immutable one that, I dunno, returned an Either of
> the mutable and immutable versions.
> 
> For CoW aggregates, you'd need some @copied attribute on the field
> to make sure that the CoW attribute was still copyable.  Within the
> implementation of the type, though, you would be projecting out the
> reference immediately, and thereafter you'd be certain that you were
> borrowing / moving it around as appropriate.
 
 If 'copy-on-write' were a trait on classes, then we could distinguish
 unique and nonunique references to the class. A unique reference would
 act like a move-only type to prevent accidental loss of uniqueness. 
>>> 
>>> +1
>>> 
 We can also allow a copy-on-write class to have "mutating" methods,
 and only allow mutation on unique references. It seems to me like,
 exploring this direction, we could also come up with a way for the
 high-level value-semantics operations on the struct to statically
 indicate which methods are known to leave the value's buffers in a
 unique state, or which return values that are uniquely owned, which
 would give the optimizer more ability to avoid uniqueness checks
 across calls without relying on inlining and IPO.
>>> 
>>> That's pretty cool.  However, I think there's nothing to prevent any
>>> mutating method from storing a copy of self in a global, so I think we'd
>>> need some participation from the programmer (either an agreement not to
>>> do that, or an explicit claim of uniqueness on exit) in order to
>>> identify operations that create/preserve uniqueness.
>> 
>> If a mutating reference (like self in a mutating method) is move-only
>> then you would not be able to “copy” it to a global.
> 
> Yes, a reference to a move-only type would work for this purpose.
> 
> 
>>> On Oct 16, 2016, at 2:01 PM, Dave Abrahams via swift-dev 
>>>  wrote:
>>> 
>>> 
>>> on Tue Oct 11 2016, Erik Eckstein  wrote:
>>> 
 This is a proposal for representing copy-on-write buffers in
 SIL. Actually it’s still a draft for a proposal. It also heavily
 depends on how we move forward with SIL ownership.
 
 :orphan:
 
 .. highlight:: sil
 

Re: [swift-dev] copy-on-write proposal

[Erik Eckstein via swift-dev]

> On Oct 19, 2016, at 6:36 PM, Andrew Trick via swift-dev  
> wrote:
> 
>> 
>> On Oct 19, 2016, at 10:13 AM, Dave Abrahams via swift-dev 
>> > wrote:
>> 
>> 
>> on Tue Oct 18 2016, Erik Eckstein > > wrote:
>> 
 On Oct 17, 2016, at 10:21 AM, Dave Abrahams > wrote:
 
 
 on Mon Oct 17 2016, Erik Eckstein >>> > wrote:
 
>>> 
> On Oct 16, 2016, at 2:05 PM, Dave Abrahams via swift-dev 
> > wrote:
> 
>> on Thu Oct 13 2016, Joe Groff >  > >> wrote:
>> 
 On Oct 11, 2016, at 4:48 PM, Erik Eckstein via swift-dev 
 > wrote:
 
 This is a proposal for representing copy-on-write buffers in
 SIL. Actually it’s still a draft for a proposal. It also heavily
 depends on how we move forward with SIL ownership.
 
 If you have any comments, please let me know.
>>> 
>>> The SIL-level design seems sensible to me at a glance. At the language
>>> level, I think it would make more sense to treat this as an attribute
>>> on class types rather than on properties in structs using the class. I
>>> don't think many people reuse class definitions as both shared
>>> reference types and as value type payloads, 
>> 
>> Foundation does, or would if they could.
>> 
>>> but beyond that, I think that making it an attribute of classes would
>>> put us into a better position to leverage the borrow model to enforce
>>> the "mutable-only-when-unique" aspect of COW implementations. John
>>> alluded to this in the "SIL address types and borrowing" thread:
>>> 
 I wonder if it would make more sense to make copy-on-write buffer
 references a move-only type, so that as long as you were just
 working with the raw reference (as opposed to the CoW aggregate,
 which would remain copyable) it wouldn't get implicitly copied
 anymore.  You could have mutable and immutable buffer reference
 types, both move-only, and there could be a consuming checkUnique
 operation on the immutable one that, I dunno, returned an Either of
 the mutable and immutable versions.
 
 For CoW aggregates, you'd need some @copied attribute on the field
 to make sure that the CoW attribute was still copyable.  Within the
 implementation of the type, though, you would be projecting out the
 reference immediately, and thereafter you'd be certain that you were
 borrowing / moving it around as appropriate.
>>> 
>>> If 'copy-on-write' were a trait on classes, then we could distinguish
>>> unique and nonunique references to the class. A unique reference would
>>> act like a move-only type to prevent accidental loss of uniqueness. 
>> 
>> +1
>> 
>>> We can also allow a copy-on-write class to have "mutating" methods,
>>> and only allow mutation on unique references. It seems to me like,
>>> exploring this direction, we could also come up with a way for the
>>> high-level value-semantics operations on the struct to statically
>>> indicate which methods are known to leave the value's buffers in a
>>> unique state, or which return values that are uniquely owned, which
>>> would give the optimizer more ability to avoid uniqueness checks
>>> across calls without relying on inlining and IPO.
>> 
>> That's pretty cool.  However, I think there's nothing to prevent any
>> mutating method from storing a copy of self in a global, so I think we'd
>> need some participation from the programmer (either an agreement not to
>> do that, or an explicit claim of uniqueness on exit) in order to
>> identify operations that create/preserve uniqueness.
> 
> If a mutating reference (like self in a mutating method) is move-only
> then you would not be able to “copy” it to a global.
 
 Yes, a reference to a move-only type would work for this purpose.
 
 
>> On Oct 16, 2016, at 2:01 PM, Dave Abrahams via swift-dev 
>> > wrote:
>> 
>> 
>> on Tue Oct 11 2016, Erik Eckstein > > wrote:
>> 
>>> This is a proposal for representing copy-on-write buffers in
>>> SIL. Actually it’s still a draft for a proposal. It also heavily
>>> depends on how we move forward with SIL ownership.
>>> 
>>> :orphan:
>>> 
>>> .. highlight:: sil
>>> 
>>> ===
>>> Copy-On-Write Representation in SIL
>>> 

Re: [swift-dev] copy-on-write proposal

[Andrew Trick via swift-dev]

> On Oct 19, 2016, at 10:13 AM, Dave Abrahams via swift-dev 
>  wrote:
> 
> 
> on Tue Oct 18 2016, Erik Eckstein  > wrote:
> 
>>> On Oct 17, 2016, at 10:21 AM, Dave Abrahams  wrote:
>>> 
>>> 
>>> on Mon Oct 17 2016, Erik Eckstein  wrote:
>>> 
>> 
 On Oct 16, 2016, at 2:05 PM, Dave Abrahams via swift-dev 
  wrote:
 
> on Thu Oct 13 2016, Joe Groff  > wrote:
> 
>>> On Oct 11, 2016, at 4:48 PM, Erik Eckstein via swift-dev 
>>>  wrote:
>>> 
>>> This is a proposal for representing copy-on-write buffers in
>>> SIL. Actually it’s still a draft for a proposal. It also heavily
>>> depends on how we move forward with SIL ownership.
>>> 
>>> If you have any comments, please let me know.
>> 
>> The SIL-level design seems sensible to me at a glance. At the language
>> level, I think it would make more sense to treat this as an attribute
>> on class types rather than on properties in structs using the class. I
>> don't think many people reuse class definitions as both shared
>> reference types and as value type payloads, 
> 
> Foundation does, or would if they could.
> 
>> but beyond that, I think that making it an attribute of classes would
>> put us into a better position to leverage the borrow model to enforce
>> the "mutable-only-when-unique" aspect of COW implementations. John
>> alluded to this in the "SIL address types and borrowing" thread:
>> 
>>> I wonder if it would make more sense to make copy-on-write buffer
>>> references a move-only type, so that as long as you were just
>>> working with the raw reference (as opposed to the CoW aggregate,
>>> which would remain copyable) it wouldn't get implicitly copied
>>> anymore.  You could have mutable and immutable buffer reference
>>> types, both move-only, and there could be a consuming checkUnique
>>> operation on the immutable one that, I dunno, returned an Either of
>>> the mutable and immutable versions.
>>> 
>>> For CoW aggregates, you'd need some @copied attribute on the field
>>> to make sure that the CoW attribute was still copyable.  Within the
>>> implementation of the type, though, you would be projecting out the
>>> reference immediately, and thereafter you'd be certain that you were
>>> borrowing / moving it around as appropriate.
>> 
>> If 'copy-on-write' were a trait on classes, then we could distinguish
>> unique and nonunique references to the class. A unique reference would
>> act like a move-only type to prevent accidental loss of uniqueness. 
> 
> +1
> 
>> We can also allow a copy-on-write class to have "mutating" methods,
>> and only allow mutation on unique references. It seems to me like,
>> exploring this direction, we could also come up with a way for the
>> high-level value-semantics operations on the struct to statically
>> indicate which methods are known to leave the value's buffers in a
>> unique state, or which return values that are uniquely owned, which
>> would give the optimizer more ability to avoid uniqueness checks
>> across calls without relying on inlining and IPO.
> 
> That's pretty cool.  However, I think there's nothing to prevent any
> mutating method from storing a copy of self in a global, so I think we'd
> need some participation from the programmer (either an agreement not to
> do that, or an explicit claim of uniqueness on exit) in order to
> identify operations that create/preserve uniqueness.
 
 If a mutating reference (like self in a mutating method) is move-only
 then you would not be able to “copy” it to a global.
>>> 
>>> Yes, a reference to a move-only type would work for this purpose.
>>> 
>>> 
> On Oct 16, 2016, at 2:01 PM, Dave Abrahams via swift-dev 
>  wrote:
> 
> 
> on Tue Oct 11 2016, Erik Eckstein  wrote:
> 
>> This is a proposal for representing copy-on-write buffers in
>> SIL. Actually it’s still a draft for a proposal. It also heavily
>> depends on how we move forward with SIL ownership.
>> 
>> :orphan:
>> 
>> .. highlight:: sil
>> 
>> ===
>> Copy-On-Write Representation in SIL
>> ===
>> 
>> .. contents::
>> 
>> Overview
>> 
>> 
>> This document proposes:
>> 
>> - An ownership attribute to define copy-on-write (COW) buffers in Swift 
>> data
>> types.
>> 
>> - A representation of COW buffers in SIL so that optimizations can take 
>> benefit
>> of it.
>> 
>> The basic idea is to enable the SIL optimizer to reason about COW data 
>> types
>> in the same way as a 

Re: [swift-dev] copy-on-write proposal

[Erik Eckstein via swift-dev]

On Oct 16, 2016, at 2:05 PM, Dave Abrahams via swift-dev  
wrote:


> on Thu Oct 13 2016, Joe Groff  > wrote:
> 
>>> On Oct 11, 2016, at 4:48 PM, Erik Eckstein via swift-dev 
>>>  wrote:
>>> 
>>> This is a proposal for representing copy-on-write buffers in
>>> SIL. Actually it’s still a draft for a proposal. It also heavily
>>> depends on how we move forward with SIL ownership.
>>> 
>>> If you have any comments, please let me know.
>> 
>> The SIL-level design seems sensible to me at a glance. At the language
>> level, I think it would make more sense to treat this as an attribute
>> on class types rather than on properties in structs using the class. I
>> don't think many people reuse class definitions as both shared
>> reference types and as value type payloads, 
> 
> Foundation does, or would if they could.
> 
>> but beyond that, I think that making it an attribute of classes would
>> put us into a better position to leverage the borrow model to enforce
>> the "mutable-only-when-unique" aspect of COW implementations. John
>> alluded to this in the "SIL address types and borrowing" thread:
>> 
>>> I wonder if it would make more sense to make copy-on-write buffer
>>> references a move-only type, so that as long as you were just
>>> working with the raw reference (as opposed to the CoW aggregate,
>>> which would remain copyable) it wouldn't get implicitly copied
>>> anymore.  You could have mutable and immutable buffer reference
>>> types, both move-only, and there could be a consuming checkUnique
>>> operation on the immutable one that, I dunno, returned an Either of
>>> the mutable and immutable versions.
>>> 
>>> For CoW aggregates, you'd need some @copied attribute on the field
>>> to make sure that the CoW attribute was still copyable.  Within the
>>> implementation of the type, though, you would be projecting out the
>>> reference immediately, and thereafter you'd be certain that you were
>>> borrowing / moving it around as appropriate.
>> 
>> If 'copy-on-write' were a trait on classes, then we could distinguish
>> unique and nonunique references to the class. A unique reference would
>> act like a move-only type to prevent accidental loss of uniqueness. 
> 
> +1
> 
>> We can also allow a copy-on-write class to have "mutating" methods,
>> and only allow mutation on unique references. It seems to me like,
>> exploring this direction, we could also come up with a way for the
>> high-level value-semantics operations on the struct to statically
>> indicate which methods are known to leave the value's buffers in a
>> unique state, or which return values that are uniquely owned, which
>> would give the optimizer more ability to avoid uniqueness checks
>> across calls without relying on inlining and IPO.
> 
> That's pretty cool.  However, I think there's nothing to prevent any
> mutating method from storing a copy of self in a global, so I think we'd
> need some participation from the programmer (either an agreement not to
> do that, or an explicit claim of uniqueness on exit) in order to
> identify operations that create/preserve uniqueness.

If a mutating reference (like self in a mutating method) is move-only then you 
would not be able to “copy” it to a global.

> 
> 
> On Oct 16, 2016, at 2:01 PM, Dave Abrahams via swift-dev 
>  wrote:
> 
> 
> on Tue Oct 11 2016, Erik Eckstein  wrote:
> 
>> This is a proposal for representing copy-on-write buffers in
>> SIL. Actually it’s still a draft for a proposal. It also heavily
>> depends on how we move forward with SIL ownership.
>> 
>> :orphan:
>> 
>> .. highlight:: sil
>> 
>> ===
>> Copy-On-Write Representation in SIL
>> ===
>> 
>> .. contents::
>> 
>> Overview
>> 
>> 
>> This document proposes:
>> 
>> - An ownership attribute to define copy-on-write (COW) buffers in Swift data
>>  types.
>> 
>> - A representation of COW buffers in SIL so that optimizations can take 
>> benefit
>>  of it.
>> 
>> The basic idea is to enable the SIL optimizer to reason about COW data types
>> in the same way as a programmer can do.
>> This means: a COW buffer can only be modified by its owning SIL value, 
>> because
>> either it's uniquely referenced or the buffer is copied before modified.
>> 
>> .. note::
>>In the following the term "buffer" refers to a Swift heap object.
>>It can be any heap object, not necessarily a “buffer” with e.g. 
>> tail-allocated elements.
>> 
>> COW Types
>> =
>> 
>> The basic structure of COW data types can be simplified as follows::
>> 
>>class COWBuffer {
>>  var someData: Int
>>  ...
>>}
>> 
>>struct COWType {
>>  var b : COWBuffer
>> 
>>  mutating func change_it() {
>>if (!isUniquelyReferenced(b)) {
>>  b = copy_buffer(b)
>>}
>>b.someData = ...
>>  }
>>}
>> 
>> Currently the COW behavior of such 

Re: [swift-dev] copy-on-write proposal

[Dave Abrahams via swift-dev]

on Thu Oct 13 2016, Joe Groff  wrote:

>> On Oct 11, 2016, at 4:48 PM, Erik Eckstein via swift-dev 
>>  wrote:
>> 
>> This is a proposal for representing copy-on-write buffers in
>> SIL. Actually it’s still a draft for a proposal. It also heavily
>> depends on how we move forward with SIL ownership.
>> 
>> If you have any comments, please let me know.
>
> The SIL-level design seems sensible to me at a glance. At the language
> level, I think it would make more sense to treat this as an attribute
> on class types rather than on properties in structs using the class. I
> don't think many people reuse class definitions as both shared
> reference types and as value type payloads, 

Foundation does, or would if they could.

> but beyond that, I think that making it an attribute of classes would
> put us into a better position to leverage the borrow model to enforce
> the "mutable-only-when-unique" aspect of COW implementations. John
> alluded to this in the "SIL address types and borrowing" thread:
>
>> I wonder if it would make more sense to make copy-on-write buffer
>> references a move-only type, so that as long as you were just
>> working with the raw reference (as opposed to the CoW aggregate,
>> which would remain copyable) it wouldn't get implicitly copied
>> anymore.  You could have mutable and immutable buffer reference
>> types, both move-only, and there could be a consuming checkUnique
>> operation on the immutable one that, I dunno, returned an Either of
>> the mutable and immutable versions.
>> 
>> For CoW aggregates, you'd need some @copied attribute on the field
>> to make sure that the CoW attribute was still copyable.  Within the
>> implementation of the type, though, you would be projecting out the
>> reference immediately, and thereafter you'd be certain that you were
>> borrowing / moving it around as appropriate.
>
> If 'copy-on-write' were a trait on classes, then we could distinguish
> unique and nonunique references to the class. A unique reference would
> act like a move-only type to prevent accidental loss of uniqueness. 

+1

> We can also allow a copy-on-write class to have "mutating" methods,
> and only allow mutation on unique references. It seems to me like,
> exploring this direction, we could also come up with a way for the
> high-level value-semantics operations on the struct to statically
> indicate which methods are known to leave the value's buffers in a
> unique state, or which return values that are uniquely owned, which
> would give the optimizer more ability to avoid uniqueness checks
> across calls without relying on inlining and IPO.

That's pretty cool.  However, I think there's nothing to prevent any
mutating method from storing a copy of self in a global, so I think we'd
need some participation from the programmer (either an agreement not to
do that, or an explicit claim of uniqueness on exit) in order to
identify operations that create/preserve uniqueness.

-- 
-Dave

___
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev

Re: [swift-dev] copy-on-write proposal

[Erik Eckstein via swift-dev]

> On Oct 13, 2016, at 10:36 AM, Joe Groff  wrote:
> 
> 
>> On Oct 11, 2016, at 4:48 PM, Erik Eckstein via swift-dev 
>>  wrote:
>> 
>> This is a proposal for representing copy-on-write buffers in SIL. Actually 
>> it’s still a draft for a proposal. It also heavily depends on how we move 
>> forward with SIL ownership.
>> 
>> If you have any comments, please let me know.
> 
> The SIL-level design seems sensible to me at a glance. At the language level, 
> I think it would make more sense to treat this as an attribute on class types 
> rather than on properties in structs using the class. I don't think many 
> people reuse class definitions as both shared reference types and as value 
> type payloads, but beyond that, I think that making it an attribute of 
> classes would put us into a better position to leverage the borrow model to 
> enforce the "mutable-only-when-unique" aspect of COW implementations.

I think this makes sense. Although we would need an attribute on the field as 
well (what John called the @copied attribute).

> John alluded to this in the "SIL address types and borrowing" thread:
> 
>> I wonder if it would make more sense to make copy-on-write buffer references 
>> a move-only type, so that as long as you were just working with the raw 
>> reference (as opposed to the CoW aggregate, which would remain copyable) it 
>> wouldn't get implicitly copied anymore.  You could have mutable and 
>> immutable buffer reference types, both move-only, and there could be a 
>> consuming checkUnique operation on the immutable one that, I dunno, returned 
>> an Either of the mutable and immutable versions.
>> 
>> For CoW aggregates, you'd need some @copied attribute on the field to make 
>> sure that the CoW attribute was still copyable.  Within the implementation 
>> of the type, though, you would be projecting out the reference immediately, 
>> and thereafter you'd be certain that you were borrowing / moving it around 
>> as appropriate.
> 
> If 'copy-on-write' were a trait on classes, then we could distinguish unique 
> and nonunique references to the class. A unique reference would act like a 
> move-only type to prevent accidental loss of uniqueness. We can also allow a 
> copy-on-write class to have "mutating" methods, and only allow mutation on 
> unique references.

The only way to get a unique reference would then be to use the 
isUnique-builtin - or to create a new buffer. This is good, because we could 
statically check that the programmer can only modify uniquely referenced 
buffers (although to get full memory safety we would probably have  to 
invalidate the original buffer reference between the is_unique - end_unique 
scope, e.g. by storing a null pointer into it).

Thinking about this in detail I believe we have to change how a COW is 
implemented. For example we could not write back the unique reference and use 
it afterwards:

if let uniqueRef = isUnique() {
} else {
  uniqueRef = Buffer()
  cow.buffer = uniqueRef // <- this would not work. It’s a copy of a unique 
buffer
}
uniqueRef.someData = ...

Instead this could be done like

if let uniqueRef = isUnique() {
} else {
  uniqueRef = Buffer()
}
uniqueRef.someData = ...
cow.buffer = uniqueRef // OK, end of lifetime of uniqueRef

It would mean that we write back the buffer even in the unique-case, But I 
think this is ok.

For the implementation we would need two different reference types in the AST 
(unique and nonunique), right? Could this be just a different StorageType?

> It seems to me like, exploring this direction, we could also come up with a 
> way for the high-level value-semantics operations on the struct to statically 
> indicate which methods are known to leave the value's buffers in a unique 
> state, or which return values that are uniquely owned, which would give the 
> optimizer more ability to avoid uniqueness checks across calls without 
> relying on inlining and IPO.
> 
> -Joe

___
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev

Re: [swift-dev] copy-on-write proposal

[Joe Groff via swift-dev]

> On Oct 11, 2016, at 4:48 PM, Erik Eckstein via swift-dev 
>  wrote:
> 
> This is a proposal for representing copy-on-write buffers in SIL. Actually 
> it’s still a draft for a proposal. It also heavily depends on how we move 
> forward with SIL ownership.
> 
> If you have any comments, please let me know.

The SIL-level design seems sensible to me at a glance. At the language level, I 
think it would make more sense to treat this as an attribute on class types 
rather than on properties in structs using the class. I don't think many people 
reuse class definitions as both shared reference types and as value type 
payloads, but beyond that, I think that making it an attribute of classes would 
put us into a better position to leverage the borrow model to enforce the 
"mutable-only-when-unique" aspect of COW implementations. John alluded to this 
in the "SIL address types and borrowing" thread:

> I wonder if it would make more sense to make copy-on-write buffer references 
> a move-only type, so that as long as you were just working with the raw 
> reference (as opposed to the CoW aggregate, which would remain copyable) it 
> wouldn't get implicitly copied anymore.  You could have mutable and immutable 
> buffer reference types, both move-only, and there could be a consuming 
> checkUnique operation on the immutable one that, I dunno, returned an Either 
> of the mutable and immutable versions.
> 
> For CoW aggregates, you'd need some @copied attribute on the field to make 
> sure that the CoW attribute was still copyable.  Within the implementation of 
> the type, though, you would be projecting out the reference immediately, and 
> thereafter you'd be certain that you were borrowing / moving it around as 
> appropriate.

If 'copy-on-write' were a trait on classes, then we could distinguish unique 
and nonunique references to the class. A unique reference would act like a 
move-only type to prevent accidental loss of uniqueness. We can also allow a 
copy-on-write class to have "mutating" methods, and only allow mutation on 
unique references. It seems to me like, exploring this direction, we could also 
come up with a way for the high-level value-semantics operations on the struct 
to statically indicate which methods are known to leave the value's buffers in 
a unique state, or which return values that are uniquely owned, which would 
give the optimizer more ability to avoid uniqueness checks across calls without 
relying on inlining and IPO.

-Joe
___
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev

Re: [swift-dev] copy-on-write proposal

[Andrew Trick via swift-dev]

> On Oct 12, 2016, at 11:19 AM, Alexis via swift-dev  
> wrote:
> 
> I’m having trouble figuring something out: is all of this contingent on all 
> of the relevant operations being completely inlined into a single function at 
> the SIL level? Could failing to inline a standard library function lead to 
> performance cliffs? I understand this is generally true of inlining and 
> dead-code elimination; but I’m wondering how this affects the abstractions we 
> expose. Can we know that some things will “always” work, even if parts aren’t 
> inlined?

Well, actually there are two basic approaches that you see within the SIL 
optimizer. One relies on being able to analyze all instructions between two 
points in the CFG. That depends on full inlining or deep IPA. The other 
approach relies on knowledge about aliasing, uniqueness, immutability, and so 
on reach a conclusion about some opaque region of code.

Some of our optimizations rely on full inlining and conservative analysis, but 
the more we can capture semantics in SIL, the more we can employ the second 
approach, which improves the power and robustness of the optimizer.

Erik proposed redundant-load elimination and ARC optimizations that both need 
to prove the absence of a store to a particular memory location within some 
region. With the proposed copy-on-write attribute, we can now prove the absence 
of a store without analyzing any of the instructions in that region. I think 
this is an good example of the second approach where we can optimize around 
opaque regions of code. So it’s worth making sure our representation supports 
that.

It is still true though that enough inlining needs to take place such that we 
can see a load of the Array storage and access to that storage all in the same 
function scope.

-Andy

>> On Oct 11, 2016, at 7:48 PM, Erik Eckstein via swift-dev 
>>  wrote:
>> 
>> This is a proposal for representing copy-on-write buffers in SIL. Actually 
>> it’s still a draft for a proposal. It also heavily depends on how we move 
>> forward with SIL ownership.
>> 
>> If you have any comments, please let me know.
>> 
>> Erik
>> 
>> 
>> ___
>> swift-dev mailing list
>> swift-dev@swift.org
>> https://lists.swift.org/mailman/listinfo/swift-dev
> 
> ___
> swift-dev mailing list
> swift-dev@swift.org
> https://lists.swift.org/mailman/listinfo/swift-dev

___
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev

Re: [swift-dev] copy-on-write proposal

[Erik Eckstein via swift-dev]

> On Oct 12, 2016, at 11:19 AM, Alexis  wrote:
> 
> I’m having trouble figuring something out: is all of this contingent on all 
> of the relevant operations being completely inlined into a single function at 
> the SIL level? Could failing to inline a standard library function lead to 
> performance cliffs? I understand this is generally true of inlining and 
> dead-code elimination; but I’m wondering how this affects the abstractions we 
> expose. Can we know that some things will “always” work, even if parts aren’t 
> inlined?

Yes, also these optimizations heavily rely on inlining. I would say that 
originally almost everything is inside a called function, just think of all the 
generated getters/setters. But usually this is not a problem because most of 
the relevant functions are quite small and always inlined anyway.


> 
>> On Oct 11, 2016, at 7:48 PM, Erik Eckstein via swift-dev 
>>  wrote:
>> 
>> This is a proposal for representing copy-on-write buffers in SIL. Actually 
>> it’s still a draft for a proposal. It also heavily depends on how we move 
>> forward with SIL ownership.
>> 
>> If you have any comments, please let me know.
>> 
>> Erik
>> 
>> 
>> ___
>> swift-dev mailing list
>> swift-dev@swift.org
>> https://lists.swift.org/mailman/listinfo/swift-dev
> 

___
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev

Re: [swift-dev] copy-on-write proposal

[Alexis via swift-dev]

I’m having trouble figuring something out: is all of this contingent on all of 
the relevant operations being completely inlined into a single function at the 
SIL level? Could failing to inline a standard library function lead to 
performance cliffs? I understand this is generally true of inlining and 
dead-code elimination; but I’m wondering how this affects the abstractions we 
expose. Can we know that some things will “always” work, even if parts aren’t 
inlined?

> On Oct 11, 2016, at 7:48 PM, Erik Eckstein via swift-dev 
>  wrote:
> 
> This is a proposal for representing copy-on-write buffers in SIL. Actually 
> it’s still a draft for a proposal. It also heavily depends on how we move 
> forward with SIL ownership.
> 
> If you have any comments, please let me know.
> 
> Erik
> 
> 
> ___
> swift-dev mailing list
> swift-dev@swift.org
> https://lists.swift.org/mailman/listinfo/swift-dev

___
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev

Re: [swift-dev] copy-on-write proposal

[Erik Eckstein via swift-dev]

Thanks for the feedback! Here is an updated version of the proposal: 
https://github.com/eeckstein/swift/blob/cow-proposal/docs/proposals/CopyOnWrite.rst
 

(you can look at the history to see the changes compared to the previous 
version)

> On Oct 11, 2016, at 7:57 PM, Michael Gottesman  wrote:
> 
>> 
>> 
>> :orphan:
>> 
>> .. highlight:: sil
>> 
>> ===
>> Copy-On-Write Representation in SIL
>> ===
>> 
>> .. contents::
>> 
>> Overview
>> 
>> 
>> This document proposes:
>> 
>> - An ownership attribute to define copy-on-write (COW) buffers in Swift data
>>  types.
>> 
>> - A representation of COW buffers in SIL so that optimizations can take 
>> benefit
>>  of it.
>> 
>> The basic idea is to enable the SIL optimizer to reason about COW data types
>> in the same way as a programmer can do.
> 
> in the same way as a programmer can do => just as a programmer can.
> 
>> 
>> 
>> This means: a COW buffer can only be modified by its owning SIL value, 
>> because
>> either it's uniquely referenced or the buffer is copied before modified.
> 
> modified => modification.
> 
>> 
>> .. note::
>>In the following the term "buffer" refers to a Swift heap object.
>>It can be any heap object, not necessarily a “buffer” with e.g. 
>> tail-allocated elements.
>> 
>> COW Types
>> =
>> 
>> The basic structure of COW data types can be simplified as follows::
>> 
>>class COWBuffer {
>>  var someData: Int
>>  ...
>>}
>> 
>>struct COWType {
>>  var b : COWBuffer
>> 
>>  mutating func change_it() {
>>if (!isUniquelyReferenced(b)) {
>>  b = copy_buffer(b)
>>}
>>b.someData = ...
>>  }
>>}
>> 
>> Currently the COW behavior of such types is just defined by their 
>> implementation.
>> But there is no representation of this special behavior in the SIL.
>> So the SIL optimizer has no clue about it and cannot take advantage of it.
>> 
>> For example::
>> 
>>func foo(arr : [Int]) {
>>  x = arr[0]
>>  opaque_function()
>>  y = arr[0] // can RLE replace this with y = x?
>>}
>> 
>> If opaque_function() wants to change the contents of the array buffer it 
>> first
>> has to copy it. But the optimizer does not know it so it has to 
>> conservatively
>> assume that opaque_function() will write to the location of arr[0].
>> 
>> Copy-on-write Ownership Attribute
>> =
>> 
>> This section proposes an ownership attribute to define a copy-on-write 
>> buffer.
>> 
>> Swift Syntax
>> 
>> 
>> A COW buffer reference can be defined with a new ownership attribute for the
>> buffer variable declaration (similar to “weak” and “unowned”)::
>> 
>>struct COWType {
>>  copy_on_write var b : COWBuffer
>> 
>>  // ...
>>}
>> 
>> The ``copy_on_write`` attribute is purely used for optimization purposes.
>> It does not change the semantics of the program.
>> 
>> .. note::
>> 
>>  “copy_on_write” is a  working title. TODO: decide on the name.
>>  Maybe it should be a @-attribute, like @copy_on_write?
>>  Another question is if we should open this attribute for the public or just
>>  use it internally in the library, because violating the implied rules
>>  (see below) could break memory safety.
>> 
>> Implementation
>> --
>> 
>> The ``copy_on_write`` references can be represented in the AST as a special
> 
> "The" is not needed here I think.
> 
>> ``StorageType``, just like how ``unowned`` and ``weak`` is represented.
> 
> is represented => are represented.
> 
>> The canonical type of a ``CopyOnWriteStorageType`` would be the referenced
>> buffer class type.
>> 
>> In SIL the buffer reference will have type::
>> 
>>$@sil_cow COWBuffer
>> 
>> where ``COWBuffer`` is the type of the referenced heap object.
>> 
>> Two conversion instructions are needed to convert from a ``@sil_cow`` 
>> reference
>> type to a regular reference type::
>> 
>>cow_to_ref
>>ref_to_cow
>> 
>> Again, this is similar to ``ref_to_unowned`` and ``unowned_to_ref``.
>> 
>> For example the SIL code for::
>> 
>>var c: COWType
>>let x = c.b.someData
>> 
>> would be::
>> 
>>%1 = struct_extract %1 : COWType, #COWType.b
>>%2 = cow_to_ref %1 : $@sil_cow COWBuffer
>>%3 = ref_element_addr %2 : $COWBuffer, #COWBuffer.someData
>>%4 = load %3 : $*Int
>> 
>> The ``ref_to_cow`` instruction is needed to store a new buffer reference 
>> into a
>> COW type.
>> 
>> COW Buffers and the Optimizer
>> =
>> 
>> A reference to a COW buffer gives the optimizer additional information:
>> 
>>  *A buffer, referenced by a @sil_cow reference is considered to be immutable
>>  during the lifetime of the reference.*
>> 
>> This means any address derived from a ``cow_to_ref`` instruction can be
>> considered to point to 

Re: [swift-dev] copy-on-write proposal

[Michael Gottesman via swift-dev]

> 
> 
> :orphan:
> 
> .. highlight:: sil
> 
> ===
> Copy-On-Write Representation in SIL
> ===
> 
> .. contents::
> 
> Overview
> 
> 
> This document proposes:
> 
> - An ownership attribute to define copy-on-write (COW) buffers in Swift data
>   types.
> 
> - A representation of COW buffers in SIL so that optimizations can take 
> benefit
>   of it.
> 
> The basic idea is to enable the SIL optimizer to reason about COW data types
> in the same way as a programmer can do.

in the same way as a programmer can do => just as a programmer can.

> 
> 
> This means: a COW buffer can only be modified by its owning SIL value, because
> either it's uniquely referenced or the buffer is copied before modified.

modified => modification.

> 
> .. note::
> In the following the term "buffer" refers to a Swift heap object.
> It can be any heap object, not necessarily a “buffer” with e.g. 
> tail-allocated elements.
> 
> COW Types
> =
> 
> The basic structure of COW data types can be simplified as follows::
> 
> class COWBuffer {
>   var someData: Int
>   ...
> }
> 
> struct COWType {
>   var b : COWBuffer
> 
>   mutating func change_it() {
> if (!isUniquelyReferenced(b)) {
>   b = copy_buffer(b)
> }
> b.someData = ...
>   }
> }
> 
> Currently the COW behavior of such types is just defined by their 
> implementation.
> But there is no representation of this special behavior in the SIL.
> So the SIL optimizer has no clue about it and cannot take advantage of it.
> 
> For example::
> 
> func foo(arr : [Int]) {
>   x = arr[0]
>   opaque_function()
>   y = arr[0] // can RLE replace this with y = x?
> }
> 
> If opaque_function() wants to change the contents of the array buffer it first
> has to copy it. But the optimizer does not know it so it has to conservatively
> assume that opaque_function() will write to the location of arr[0].
> 
> Copy-on-write Ownership Attribute
> =
> 
> This section proposes an ownership attribute to define a copy-on-write buffer.
> 
> Swift Syntax
> 
> 
> A COW buffer reference can be defined with a new ownership attribute for the
> buffer variable declaration (similar to “weak” and “unowned”)::
> 
> struct COWType {
>   copy_on_write var b : COWBuffer
> 
>   // ...
> }
> 
> The ``copy_on_write`` attribute is purely used for optimization purposes.
> It does not change the semantics of the program.
> 
> .. note::
> 
>   “copy_on_write” is a  working title. TODO: decide on the name.
>   Maybe it should be a @-attribute, like @copy_on_write?
>   Another question is if we should open this attribute for the public or just
>   use it internally in the library, because violating the implied rules
>   (see below) could break memory safety.
> 
> Implementation
> --
> 
> The ``copy_on_write`` references can be represented in the AST as a special

"The" is not needed here I think.

> ``StorageType``, just like how ``unowned`` and ``weak`` is represented.

is represented => are represented.

> The canonical type of a ``CopyOnWriteStorageType`` would be the referenced
> buffer class type.
> 
> In SIL the buffer reference will have type::
> 
> $@sil_cow COWBuffer
> 
> where ``COWBuffer`` is the type of the referenced heap object.
> 
> Two conversion instructions are needed to convert from a ``@sil_cow`` 
> reference
> type to a regular reference type::
> 
> cow_to_ref
> ref_to_cow
>  
> Again, this is similar to ``ref_to_unowned`` and ``unowned_to_ref``.
> 
> For example the SIL code for::
> 
> var c: COWType
> let x = c.b.someData
> 
> would be::
> 
> %1 = struct_extract %1 : COWType, #COWType.b
> %2 = cow_to_ref %1 : $@sil_cow COWBuffer
> %3 = ref_element_addr %2 : $COWBuffer, #COWBuffer.someData
> %4 = load %3 : $*Int
> 
> The ``ref_to_cow`` instruction is needed to store a new buffer reference into 
> a
> COW type.
> 
> COW Buffers and the Optimizer
> =
> 
> A reference to a COW buffer gives the optimizer additional information:
> 
>   *A buffer, referenced by a @sil_cow reference is considered to be immutable
>   during the lifetime of the reference.*
> 
> This means any address derived from a ``cow_to_ref`` instruction can be
> considered to point to immutable memory.
> 
> Some examples of optimizations which will benefit from copy-on-write
> representation in SIL:
> 
> - Redundant load elimination
> 
>   RLE can assume that opaque code does not modify a COW buffer.
>   Example::
> 
>   %2 = cow_to_ref %1 : $@sil_cow COWBuffer
>   %3 = ref_element_addr %2 : $COWBuffer, #someData
>   %4 = load %3 : $*Int
>   %5 = apply %foo()// Cannot overwrite memory 
> location %3
>   %6 = load %3 : $*Int // Can be replaced by %4
> 
>   Currently we 

[swift-dev] copy-on-write proposal

[Erik Eckstein via swift-dev]

This is a proposal for representing copy-on-write buffers in SIL. Actually it’s 
still a draft for a proposal. It also heavily depends on how we move forward 
with SIL ownership.


CopyOnWrite.rst
Description: Binary data

If you have any comments, please let me know.

Erik


___
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev