[swift-evolution] Reduce with inout

[Chris Eidhof]

Not as a direct reply to Russ, but just to reiterate: to me, there are two
clear benefits of using the `inout` version of reduce:

1. The performance (currently discussed at length)
2. Readability (because we can use mutating methods on `inout` arguments).

Even if the compiler were to optimize the unnecessary copy of `return arr +
[el]` away, there are still a lot of other mutable methods that you might
want to use within the reduce closure. So I think the proposal is still
very valid even if the compiler optimizations would magically appear
tomorrow.

To push this proposal forward a little bit, I'd like to come up with a good
name. It seems like we shouldn't overload `reduce`, but choose a different
name, so that we don't stress the typechecker. Any other suggestions?

On Mon, Jan 23, 2017 at 7:11 AM, Russ Bishop <xenadu at gmail.com> wrote:

>
> On Jan 20, 2017, at 11:27 PM, Charles Srstka <cocoadev at charlessoft.com>
> wrote:
>
> On Jan 21, 2017, at 12:37 AM, Russ Bishop <xenadu at gmail.com> wrote:
>
>
> On Jan 16, 2017, at 9:43 AM, Charles Srstka via swift-evolution <
> swift-evolution at swift.org> wrote:
>
> *I don’t even know how long it actually takes to finish this test, because
> the last time I did this I eventually got sick of waiting and killed the
> process. So, I don’t know quite how many orders of magnitude slower it is,
> but it’s a lot.*
>
>
> That’s all the endorsement I need. +1 from me.
>
>
> I do wonder if there is any way to get this sort of optimization out of
> the compiler. I suppose it would be difficult because the compiler doesn’t
> know what the mutable vs immutable pairs are or if such a pair even exists
> (array doesn’t have appending()).
>
>
> The (somewhat naïve) assumption that some optimization of this sort might
> be going on is what led me to do the speed test in the first place.
> However, when you think about it, it’d be really quite hard to do. A reduce
> that builds an array consists of the closure that adds something to an
> array, and the reduce function itself. With the code to both of these, it’s
> not inconceivable that the compiler could figure out what you’re doing, but
> unfortunately the two components live in different modules / compilation
> units. The closure doesn’t know that its return value is just going to be
> replacing the passed-in value, and the reduce function doesn’t know that
> the closure isn’t going to store the original array somewhere, so neither
> can really know that it’s safe to modify the array in place.
>
> Charles
>
>
>
> I was thinking of an optimization like this:
>
> 1. The closure or function doesn’t capture anything (and thus by
> definition nothing can escape the closure)
> 2. ???
> 3. Therefore input returns true for isUniquelyReferenced and no copying of
> the underlying storage is required (Profit!)
>
>
> The problem is obviously in step 2. We don’t have any way to express the
> necessary contract other than inout, which requires a separate definition.
> If it worked like throws/rethrows where a non-mutating closure promoted to
> an inout closure then we could just change the definition of reduce (though
> you’d still have to return the value). The compiler would need to
> understand that ownership of the underlying array storage moves from the
> input parameter to the constructed array inside the closure (and ultimately
> the return value). That’s a bit of a tall order.
>
> That leads me to think about why inout is required (because
> isKnownUniquelyReferenced returns false otherwise). Why can’t the compiler
> determine that the intermediate array is unique? Take this program:
> func doSomething(_ x: MyStruct) -> MyStruct {
>     var mutX = x
>     let isUnique = isKnownUniquelyReferenced(&mutX.refTypeInstance)
>     print("isUnique = \(isUnique)") //prints false
>     return mutX
> }
> doSomething(MyStruct())
>
>
> The fact that storage is uniquely owned is trivially provable to a human
> but not to the compiler. Why?
>
>
> These are just idle musings. My suspicion is you need ownership
> annotations (aka borrow checker) to make this tractable but I don’t have
> any proof of that.
>
> Russ
>



-- 
Chris Eidhof
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170123/83425ef5/attachment.html>