> On 22.12.2015, at 21:40, Michael Gottesman <[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. > 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
