OOPer, your response was very insightful and your guesses seem to be spot on! I did not realize that Apple's Swift implementation isn't even able to deallocate a class-based linked list such as:
final class LinkedList {
let next: LinkedList?
init(_ next: LinkedList? = nil) {
self.next = next
}
}
var lst = LinkedList()
for _ in 0..<150000 {
lst = .init(lst)
}
print("Done creating list")
// The following statement never returns
lst = LinkedList()
print("Completed program (this is never printed)")
The conclusion for me from this is that it's basically impossible to manage large interconnected data structures in Swift. For value types (such as enums and structs), it is trivial to construct very large values, but it's impossible to deallocate them afterwards since this process seems to be implemented recursively and you can't interfere.
Equally, for class-based data structures, deallocation of large interconnected object graphs isn't scaling as it's done recursively too utilizing the fixed stack. In this case, it is possible to interfere (as OOPer has shown), but doing this in general requires messing with retain counts (possibly via CFGetRetainCount). The implementation above works nicely only for the special case that linked list nodes are not referenced anywhere else.
BTW, I was also able to verify what OOPer was stating: that deallocation is recursive and uses the regular stack. The following code does execute correctly because I was sufficiently increasing the stack size (from 8MB to 10MB):
enum MyList {
case empty
indirect case pair(MyList)
}
let condition = NSCondition()
var t = Thread {
condition.lock()
var lst = MyList.empty
for _ in 0..<150000 {
lst = .pair(lst)
}
print("Done creating list")
// The following statement now returns
lst = .empty
print("Completed program (this is never printed)")
condition.signal()
condition.unlock()
}
t.stackSize = 2560 * 4096 // 10MB
condition.lock()
t.start()
print("Started")
condition.wait()
condition.unlock()
print("Finished")