# ARC, tail recursion

**URL:** <https://forums.swift.org/t/arc-tail-recursion/57054>\
**Category:** Using Swift\
**Tags:** performance, arc\
**Created:** [April 29, 2022, 5:21pm UTC](https://forums.swift.org/t/arc-tail-recursion/57054 "2022-04-29T17:21:30Z")\
**Posts on this page:** 14\
**Page:** 1

<div class="post-metadata">

**Author:** ![RonAvitzur](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ronavitzur/32/13927_2.png) [@RonAvitzur](https://forums.swift.org/u/RonAvitzur)\
**Post date:** [April 29, 2022, 5:21pm UTC](https://forums.swift.org/t/arc-tail-recursion/57054/1 "2022-04-29T17:21:30Z")

</div>

While looking at a stack overflow crash, it looks like

`var leftMost: Expr { count == 0 ? self : args[0].leftMost }`

is not benefiting from tail call optimization.

```swift
final class Expr : Sequence, Equatable, Hashable {
    unowned(unsafe) var parent: Expr? = nil
    var op: OpCode
    var args: ContiguousArray<Expr> 
...
}

```

Is the retain/release inhibiting tail-call optimization?

```swift
Graphing Calculator`Expr.leftMost.getter:
    0x102eb6900 <+0>: stp x20, x19, [sp, #-0x20]!
    0x102eb6904 <+4>: stp x29, x30, [sp, #0x10]
    0x102eb6908 <+8>: add x29, sp, #0x10
-> 0x102eb690c <+12>: ldr x8, [x20, #0x38]
    0x102eb6910 <+16>: ldr x9, [x8, #0x10]
    0x102eb6914 <+20>: cbz x9, 0x102eb6944 ; <+68> at Expr.swift:218:40
    0x102eb6918 <+24>: ldr x20, [x8, #0x20]
    0x102eb691c <+28>: mov x0, x20
    0x102eb6920 <+32>: bl 0x1033a9688 ; symbol stub for: swift_retain
    0x102eb6924 <+36>: bl 0x102eb6900 ; <+0> at Expr.swift:218
    0x102eb6928 <+40>: mov x19, x0
    0x102eb692c <+44>: mov x0, x20
    0x102eb6930 <+48>: bl 0x1033a9670 ; symbol stub for: swift_release
    0x102eb6934 <+52>: mov x0, x19
    0x102eb6938 <+56>: ldp x29, x30, [sp, #0x10]
    0x102eb693c <+60>: ldp x20, x19, [sp], #0x20
    0x102eb6940 <+64>: ret    
    0x102eb6944 <+68>: mov x0, x20
    0x102eb6948 <+72>: ldp x29, x30, [sp, #0x10]
    0x102eb694c <+76>: ldp x20, x19, [sp], #0x20
    0x102eb6950 <+80>: b 0x1033a9688 ; symbol stub for: swift_retain

```

It is straightforward to avoid the recursion manually with

```swift
    var leftMost: Expr {
        var expr = self
        while expr.count > 0 { expr = expr.args[0] }
        return expr
    }

```

but is there any way to avoid the retain/release while stepping down the child nodes?

---

<div class="post-metadata">

**Author:** ![tera](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/tera/32/38201_2.png) [@tera](https://forums.swift.org/u/tera)\
**Post date:** [April 29, 2022, 9:22pm UTC](https://forums.swift.org/t/arc-tail-recursion/57054/2 "2022-04-29T21:22:31Z")

</div>

Try `unowned var expr = self`

What's the max child count in a node (if any)?

---

<div class="post-metadata">

**Author:** ![RonAvitzur](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ronavitzur/32/13927_2.png) [@RonAvitzur](https://forums.swift.org/u/RonAvitzur)\
**Post date:** [April 29, 2022, 9:49pm UTC](https://forums.swift.org/t/arc-tail-recursion/57054/3 "2022-04-29T21:49:11Z")

</div>

> [@tera](#):
>
> What's the max child count in a node (if any)?

No maximum. In practice, the number is typically very small.

> [@tera](#):
>
> Try `unowned var expr = self`

This particular function is one of a dozen with the same issue, so it would take some work to change them all and measure the effect. Looking at the generated code:

```swift
    @inline(never)
    var leftMost: Expr {
        var expr = self
        while expr.count > 0 { expr = expr.args[0] }
        return expr
    }

```

generates

```swift
Calculator`Expr.leftMost.getter:
    0x1030cf244 <+0>: stp x22, x21, [sp, #-0x30]!
    0x1030cf248 <+4>: stp x20, x19, [sp, #0x10]
    0x1030cf24c <+8>: stp x29, x30, [sp, #0x20]
    0x1030cf250 <+12>: add x29, sp, #0x20
    0x1030cf254 <+16>: ldr x21, [x20, #0x38]
    0x1030cf258 <+20>: ldr x19, [x21, #0x10]
    0x1030cf25c <+24>: mov x0, x20
    0x1030cf260 <+28>: bl 0x1035c1688 ; symbol stub for: swift_retain
-> 0x1030cf264 <+32>: cbz x19, 0x1030cf290 ; <+76> at Expr.swift
    0x1030cf268 <+36>: ldr x19, [x21, #0x20]
    0x1030cf26c <+40>: mov x0, x19
    0x1030cf270 <+44>: bl 0x1035c1688 ; symbol stub for: swift_retain
    0x1030cf274 <+48>: mov x0, x20
    0x1030cf278 <+52>: bl 0x1035c1670 ; symbol stub for: swift_release
    0x1030cf27c <+56>: ldr x21, [x19, #0x38]
    0x1030cf280 <+60>: ldr x8, [x21, #0x10]
    0x1030cf284 <+64>: mov x20, x19
    0x1030cf288 <+68>: cbnz x8, 0x1030cf268 ; <+36> [inlined] generic specialization <Graphing_Calculator.Expr> of Swift.ContiguousArray.subscript.getter : (Swift.Int) -> τ_0_0 at <compiler-generated>
    0x1030cf28c <+72>: b 0x1030cf294 ; <+80> at Expr.swift:223:9
    0x1030cf290 <+76>: mov x19, x20
    0x1030cf294 <+80>: mov x0, x19
    0x1030cf298 <+84>: ldp x29, x30, [sp, #0x20]
    0x1030cf29c <+88>: ldp x20, x19, [sp, #0x10]
    0x1030cf2a0 <+92>: ldp x22, x21, [sp], #0x30
    0x1030cf2a4 <+

```

while

```swift
    @inline(never)
    var leftMost: Expr {
        unowned var expr = self
        while expr.count > 0 { expr = expr.args[0] }
        return expr

```

generates

```swift
Graphing Calculator`Expr.leftMost.getter:
    0x100ba77e4 <+0>: stp x22, x21, [sp, #-0x30]!
    0x100ba77e8 <+4>: stp x20, x19, [sp, #0x10]
    0x100ba77ec <+8>: stp x29, x30, [sp, #0x20]
    0x100ba77f0 <+12>: add x29, sp, #0x20
-> 0x100ba77f4 <+16>: mov x0, x20
    0x100ba77f8 <+20>: bl 0x1010997c0 ; symbol stub for: swift_unownedRetainStrong
    0x100ba77fc <+24>: ldr x8, [x20, #0x38]
    0x100ba7800 <+28>: ldr x19, [x8, #0x10]
    0x100ba7804 <+32>: bl 0x1010997b4 ; symbol stub for: swift_unownedRetain
    0x100ba7808 <+36>: bl 0x101099670 ; symbol stub for: swift_release
    0x100ba780c <+40>: cbz x19, 0x100ba7860 ; <+124> at Expr.swift
    0x100ba7810 <+44>: mov x0, x20
    0x100ba7814 <+48>: bl 0x1010997c0 ; symbol stub for: swift_unownedRetainStrong
    0x100ba7818 <+52>: ldr x8, [x20, #0x38]
    0x100ba781c <+56>: ldr x9, [x8, #0x10]
    0x100ba7820 <+60>: cbz x9, 0x100ba7884 ; <+160> [inlined] Swift runtime failure: Index out of range at <compiler-generated>
    0x100ba7824 <+64>: ldr x19, [x8, #0x20]
    0x100ba7828 <+68>: mov x0, x19
    0x100ba782c <+72>: bl 0x1010997b4 ; symbol stub for: swift_unownedRetain
    0x100ba7830 <+76>: mov x0, x20
    0x100ba7834 <+80>: bl 0x1010997a8 ; symbol stub for: swift_unownedRelease
    0x100ba7838 <+84>: mov x0, x20
    0x100ba783c <+88>: bl 0x101099670 ; symbol stub for: swift_release
    0x100ba7840 <+92>: mov x0, x19
    0x100ba7844 <+96>: bl 0x1010997c0 ; symbol stub for: swift_unownedRetainStrong
    0x100ba7848 <+100>: ldr x8, [x19, #0x38]
    0x100ba784c <+104>: ldr x21, [x8, #0x10]
    0x100ba7850 <+108>: bl 0x101099670 ; symbol stub for: swift_release
    0x100ba7854 <+112>: mov x20, x19
    0x100ba7858 <+116>: cbnz x21, 0x100ba7810 ; <+44> at Expr.swift:222:39
    0x100ba785c <+120>: b 0x100ba7864 ; <+128> at Expr.swift:223:16
    0x100ba7860 <+124>: mov x19, x20
    0x100ba7864 <+128>: mov x0, x19
    0x100ba7868 <+132>: bl 0x1010997c0 ; symbol stub for: swift_unownedRetainStrong
    0x100ba786c <+136>: bl 0x1010997a8 ; symbol stub for: swift_unownedRelease
    0x100ba7870 <+140>: mov x0, x19
    0x100ba7874 <+144>: ldp x29, x30, [sp, #0x20]
    0x100ba7878 <+148>: ldp x20, x19, [sp, #0x10]
    0x100ba787c <+152>: ldp x22, x21, [sp], #0x30
    0x100ba7880 <+156>: ret    
    0x100ba7884 <+160>: brk #0x1

```

but I am in over my depths to interpret any of that.

---

<div class="post-metadata">

**Author:** ![tera](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/tera/32/38201_2.png) [@tera](https://forums.swift.org/u/tera)\
**Post date:** [April 29, 2022, 9:53pm UTC](https://forums.swift.org/t/arc-tail-recursion/57054/4 "2022-04-29T21:53:31Z")

</div>

What's count, is it a computed variable, can it cause ARC traffic?

would that make a difference?

```swift
  unowned(unsafe) var e = expr

```

ps. i presume the above output is for "release" mode?

pps. if count is a wrapper for "args.count" (as it seems) then you may probably change the code to use "args.first" instead.

---

<div class="post-metadata">

**Author:** ![RonAvitzur](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ronavitzur/32/13927_2.png) [@RonAvitzur](https://forums.swift.org/u/RonAvitzur)\
**Post date:** [April 29, 2022, 10:01pm UTC](https://forums.swift.org/t/arc-tail-recursion/57054/5 "2022-04-29T22:01:38Z")

</div>

> [@tera](#):
>
> What's count, is it a computed variable, can it cause ARC traffic?

The `count` property is just shorthand for `args.count`

> [@tera](#):
>
> ps. i presume the above output is for "release" mode?

Yes, definitely.

> [@tera](#):
>
> ` unowned(unsafe) var e = expr`

```swift
    @inline(never)
    var leftMost: Expr {
        unowned(unsafe) var expr = self
        while expr.count > 0 { expr = expr.args.first! }
        return expr
    }

```

generates

```swift
Graphing Calculator`Expr.leftMost.getter:
    0x104c137e4 <+0>: stp x20, x19, [sp, #-0x20]!
    0x104c137e8 <+4>: stp x29, x30, [sp, #0x10]
    0x104c137ec <+8>: add x29, sp, #0x10
    0x104c137f0 <+12>: ldr x0, [x20, #0x38]
    0x104c137f4 <+16>: ldr x8, [x0, #0x10]
-> 0x104c137f8 <+20>: cbz x8, 0x104c1380c ; <+40> at Expr.swift:223:16
    0x104c137fc <+24>: bl 0x105105688 ; symbol stub for: swift_retain
    0x104c13800 <+28>: ldr x20, [x0, #0x20]
    0x104c13804 <+32>: bl 0x105105670 ; symbol stub for: swift_release
    0x104c13808 <+36>: b 0x104c137f0 ; <+12> [inlined] Graphing_Calculator.Expr.count.getter : Swift.Int at Expr.swift:124:22
    0x104c1380c <+40>: mov x0, x20
    0x104c13810 <+44>: ldp x29, x30, [sp, #0x10]
    0x104c13814 <+48>: ldp x20, x19, [sp], #0x20
    0x104c13818 <+52>: b 0x105105688 ; symbol stub for: swift_retain

```

---

<div class="post-metadata">

**Author:** ![tera](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/tera/32/38201_2.png) [@tera](https://forums.swift.org/u/tera)\
**Post date:** [April 29, 2022, 10:05pm UTC](https://forums.swift.org/t/arc-tail-recursion/57054/6 "2022-04-29T22:05:00Z")

</div>

and this one any better?

```
while expr.args.first != nil { expr = expr.args.first! }

```

you may later on optimise this to calculate the expression once, perhaps by using another unowned variable.

_ps. also, consider switching to value types! It might be a big change to your code base but the end result might well worth it._

---

<div class="post-metadata">

**Author:** ![jrose](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/jrose/32/408_2.png) [@jrose](https://forums.swift.org/u/jrose)\
**Post date:** [April 29, 2022, 10:08pm UTC](https://forums.swift.org/t/arc-tail-recursion/57054/7 "2022-04-29T22:08:16Z")

</div>

Swift will not let you do anything with a value without it being retained, or without a promise that someone else is retaining it in the mean time. There aren't many generally supported ways to spell the latter if it can't be inferred from the structure of the code, though there have been various proposals to add such functionality (which I'm having trouble finding right now).

In this case, the code in question _is_ enough to guarantee that, since the compiler can see that indeed no mutations can happen at all here. So I'd say this is a missed optimization opportunity and leave it at that.

---

<div class="post-metadata">

**Author:** ![RonAvitzur](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ronavitzur/32/13927_2.png) [@RonAvitzur](https://forums.swift.org/u/RonAvitzur)\
**Post date:** [April 29, 2022, 10:12pm UTC](https://forums.swift.org/t/arc-tail-recursion/57054/8 "2022-04-29T22:12:31Z")

</div>

> [@jrose](#):
>
> In this case, the code in question _is_ enough to guarantee that, since the compiler can see that indeed no mutations can happen at all here. So I'd say this is a missed optimization opportunity and leave it at that.

I wonder if this is a regression. I _thought_ I inspected this about a year ago and found that the recursive version both elided out the retain/release and also did the tail-recursion optimization. But I didn't take exhaustive notes at the time, so I may be misremembering.

---

<div class="post-metadata">

**Author:** ![jrose](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/jrose/32/408_2.png) [@jrose](https://forums.swift.org/u/jrose)\
**Post date:** [April 29, 2022, 10:15pm UTC](https://forums.swift.org/t/arc-tail-recursion/57054/9 "2022-04-29T22:15:23Z")

</div>

It's certainly possible, I bet some of the work for [A roadmap for improving Swift performance predictability: ARC improvements and ownership control](https://forums.swift.org/t/a-roadmap-for-improving-swift-performance-predictability-arc-improvements-and-ownership-control/54206) resulted in regressions that weren't strictly related to that model change.

---

<div class="post-metadata">

**Author:** ![RonAvitzur](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ronavitzur/32/13927_2.png) [@RonAvitzur](https://forums.swift.org/u/RonAvitzur)\
**Post date:** [April 29, 2022, 10:27pm UTC](https://forums.swift.org/t/arc-tail-recursion/57054/10 "2022-04-29T22:27:51Z")

</div>

> [@tera](#):
>
> and this one any better?
> 
> `while expr.args.first != nil { expr = expr.args.first! }`

That generated identical code to `while expr.count > 0 { expr = expr.args.first! }`

> [@tera](#):
>
> _ps. also, consider switching to value types! It might be a big change to your code base but the end result might well worth it._

I've been considering it in depth while rewriting all the ancient C++ code over the last year, but I fear I would only be trading one set of issues for another. I couldn't see how to do it in a way that simplified the structure of the various parts using `Expr`. On the one hand, the C++ is significantly faster. However, it was not thread-safe and it was extremely fragile doing all memory management manually. The Swift rewrite using ARC does the same work in about 25% the lines of source code and is significantly less fragile to use, so I'm willing to accept a performance penalty for using ARC _if necessary_. Having said that, I keep posting these questions to ensure that I'm not leaving any performance gains on the ground just out of ignorance.

Should I post this issue to [bugs.swift.org](http://bugs.swift.org)? Or is that on github now?

---

<div class="post-metadata">

**Author:** ![tera](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/tera/32/38201_2.png) [@tera](https://forums.swift.org/u/tera)\
**Post date:** [April 29, 2022, 10:33pm UTC](https://forums.swift.org/t/arc-tail-recursion/57054/11 "2022-04-29T22:33:56Z")

</div>

> [@RonAvitzur](#):
>
> I've been considering it in depth while rewriting all the ancient C++ code over the last year, but I fear I would only be trading one set of issues for another.

I see. Yet another option could be manual linked lists instead of arrays.

> [@RonAvitzur](#):
>
> The Swift rewrite using ARC does the same work in about 25% the lines of source code and is significantly less fragile to use

What is the slowdown compared to C++?

> [@RonAvitzur](#):
>
> Should I post this issue to [bugs.swift.org](http://bugs.swift.org)? Or is that on github now?

[Swift Bugs](http://bugs.swift.org) will suggest you using [GitHub Issues](https://github.com/apple/swift/issues) on the first page.

---

<div class="post-metadata">

**Author:** ![RonAvitzur](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ronavitzur/32/13927_2.png) [@RonAvitzur](https://forums.swift.org/u/RonAvitzur)\
**Post date:** [April 29, 2022, 10:44pm UTC](https://forums.swift.org/t/arc-tail-recursion/57054/12 "2022-04-29T22:44:45Z")

</div>

> [@tera](#):
>
> What is the slowdown compared to C++?

It depends on what the user is doing. For most things: none. Most things are compute-bound in numeric computations, for which the Swift code has comparable performance to the C++ code now (after a learning curve using the Unsafe APIs.) The ARC issues only arise where the code is compute bound on symbolic computation of expression trees, which can arise from documents with ridiculously large equations or a complex series of definitions that generate large equations internally. [x.com](https://twitter.com/RonAvitzur/status/1461023215724097536) details diving into one such example. The last document I measured that was compute bound in symbolic code showed a 3x slowdown in the Swift version, but I haven't looked at enough cases to know if that is typical.

---

<div class="post-metadata">

**Author:** ![RonAvitzur](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ronavitzur/32/13927_2.png) [@RonAvitzur](https://forums.swift.org/u/RonAvitzur)\
**Post date:** [April 29, 2022, 11:15pm UTC](https://forums.swift.org/t/arc-tail-recursion/57054/13 "2022-04-29T23:15:50Z")

</div>

Submitted to [missed optimization opportunity for elimination of retain/release and tail recursion · Issue #58549 · apple/swift · GitHub](https://github.com/apple/swift/issues/58549)

---

<div class="post-metadata">

**Author:** ![tera](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/tera/32/38201_2.png) [@tera](https://forums.swift.org/u/tera)\
**Post date:** [May 2, 2022, 12:16am UTC](https://forums.swift.org/t/arc-tail-recursion/57054/14 "2022-05-02T00:16:44Z")

</div>

> [@RonAvitzur](#):
>
> > [@tera](#):
> >
> > _ps. also, consider switching to value types! It might be a big change to your code base but the end result might well worth it._
> 
> I've been considering it in depth while rewriting all the ancient C++ code over the last year, but I fear I would only be trading one set of issues for another. I couldn't see how to do it in a way that simplified the structure of the various parts using `Expr` . On the one hand, the C++ is significantly faster. However, it was not thread-safe and it was extremely fragile doing all memory management manually. The Swift rewrite using ARC does the same work in about 25% the lines of source code and is significantly less fragile to use, so I'm willing to accept a performance penalty for using ARC _if necessary_ .

You may find the following applicable to your case. I played with several tree implementations, value and reference types, binary and non binary, here is the result of that microbenchmark (in each case it's creating a tree with 16M nodes and doing various typical operations on the tree: traverse, reverse, clone, delete). All times are in ms (the smaller the better):

```swift
				create travers reverse	clone delete
RefTree 2258	716 1143	9541	3661
RefBinTree 1114	390 532 1891	2246
ValueTree 1113	371 350 2159	1547
ValueBinTree 1104	474 3537	3400	3656
RawBinTree 258 224 176 0 23

```

> **The main data structures used.**
>
> ```swift
> class RefTree: Tree {
> var id: Int
> var value: Int
> var nodes: [RefTree]
> }
> 
> class RefBinTree: Tree {
> var id: Int
> var value: Int
> var left: RefBinTree?
> var right: RefBinTree?
> }
> 
> struct ValueTree: Tree {
> var id: Int
> var value: Int
> var nodes: [ValueTree]
> }
> 
> struct ValueBinTree: Tree {
> var id: Int
> var value: Int
> var left: MyOptional<ValueBinTree>
> var right: MyOptional<ValueBinTree>
> }
> 
> struct RawBinTreeNode {
> var value: Int
> var left: Int = 0
> var right: Int = 0
> }
> 
> struct RawBinTree: Tree {
> var id: Int
> }
> 
> ```
> 
> MyOptional is like Optional - I wasn't use Optional in a recursive data structure - not possible to put "indirect" on a struct or it's member.

> **Note on the RawBinTree.**
>
> RawBinTree is a custom data structure that's neither value nor reference - it's using fixed sized nodes, referenced by their Int ids, nodes are allocated from an arena (which is resized via realloc), deleted nodes are put on a linked list of free nodes. The reason clone / delete is fast is because it is a single realloc + memmove. Raw tree can only hold simple value types (like ints / enums without associated values or with simple associated values), more complex dynamic types like String or Array are not supported although fixed sized short strings (e.g. typical formula labels like "x") can be implemented "inline" and more complex types can be placed in an out of place table with entries referenced via short integer indices. If I were to implement a non binary variant of "RawBinTree" I'd probably go with a fixed sized nodes still:
> 
> ```swift
> struct RawTreeNode {
> var value: Int
> var right: Int = 0 // sibling nodes, 0 terminated
> var child: Int = 0 // first child node
> }
> 
> ```
