<div dir="ltr"><div>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:<br></div><div><br></div><div>1. The performance (currently discussed at length)</div><div>2. Readability (because we can use mutating methods on `inout` arguments).</div><div><br></div><div>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.</div><div><br></div><div>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?</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Jan 23, 2017 at 7:11 AM, Russ Bishop <span dir="ltr"><<a href="mailto:xenadu@gmail.com" target="_blank">xenadu@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><div><div class="h5"><br><div><blockquote type="cite"><div>On Jan 20, 2017, at 11:27 PM, Charles Srstka <<a href="mailto:cocoadev@charlessoft.com" target="_blank">cocoadev@charlessoft.com</a>> wrote:</div><br class="m_-6078723480564722793Apple-interchange-newline"><div><div style="word-wrap:break-word"><blockquote type="cite">On Jan 21, 2017, at 12:37 AM, Russ Bishop <<a href="mailto:xenadu@gmail.com" target="_blank">xenadu@gmail.com</a>> wrote:<br></blockquote><div><blockquote type="cite"><br class="m_-6078723480564722793Apple-interchange-newline"><div><div style="word-wrap:break-word"><div><blockquote type="cite" style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><div>On Jan 16, 2017, at 9:43 AM, Charles Srstka via swift-evolution <<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>> wrote:</div></blockquote></div><div><blockquote type="cite"><b>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.</b></blockquote><br></div><div>That’s all the endorsement I need. +1 from me.</div><div><br></div><div><br></div><div>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()).</div></div></div></blockquote></div><br><div>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.</div><div><br></div><div>Charles</div></div></div></blockquote></div><div><br></div></div></div><div><br><div>I was thinking of an optimization like this:</div><div><br></div><div>1. The closure or function doesn’t capture anything (and thus by definition nothing can escape the closure)</div><div>2. ???</div><div>3. Therefore input returns true for isUniquelyReferenced and no copying of the underlying storage is required (Profit!)</div><div><br></div><div><br></div><div>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.</div><div><br></div><div>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:</div><div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><div style="margin:0px;line-height:normal"><span style="font-variant-ligatures:no-common-ligatures;color:#ba2da2">func</span><span style="font-variant-ligatures:no-common-ligatures"> doSomething(</span><span style="font-variant-ligatures:no-common-ligatures;color:#ba2da2">_</span><span style="font-variant-ligatures:no-common-ligatures"> x: </span><span style="font-variant-ligatures:no-common-ligatures;color:#4f8187">MyStruct</span><span style="font-variant-ligatures:no-common-ligatures">) -> </span><span style="font-variant-ligatures:no-common-ligatures;color:#4f8187">MyStruct</span><span style="font-variant-ligatures:no-common-ligatures"> {</span></div><div style="margin:0px;line-height:normal"><span style="font-variant-ligatures:no-common-ligatures"> </span><span style="font-variant-ligatures:no-common-ligatures;color:#ba2da2">var</span><span style="font-variant-ligatures:no-common-ligatures"> mutX = x</span></div><div style="margin:0px;line-height:normal;color:rgb(62,30,129)"><span style="font-variant-ligatures:no-common-ligatures;color:#000000"> </span><span style="font-variant-ligatures:no-common-ligatures;color:#ba2da2">let</span><span style="font-variant-ligatures:no-common-ligatures;color:#000000"> isUnique = </span><span style="font-variant-ligatures:no-common-ligatures">isKnownUniquelyReferenced</span><span style="font-variant-ligatures:no-common-ligatures;color:#000000">(&<wbr>mutX.</span><span style="font-variant-ligatures:no-common-ligatures;color:#4f8187">refTypeInstance</span><span style="font-variant-ligatures:no-common-ligatures;color:#000000">)</span></div><div style="margin:0px;line-height:normal"><span style="font-variant-ligatures:no-common-ligatures"> </span><span style="font-variant-ligatures:no-common-ligatures;color:#3e1e81">print</span><span style="font-variant-ligatures:no-common-ligatures">(</span><span style="font-variant-ligatures:no-common-ligatures;color:#d12f1b">"isUnique = </span><span style="font-variant-ligatures:no-common-ligatures">\</span><span style="font-variant-ligatures:no-common-ligatures;color:#d12f1b">(</span><span style="font-variant-ligatures:no-common-ligatures">isUnique</span><span style="font-variant-ligatures:no-common-ligatures;color:#d12f1b">)"</span><span style="font-variant-ligatures:no-common-ligatures">) </span><span style="font-variant-ligatures:no-common-ligatures;color:#008400">//prints false</span></div><div style="margin:0px;line-height:normal"><span style="font-variant-ligatures:no-common-ligatures"> </span><span style="font-variant-ligatures:no-common-ligatures;color:#ba2da2">return</span><span style="font-variant-ligatures:no-common-ligatures"> mutX</span></div><div style="margin:0px;line-height:normal"><span style="font-variant-ligatures:no-common-ligatures">}</span></div><div style="margin:0px;line-height:normal;color:rgb(49,89,93)"><span style="font-variant-ligatures:no-common-ligatures">doSomething</span><span style="font-variant-ligatures:no-common-ligatures;color:#000000">(</span><span style="font-variant-ligatures:no-common-ligatures;color:#4f8187">MyStruct</span><span style="font-variant-ligatures:no-common-ligatures;color:#000000">())</span></div></div></div><div><br></div><div><br></div><div>The fact that storage is uniquely owned is trivially provable to a human but not to the compiler. Why? </div><div><br></div><div><br></div><div>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.</div><span class="HOEnZb"><font color="#888888"><div><br></div><div>Russ</div></font></span></div></div></blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature" data-smartmail="gmail_signature">Chris Eidhof</div>
</div>