Continuing the topic from this thread as a discussion, I would like to ask if there are any news about this issue.
@Joe_Groff: Has there been progress on this? Thanks.
A quick search on GitHub found this:
At the linked issue is noted:
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) is not resolved in Swift 5.6.1.
Definitely a progress!
Although the check of this form is quite shallow.
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()
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?
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().
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.
This is a more simple case for which the fix should work (I guess on 5.7)
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.
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()
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.
2 Likes
Thank you. Please have a look at one approach and its implementation, hope you can find something useful in it.