[swift-users] problems with simple binary-trees program

[Michael Gottesman]

> On Dec 22, 2015, at 2:31 PM, Pascal Urban via swift-users <swift-users at swift.org> wrote:
> 
>> 
>> On 20.12.2015, at 19:54, Maurus Kühne via swift-users <swift-users at swift.org <mailto:swift-users at swift.org>> 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
>> swift-users at swift.org <mailto:swift-users at swift.org>
>> 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.

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 <swift-users at swift.org <mailto:swift-users at swift.org>> 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
> swift-users at swift.org <mailto:swift-users at swift.org>
> https://lists.swift.org/mailman/listinfo/swift-users <https://lists.swift.org/mailman/listinfo/swift-users>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-users/attachments/20151222/d127c655/attachment.html>