<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Dec 22, 2015, at 2:31 PM, Pascal Urban via swift-users <<a href="mailto:swift-users@swift.org" class="">swift-users@swift.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><blockquote type="cite" class=""><div class=""><br class="Apple-interchange-newline">On 20.12.2015, at 19:54, Maurus Kühne via swift-users <<a href="mailto:swift-users@swift.org" class="">swift-users@swift.org</a>> wrote:</div><div class=""><div class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><br class=""></div></div></blockquote>…<br class=""><blockquote type="cite" class=""><div class=""><div class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><div class="">I was able to speed up David’s solution by almost 50% by changing the method checkTree from this:</div><div class=""><br class=""></div><div class=""><span class="" style="font-family: Menlo; font-size: 11px; color: rgb(187, 44, 162);">func</span><span class="" style="font-family: Menlo; font-size: 11px;"><span class="Apple-converted-space"> </span>checkTree(</span><span class="" style="font-family: Menlo; font-size: 11px;">t:<span class="Apple-converted-space"> </span></span><span class="" style="font-family: Menlo; font-size: 11px; color: rgb(112, 61, 170);">Array</span><span class="" style="font-family: Menlo; font-size: 11px;"><</span><span class="" style="font-family: Menlo; font-size: 11px; color: rgb(79, 129, 135);">TreeNodeItem</span><span class="" style="font-family: Menlo; font-size: 11px;">>,<span class="Apple-converted-space"> </span></span><span class="" style="font-family: Menlo; font-size: 11px; color: rgb(187, 44, 162);">_</span><span class="" style="font-family: Menlo; font-size: 11px;"><span class="Apple-converted-space"> </span>i:<span class="Apple-converted-space"> </span></span><span class="" style="font-family: Menlo; font-size: 11px; color: rgb(112, 61, 170);">Int</span><span class="" style="font-family: Menlo; font-size: 11px;">) -><span class="Apple-converted-space"> </span></span><span class="" style="font-family: Menlo; font-size: 11px; color: rgb(112, 61, 170);">Int</span></div><div class=""><span class="" style="font-family: Menlo; font-size: 11px; color: rgb(112, 61, 170);"><br class=""></span></div><div class="">to this:</div><div class=""><span class="" style="font-family: Menlo; font-size: 11px; color: rgb(187, 44, 162);"><br class=""></span></div><div class=""><span class="" style="font-family: Menlo; font-size: 11px; color: rgb(187, 44, 162);">func</span><span class="" style="font-family: Menlo; font-size: 11px;"> checkTree(</span><span class="" style="color: rgb(187, 44, 162); font-family: Menlo; font-size: 11px;">inout </span><span class="" style="font-family: Menlo; font-size: 11px;">t: </span><span class="" style="font-family: Menlo; font-size: 11px; color: rgb(112, 61, 170);">Array</span><span class="" style="font-family: Menlo; font-size: 11px;"><</span><span class="" style="font-family: Menlo; font-size: 11px; color: rgb(79, 129, 135);">TreeNodeItem</span><span class="" style="font-family: Menlo; font-size: 11px;">>, </span><span class="" style="font-family: Menlo; font-size: 11px; color: rgb(187, 44, 162);">_</span><span class="" style="font-family: Menlo; font-size: 11px;"> i: </span><span class="" style="font-family: Menlo; font-size: 11px; color: rgb(112, 61, 170);">Int</span><span class="" style="font-family: Menlo; font-size: 11px;">) -> </span><span class="" style="font-family: Menlo; font-size: 11px; color: rgb(112, 61, 170);">Int</span></div><div class=""><span class="" style="font-family: Menlo; font-size: 11px; color: rgb(112, 61, 170);"><br class=""></span></div><div class="">It completes in about ~10s instead of ~20s on my 2.66GHz i5 iMac for n=20. </div><div class="">This also works together with Pascal’s libdispatch solution. In this case it completes in ~5s.</div><div class="">Here is the modified version: <a href="https://gist.github.com/mauruskuehne/633789417c2357a6bb93" class="">https://gist.github.com/mauruskuehne/633789417c2357a6bb93</a></div><div class=""><br class=""></div><div class="">Could somebody explain to me why this is the case? I know what the inout keyword does, but I don’t understand why it makes the code faster in this case?</div><div class=""><br class=""></div><div class="">Maurus</div><img src="https://u2002410.ct.sendgrid.net/wf/open?upn=BTgI15RKzKXMjyS0Xbr6HqrvK8u2RqOrKOjNlXDGm1pWVozrmlMBrsqK3B-2BdMzYRR4FOvg0aK8SoalHo1Y7Kl0Kzl2dr6N1CW97SgsheCvqRkTsukBECLCc1etPjtEirnt5KPhnsstmlXhhhjSs7MB2L4pRqmh2NThfJ-2BWlRSP36uN4IhWuP2oR-2FLEOVMEsUC5YYJmOD4h8fPcfJfhSZNA-3D-3D" alt="" width="1" height="1" border="0" class="" style="height: 1px !important; width: 1px !important; border-width: 0px !important; margin: 0px !important; padding: 0px !important;"></div>_______________________________________________<br class="">swift-users mailing list<br class=""><a href="mailto:swift-users@swift.org" class="">swift-users@swift.org</a><br class=""><a href="https://lists.swift.org/mailman/listinfo/swift-users" class="">https://lists.swift.org/mailman/listinfo/swift-users</a><br class=""></div></blockquote></div><br class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div class=""><br class=""></div><div class="">Like Janosch said: ARC overhead</div><div class=""><br class=""></div><div class="">So here is whats happening:</div><div class="">A function reference parameter gets retained before calling the function and then released within the called function (generally), so the function is taking ownership of the parameter. [1]</div><div class="">If a parameter is marked with the inout keyword the function does not take ownership of the reference parameter, so no retains and releases. [2]</div><div class=""><br class=""></div><div class="">Given how often checkTree is called the retains and releases of the array get quiet expensive.</div><div class="">You can see this quiet nicely while profiling these functions in Instruments using the time profiler.</div><div class=""><br class=""></div><div class="">I think normally this shouldn't be a problem, but because of the recursion the compiler is not able to optimize the retain and release calls.</div></div></div></blockquote><div><br class=""></div><div>This is not true. We can hit this case. It requires further work in the ARC optimizer. We some time ago actually did have the functionality to hit this case, but I had to disable it b/c of some correctness issues.</div><div><br class=""></div><div>File a bug with this test case and assign to me.</div><div><br class=""></div><div>Michael</div><br class=""><blockquote type="cite" class=""><div class=""><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div class=""><br class=""></div><div class="">Another solution could be some kind of wrapper struct/class which has the array as a property and checkTree as a method.</div><div class="">This way checkTree would only access the property and additional retains/releases would not be necessary.</div><div class=""><br class=""></div><div class=""><div class="">[1]<span class="Apple-converted-space"> </span><a href="https://github.com/apple/swift/blob/master/docs/SIL.rst#reference-counts" class="">https://github.com/apple/swift/blob/master/docs/SIL.rst#reference-counts</a></div><div class="">[2]<span class="Apple-converted-space"> </span><a href="https://github.com/apple/swift/blob/master/docs/SIL.rst#inout-arguments" class="">https://github.com/apple/swift/blob/master/docs/SIL.rst#inout-arguments</a></div></div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><div class=""></div><blockquote type="cite" class=""><div class="">On 20.12.2015, at 17:12, Janosch Hildebrand via swift-users <<a href="mailto:swift-users@swift.org" class="">swift-users@swift.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><span class="" style="float: none; display: inline !important;">Basically just rewrite a C example in Swift; not pretty but it should also perform very much like C then.</span></div></blockquote></div><div class=""><span class="" style="float: none; display: inline !important;"><br class=""></span></div><div class="">Someone has done this and is now in second place:</div><div class=""><a href="http://benchmarksgame.alioth.debian.org/u64q/program.php?test=binarytrees&lang=swift&id=5" class="">http://benchmarksgame.alioth.debian.org/u64q/program.php?test=binarytrees&lang=swift&id=5</a></div><div class=""><br class=""></div><div class=""><br class=""></div></div><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><br class=""></div><img src="https://u2002410.ct.sendgrid.net/wf/open?upn=BsPB5S3Z2usbY-2FzcCsd-2F2r4MihYe9FiKHjzH65yItK4RflEXy-2BFTtPTMeBu2z3v6cQjibR7ey1NPmmRgFmuMPIRfA0zixhUjUf4FynjHh-2BF0jlyT87unVVlu20f5Y-2FIOv6-2F2RVFkI-2FxW-2FAZkHtCbXbryKfQIXeN5sPPXTiOaLMtnSms6OM1OsRL81lqanyb4rvrNwLHvBkGSoWpqnLBYKuKn1esLJTDoT-2B3W2SdSq7M-3D" alt="" width="1" height="1" border="0" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; height: 1px !important; width: 1px !important; border-width: 0px !important; margin: 0px !important; padding: 0px !important;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class=""><span class="Apple-converted-space"> </span></span><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">_______________________________________________</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">swift-users mailing list</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><a href="mailto:swift-users@swift.org" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">swift-users@swift.org</a><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><a href="https://lists.swift.org/mailman/listinfo/swift-users" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">https://lists.swift.org/mailman/listinfo/swift-users</a></div></blockquote></div><br class=""></body></html>