[swift-evolution] Improved value and move semantics

[Dave Abrahams]

on Sun Jul 31 2016, Bram Beernink <swift-evolution at swift.org> wrote:

> Hi Karl and Haravikk,
>
> Thank you for your replies. 
>
> I was assuming that the cases I represented are not always optimized for several reasons:
> Swift’s book only talks about optimization in the context of arrays,
> strings and dictionaries. Not in the context of structs in general:
> “The description above refers to the “copying” of strings, arrays, and
> dictionaries. The behavior you see in your code will always be as if a
> copy took place. However, Swift only performs an actual copy behind
> the scenes when it is absolutely necessary to do so. Swift manages all
> value copying to ensure optimal performance, 

If it says that, it's... not quite right.  There are things we could do
to make some value copies more optimal.  For example, any value type
containing multiple class references—or multiple other value types (such
as arrays or strings or dictionaries) that contain class references—will
cost more to copy than a single class reference does.  At the cost of
some allocation and indirection, we could reduce the copying cost of
such values.  It's an optimization we've considered making, but haven't
prioritized.  

You can put a CoW wrapper around your value to do it manually.  I hacked
one up using ManagedBuffer for someone at WWDC but I don't seem to have
saved the code, sadly.

> and you should not avoid assignment to try to preempt this
> optimization.”  

But that's basically still true.  The CoW wrapper technique is a good
way to tune things later if you find it necessary, without distorting
your code.

> Excerpt From: Apple Inc. “The Swift Programming Language (Swift 2.2).”
> iBooks. https://itun.es/nl/jEUH0.l <https://itun.es/nl/jEUH0.l> In
> https://github.com/apple/swift/tree/eb27bb65a7c17bd9b4255baee5c4e4f9c214bde6/stdlib/public/core
> <https://github.com/apple/swift/tree/eb27bb65a7c17bd9b4255baee5c4e4f9c214bde6/stdlib/public/core>
> I see public mutating func append(_ newElement: Element) , line 1268,
> using _makeUniqueAndReserveCapacityIfNotUnique() at line 1269, leading
> me to suspect that to have COW, you have to do additional work.  Doing
> some manual tests some time ago, isUniquelyReferenced seemed to return
> false in a case like append_one as
> https://github.com/apple/swift/blob/master/docs/OptimizationTips.rst#advice-use-inplace-mutation-instead-of-object-reassignment
> <https://github.com/apple/swift/blob/master/docs/OptimizationTips.rst#advice-use-inplace-mutation-instead-of-object-reassignment>
> mentioned by Karl, meaning that it indeed leads to unnecessary
> copying.
>
> In any case,
> https://github.com/apple/swift/blob/master/docs/OptimizationTips.rst#advice-use-inplace-mutation-instead-of-object-reassignment
> <https://github.com/apple/swift/blob/master/docs/OptimizationTips.rst#advice-use-inplace-mutation-instead-of-object-reassignment>
> does mention that: “Sometimes COW can introduce additional unexpected
> copies if the user is not careful.” I would argue that what we need is
> not only COW, but Copy On Write When Necessary, COWWN. In COWWN copies
> are only made when writing to the shared reference if it is not unique
> and the shared reference’s old state is still referred to in next
> statements. 

That's what the standard library CoW types do currently, and yours can
too.  See isKnownUniquelyReferenced (née isUniquelyReferenced).

> So not only is the current reference count taken into account, but
> also whether the old state is needed afterwards. This is both runtime
> as well as compile-time data.
>
> So my questions would be:
> Why does Swift sometimes do additional unnecessary copying, as implied
> by
> https://github.com/apple/swift/blob/master/docs/OptimizationTips.rst#advice-use-inplace-mutation-instead-of-object-reassignment
> <https://github.com/apple/swift/blob/master/docs/OptimizationTips.rst#advice-use-inplace-mutation-instead-of-object-reassignment>
> in the case of append_one? 

In this case it could be needlessly copied because the optimizer is either 

a) off (-Onone)
b) not smart enough to know that `a` isn't used before being reassigned

> Is this a problem that cannot be solved?

I think this particular example can be solved.  There are other cases
where avoiding a needless copy is impossible due to the existence of a
separate compilation boundary (e.g. across frameworks, or files if
whole-module-optimization is disabled).

> (In C++ you would solve this example using
> a=a.append_one(std::move(a)). But I would think that since Swift does
> not have to deal with pointers and manual memory management, it can
> automatically detect such cases unlike C++?)  

In principle, yes.  In practice, it depends on visibility through
function call boundaries.

> If/once structs are COWWN, can Swift introduce immutable functions for
> the standard library, such as func appended(_ newElement: Element) ->
> Array<Element>?

That would be “appending.”  We could introduce that method today, though
I'm not sure it's useful enough to justify its existence.

>
> Best regards,
> Bram.
>
>> On 30 jul. 2016, at 12:46, Haravikk <swift-evolution at haravikk.me> wrote:
>> 
>>> On 29 Jul 2016, at 17:42, Bram Beernink via swift-evolution
>>> <swift-evolution at swift.org
>>> <mailto:swift-evolution at swift.org>>
>>> wrote:
>>> 
>>> Hi all,
>>> 
>>> Would it be possible to improve value and move semantics
>>> (performance) in Swift? Consider this possible Swift code in a
>>> future release of Swift:
>>> 
>>> let array1 : [String] = ["Val1", "Val2"]
>>> let array2 = array1.appended(“Val3”) // Copy of array1 with “Val3”
>>> appended. array1 is left untouched. Nothing special yet.
>>> var array3 : [String] = [“Var1”]
>>> array3 = array3.appended(“Var2”) // array3 can just be mutated to
>>> add “Var2”, while maintaining value semantics. Swift can recognize
>>> that array3’s old state is not referenced anywhere in the future.
>>> let array4 = array2.appended("Val4").appended("Val5") // Copy of
>>> array2 with both "Val4" and "Val5" appended. In this case, “Val5”
>>> can also be appended by mutation.
>> 
>> Well, for the array3 = array3.appended("Var2") example this could
>> possibly be addressed by an attribute to indicate to the compiler
>> that .appended() has a mutating variant, as this will allow it to
>> issue a warning when the assignment is to the same variable, which
>> would address that simple case (and provide more awareness of the
>> mutating options and encourage developers to use them).
>> 
>>> This example illustrates improved value semantics with a string array. But it would be good if this can work with any struct. Maybe via something similar to isUniquelyReferenced? Or maybe you can even have a “smart” self in a non-mutating func in a struct:
>>> struct Array<T> {
>>>     func appended(e : T) -> Array<T> { // No mutating keyword!
>>>         self.append(e) // self would either be mutated here if the current ref count of self is 1, and self is either a “rvalue” or self’s old state cannot possibly referenced anymore after this call. Otherwise, "self” would actually be a copy of self.
>>>         return self
>>>     }
>>> }
>> 
>> I don't know about allowing mutation of self in non-mutating
>> methods, that seems confusing; however, I'd be surprised if the
>> compiler doesn't already detect variables that only exist to create
>> a copy that is discarded.
>> 
>> The compiler should already be trying to inline very simple methods
>> like the common copy -> mutate -> return style of non-mutating
>> implementations, in which case it should be able to identify that a
>> copy is being created only to overwrite the original anyway, so can
>> be eliminated. Do you believe that this isn't currently being done?
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>

-- 
-Dave