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

Pascal Urban mail at pscl.de
Tue Dec 22 14:31:42 CST 2015

> On 20.12.2015, at 19:54, Maurus Kühne via swift-users <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
> 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.

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
[2] 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> 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:

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-users/attachments/20151222/ed167030/attachment.html>

More information about the swift-users mailing list