<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 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 style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""></div></div></blockquote>…<br class=""><blockquote type="cite" class=""><div class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><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 style="font-family: Menlo; font-size: 11px; color: rgb(187, 44, 162);" class="">func</span><span style="font-family: Menlo; font-size: 11px;" class=""> checkTree(</span><span style="font-family: Menlo; font-size: 11px;" class="">t: </span><span style="font-family: Menlo; font-size: 11px; color: rgb(112, 61, 170);" class="">Array</span><span style="font-family: Menlo; font-size: 11px;" class=""><</span><span style="font-family: Menlo; font-size: 11px; color: rgb(79, 129, 135);" class="">TreeNodeItem</span><span style="font-family: Menlo; font-size: 11px;" class="">>, </span><span style="font-family: Menlo; font-size: 11px; color: rgb(187, 44, 162);" class="">_</span><span style="font-family: Menlo; font-size: 11px;" class=""> i: </span><span style="font-family: Menlo; font-size: 11px; color: rgb(112, 61, 170);" class="">Int</span><span style="font-family: Menlo; font-size: 11px;" class="">) -> </span><span style="font-family: Menlo; font-size: 11px; color: rgb(112, 61, 170);" class="">Int</span></div><div class=""><span style="font-family: Menlo; font-size: 11px; color: rgb(112, 61, 170);" class=""><br class=""></span></div><div class="">to this:</div><div class=""><span style="font-family: Menlo; font-size: 11px; color: rgb(187, 44, 162);" class=""><br class=""></span></div><div class=""><span style="font-family: Menlo; font-size: 11px; color: rgb(187, 44, 162);" class="">func</span><span style="font-family: Menlo; font-size: 11px;" class=""> checkTree(</span><span style="color: rgb(187, 44, 162); font-family: Menlo; font-size: 11px;" class="">inout </span><span style="font-family: Menlo; font-size: 11px;" class="">t: </span><span style="font-family: Menlo; font-size: 11px; color: rgb(112, 61, 170);" class="">Array</span><span style="font-family: Menlo; font-size: 11px;" class=""><</span><span style="font-family: Menlo; font-size: 11px; color: rgb(79, 129, 135);" class="">TreeNodeItem</span><span style="font-family: Menlo; font-size: 11px;" class="">>, </span><span style="font-family: Menlo; font-size: 11px; color: rgb(187, 44, 162);" class="">_</span><span style="font-family: Menlo; font-size: 11px;" class=""> i: </span><span style="font-family: Menlo; font-size: 11px; color: rgb(112, 61, 170);" class="">Int</span><span style="font-family: Menlo; font-size: 11px;" class="">) -> </span><span style="font-family: Menlo; font-size: 11px; color: rgb(112, 61, 170);" class="">Int</span></div><div class=""><span style="font-family: Menlo; font-size: 11px; color: rgb(112, 61, 170);" class=""><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" style="height:1px !important;width:1px !important;border-width:0 !important;margin-top:0 !important;margin-bottom:0 !important;margin-right:0 !important;margin-left:0 !important;padding-top:0 !important;padding-bottom:0 !important;padding-right:0 !important;padding-left:0 !important;" class="">
</div>
_______________________________________________<br class="">swift-users mailing list<br class=""><a href="mailto:swift-users@swift.org" class="">swift-users@swift.org</a><br class="">https://lists.swift.org/mailman/listinfo/swift-users<br class=""></div></blockquote></div><br class=""><div class=""><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 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] <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] <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=""><br class=""></div></body></html>