# Deep recursion in deinit, revisited

**URL:** <https://forums.swift.org/t/deep-recursion-in-deinit-revisited/57654>\
**Category:** Discussion\
**Created:** [May 28, 2022, 6:07am UTC](https://forums.swift.org/t/deep-recursion-in-deinit-revisited/57654 "2022-05-28T06:07:54Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![sspringer](https://avatars.discourse-cdn.com/v4/letter/s/e9c0ed/32.png) [@sspringer](https://forums.swift.org/u/sspringer)\
**Post date:** [May 28, 2022, 6:07am UTC](https://forums.swift.org/t/deep-recursion-in-deinit-revisited/57654/1 "2022-05-28T06:07:54Z")

</div>

Continuing the topic from [this thread](https://forums.swift.org/t/deep-recursion-in-deinit-should-not-happen/54987) as a discussion, I would like to ask if there are any news about this issue.

> [@Deep recursion in deinit should not happen](https://forums.swift.org/t/deep-recursion-in-deinit-should-not-happen/54987/8):
>
> We have some ideas for how to apply this technique to Swift, but we haven't gotten around to implementing them yet.

@Joe_Groff: Has there been progress on this? Thanks.

---

<div class="post-metadata">

**Author:** ![benrimmington](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/benrimmington/32/695_2.png) [@benrimmington](https://forums.swift.org/u/benrimmington)\
**Post date:** [May 28, 2022, 11:12am UTC](https://forums.swift.org/t/deep-recursion-in-deinit-revisited/57654/2 "2022-05-28T11:12:07Z")

</div>

A quick search on GitHub found this:

> <https://github.com/apple/swift/pull/41459>
>
> …tures
> 
> Adds detection of linearly recursive data structures by finding stored… properties that share the type of the class the dealloc is being generated for. Each link will then be deallocated in a loop, while ensuring to keep the next link alive to prevent the recursion. This prevents stack overflows for long chains while also improving performance.
> 
> rdar://89162954

---

<div class="post-metadata">

**Author:** ![sspringer](https://avatars.discourse-cdn.com/v4/letter/s/e9c0ed/32.png) [@sspringer](https://forums.swift.org/u/sspringer)\
**Post date:** [May 29, 2022, 5:56pm UTC](https://forums.swift.org/t/deep-recursion-in-deinit-revisited/57654/3 "2022-05-29T17:56:20Z")

</div>

At the linked issue is noted:

```nohighlight
drexin merged commit 6d55ecd into apple:main on 14 Mar

```

and the current Swift 5.6.1 is from April 8, 2022, so I would guess that it is part of the current Swift version, or will it be in a next version? Because this issue (cf. [the other thread](https://forums.swift.org/t/deep-recursion-in-deinit-should-not-happen/54987)) is _not resolved in Swift 5.6.1._

---

<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 30, 2022, 12:12am UTC](https://forums.swift.org/t/deep-recursion-in-deinit-revisited/57654/4 "2022-05-30T00:12:11Z")

</div>

> [@](#):
>
> Adds detection of linearly recursive data structures by finding stored properties that share the type of the class the dealloc is being generated for. Each link will then be deallocated in a loop, while ensuring to keep the next link alive to prevent the recursion. This prevents stack overflows for long chains while also improving performance.

Definitely a progress!

> **Although the check of this form is quite shallow.**
>
> ```swift
> class Node1 {
> var next: Node2?
> init(next: Node2?) {
> self.next = next
> }
> }
> 
> class Node2 {
> var next: Node1?
> init(next: Node1?) {
> self.next = next
> }
> }
> 
> func foo() {
> var top: Node1?
> print("alloc")
> for _ in 0 ..< 100000 {
> top = Node1(next: Node2(next: top))
> }
> print("free")
> top = nil // crash here
> print("done")
> }
> 
> foo()
> 
> ```

---

<div class="post-metadata">

**Author:** ![philipturner](https://avatars.discourse-cdn.com/v4/letter/p/b5e925/32.png) [@philipturner](https://forums.swift.org/u/philipturner)\
**Post date:** [May 30, 2022, 1:06am UTC](https://forums.swift.org/t/deep-recursion-in-deinit-revisited/57654/5 "2022-05-30T01:06:44Z")

</div>

Question @tera: I'm running the following file on both the Swift 5.6.1 release and the May 18 Swift 5.7 snapshot. Why is the script executing in \< 0.1 seconds and with no crash?

```swift
class Node1 {
    var next: Node2?
    init(next: Node2?) {
        self.next = next
    }
}

class Node2 {
    var next: Node1?
    init(next: Node1?) {
        self.next = next
    }
}

func foo() {
    var top: Node1?
    print("alloc")
    // My Mac doesn't have 8 exabytes of memory.
    for _ in 0 ..< 1_000_000_000_000_000_000 {
        top = Node1(next: Node2(next: top))
    }
    print("free")
    top = nil // crash NOT here
    print("done")
}

```

_My bad. I forgot to call `foo()`._

```nohighlight
zsh: illegal hardware instruction swift file.swift

```

More precisely, it will crash if you loop 32609 or more times. If you loop 32608 or less times, it won't crash.

---

<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 30, 2022, 1:14am UTC](https://forums.swift.org/t/deep-recursion-in-deinit-revisited/57654/6 "2022-05-30T01:14:22Z")

</div>

> **This is a more simple case for which the fix should work (I guess on 5.7)**
>
> ```swift
> class Node1 {
> var next: Node1?
> init(next: Node1?) {
> self.next = next
> }
> }
> 
> func foo() {
> var top: Node1?
> print("alloc")
> for _ in 0 ..< 100000 {
> top = Node1(next: top)
> }
> print("free!!")
> top = nil
> print("done!!")
> }
> 
> foo()
> 
> ```

> **Edit: This common case is not covered by the fix.**
>
> ```swift
> class Node1 {
> var children: [Node1]
> init(children: [Node1]) {
> self.children = children
> }
> }
> 
> func foo() {
> var top = Node1(children: [])
> print("alloc")
> for _ in 0 ..< 100000 {
> top = Node1(children: [top])
> }
> print("free")
> top = Node1(children: []) // crash
> print("done")
> }
> 
> foo()
> 
> ```

---

<div class="post-metadata">

**Author:** ![drexin](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/drexin/32/7573_2.png) [@drexin](https://forums.swift.org/u/drexin)\
**Post date:** [June 1, 2022, 12:38am UTC](https://forums.swift.org/t/deep-recursion-in-deinit-revisited/57654/7 "2022-06-01T00:38:15Z")

</div>

Yes, the fix only works for the simple case. Mutual (or deeper) recursion pattern could be detected, but it requires more work and the deinit would be more complicated as well. We have some ideas around optimizing deinit for tree like structures as well and I think the same approach could work for the mutual recursion case as well.

That said, as with any optimization, we have to consider how much work we put into it vs. how much we gain. I am working on some more widely applicable optimizations at the moment, but I would love to get back to this eventually.

If you have real world use cases that would benefit from this, I‘d love to hear about them. It would help us prioritize this work appropriately.

---

<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:** [June 1, 2022, 1:15am UTC](https://forums.swift.org/t/deep-recursion-in-deinit-revisited/57654/8 "2022-06-01T01:15:12Z")

</div>

Thank you. Please have a look at [one approach](https://forums.swift.org/t/deep-recursion-in-deinit-should-not-happen/54987/23) and [its implementation](https://forums.swift.org/t/deep-recursion-in-deinit-should-not-happen/54987/39), hope you can find something useful in it.