> On Dec 23, 2015, at 11:32 AM, Pascal Urban <[email protected]> wrote: > >> >> On 22.12.2015, at 21:40, Michael Gottesman <[email protected] >> <mailto:[email protected]>> wrote: >> >> >>> On Dec 22, 2015, at 2:31 PM, Pascal Urban via swift-users >>> <[email protected] <mailto:[email protected]>> wrote: >>> >>>> >>>> On 20.12.2015, at 19:54, Maurus Kühne via swift-users >>>> <[email protected] <mailto:[email protected]>> wrote: >>>> >>> … >>>> I was able to speed up David’s solution by almost 50% by changing the >>>> method checkTree from this: >>>> >>>> func checkTree(t: Array<TreeNodeItem>, _ i: Int) -> Int >>>> >>>> to this: >>>> >>>> func checkTree(inout t: Array<TreeNodeItem>, _ i: Int) -> Int >>>> >>>> It completes in about ~10s instead of ~20s on my 2.66GHz i5 iMac for n=20. >>>> This also works together with Pascal’s libdispatch solution. In this case >>>> it completes in ~5s. >>>> Here is the modified version: >>>> https://gist.github.com/mauruskuehne/633789417c2357a6bb93 >>>> <https://gist.github.com/mauruskuehne/633789417c2357a6bb93> >>>> >>>> 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? >>>> >>>> Maurus >>>> >>>> _______________________________________________ >>>> swift-users mailing list >>>> [email protected] <mailto:[email protected]> >>>> https://lists.swift.org/mailman/listinfo/swift-users >>>> <https://lists.swift.org/mailman/listinfo/swift-users> >>> >>> >>> Like Janosch said: ARC overhead >>> >>> So here is whats happening: >>> 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] >>> 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] >>> >>> Given how often checkTree is called the retains and releases of the array >>> get quiet expensive. >>> You can see this quiet nicely while profiling these functions in >>> Instruments using the time profiler. >>> >>> 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. >> >> 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. >> >> File a bug with this test case and assign to me. > > Nice. I figured that this would be optimized in the future. > Filed as SR-356 with a simplified test case. >
Thanks! Michael >> Michael >> >>> >>> Another solution could be some kind of wrapper struct/class which has the >>> array as a property and checkTree as a method. >>> This way checkTree would only access the property and additional >>> retains/releases would not be necessary. >>> >>> [1] >>> https://github.com/apple/swift/blob/master/docs/SIL.rst#reference-counts >>> <https://github.com/apple/swift/blob/master/docs/SIL.rst#reference-counts> >>> [2] https://github.com/apple/swift/blob/master/docs/SIL.rst#inout-arguments >>> <https://github.com/apple/swift/blob/master/docs/SIL.rst#inout-arguments> >>> >>> >>>> On 20.12.2015, at 17:12, Janosch Hildebrand via swift-users >>>> <[email protected] <mailto:[email protected]>> wrote: >>>> >>>> Basically just rewrite a C example in Swift; not pretty but it should also >>>> perform very much like C then. >>> >>> >>> Someone has done this and is now in second place: >>> http://benchmarksgame.alioth.debian.org/u64q/program.php?test=binarytrees&lang=swift&id=5 >>> >>> <http://benchmarksgame.alioth.debian.org/u64q/program.php?test=binarytrees&lang=swift&id=5> >>> >>> >>> >>> _______________________________________________ >>> swift-users mailing list >>> [email protected] <mailto:[email protected]> >>> https://lists.swift.org/mailman/listinfo/swift-users >>> <https://lists.swift.org/mailman/listinfo/swift-users>
_______________________________________________ swift-users mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-users
