Deep recursion in deinit should not happen

Evolution Discussion
43

Relative figures for swift are about the same. All tests got proportionally faster on the newer hardware. Obj-C becomes slower. Putting the old and new results together:

Old (x86 computer of 2016):
C            alloc: 13.66, dealloc: 13.96, total: 27.63
Swift unsafe alloc: 14.85, dealloc: 14.12, total: 28.98 (5% slower than C)
Obj-C MRC    alloc: 15.84, dealloc: 18.27, total: 34.11 (23% slower than C)
Swift (ARC)  alloc: 20.43, dealloc: 26.36, total: 46.79 (69% slower than C)
Obj-C ARC    alloc: 21.27, dealloc: 32.58, total: 53.86 (95% slower than C)

New (M1 Pro computer of 2021):
C            alloc:  3.21, dealloc:  4.16, total:  7.37
swift unsafe alloc:  3.68, dealloc:  3.99, total:  7.68 (4% slower than C)
objc MRC     alloc:  4.69, dealloc:  5.18, total:  9.87 (34% slower than C)
swift (ARC)  alloc:  4.22, dealloc:  8.12, total: 12.34 (67% slower than C)
objc ARC     alloc:  5.84, dealloc: 14.47, total: 20.31 (176% slower than C)

Yep, simple case fixed:

stackoverflow1 - direct recursion ✅ 
class Node1 {
    var next: Node1?
    init(next: Node1?) {
        self.next = next
    }
}

func stackOverflow1() {
    var top: Node1?
    print("alloc")
    for _ in 0 ..< 100000 {
        top = Node1(next: top)
    }
    print("free!!")
    top = nil
    print("done!!")
}

More general cases not:

stackOverflow2 - indirect recursion 💣 
class NodeA {
    var next: NodeB?
    init(next: NodeB?) {
        self.next = next
    }
}

class NodeB {
    var next: NodeA?
    init(next: NodeA?) {
        self.next = next
    }
}

func stackOverflow2() {
    var top: NodeA?
    print("alloc")
    for _ in 0 ..< 100000 {
        top = NodeA(next: NodeB(next: top))
    }
    print("free")
    top = nil // crash here
    print("done")
}
stackOverflow3 - children in array 💣 
class Node3 {
    var children: [Node3]
    init(children: [Node3]) {
        self.children = children
    }
}

func stackOverflow3() {
    var top = Node3(children: [])
    print("alloc")
    for _ in 0 ..< 100000 {
        top = Node3(children: [top])
    }
    print("free")
    top = Node3(children: []) // crash
    print("done")
}
stackOverflow4 - indirect enum 💣 
indirect enum Node4 {
    case last(payload: Int)
    case notLast(payload: Int, next: Node4)
    
    init(payload: Int) {
        self = .last(payload: payload)
    }
    init(payload: Int, next: Node4) {
        self = .notLast(payload: payload, next: next)
    }
}

func stackOverflow4() {
    var top = Node4(payload: 0)
    print("alloc")
    for i in 1 ..< 100000 {
        top = Node4(payload: i, next: top)
    }
    print("free")
    top = Node4(payload: 0) // crash
    print("done")
}
1 Like