Deep recursion in deinit should not happen

Evolution Discussion
39

The following implements a simplified version of non recursive deallocation algorithm that might be good for Swift / Objective-C and other ref count based languages.

  • The sketch is done in C++ subset (C with inheritance and inference)

  • The sketch reuses retainCount variable storage for the link variable for objects being deallocated.

  • The particular guinea pig user type doesn't matter for this sketch. Currently it uses a binary tree structure as an example. If you want to experiment with a different user data structure adjust these two overrides accordingly:

    virtual int objectCount() override {
    return 2;
}
virtual id objectAtIndex(int i) override {
    return i == 0 ? left : right;
}

Sketch output when recursion is used (mimics the current recursive algorithm found in Swift & Objective-C). Note the indentation:

test1 (small tree)
    1 deinit Node root
        2 deinit Node left
            3 deinit Node left-a
            4 deinit Node left-b
        5 deinit Node right
            6 deinit Node right-a

test2 (long list)
b4 release
1000 deinit Node node
2000 deinit Node node
3000 deinit Node node
...
21000 deinit Node node
22000 deinit Node node
23000 deinit Node node

ThreadSanitizer:DEADLYSIGNAL
==67795==ERROR: ThreadSanitizer: SEGV on unknown address 0x60000108a000 (pc 0x0001001912b7 bp 0x7ffeef6f7250 sp 0x7ffeef6f7230 T2047778)
==67795==The signal is caused by a WRITE memory access.

Sketch output when recursion is not used:

test1 (small tree)
    1 deinit Node root
    2 deinit Node left
    3 deinit Node left-a
    4 deinit Node left-b
    5 deinit Node right
    6 deinit Node right-a

test2 (long list)
b4 release
1000 deinit Node node
2000 deinit Node node
3000 deinit Node node
...
98000 deinit Node node
99000 deinit Node node
100000 deinit Node node
after release
done
Implementation 
#include <stdio.h>
#include <assert.h>

#define var auto
#define let const auto
#define nil nullptr

let useRecursion = false;

struct NSObject;

typedef NSObject* id;

static var gap = 0;
static var printEnabled = true;

void printGap() {
    for (var i = 0; i < gap; i++) {
        printf("    ");
    }
}

struct String {
    char str[256];
};

struct NSObject {
    union {
        int retainCount;
        id link;
    } u;
    
    NSObject() {
        u.retainCount = 1;
    }
    
    virtual ~NSObject() {}
    
    id retain() {
        u.retainCount++;
        return this;
    }
    
    void release() {
        if (--u.retainCount == 0) {
            dealloc();
        }
    }
    
    int retainCount() {
        return u.retainCount;
    }
    
    virtual void deinit() {
        static var printCount = 0;
        
        printCount++;
        if (printEnabled || (printCount % 1000) == 0) {
            if (printEnabled) {
                printGap();
            }
            printf("%d deinit %s\n", printCount, description().str);
        }
    }
    
    virtual void dealloc() {
        gap++;
        if (useRecursion) {
            deallocRecursive();
        } else {
            deallocNonRecursive();
        }
        gap--;
    }
    virtual String description() = 0;
    virtual int objectCount() = 0;
    virtual id objectAtIndex(int index) = 0;

    void deallocRecursive() {
        deinit();
        
        for (var n = objectCount(), i = 0; i < n; i++) {
            if (let object = objectAtIndex(i)) {
                object->release();
            }
        }
        delete this;
    }
    
    void deallocNonRecursive() {
        u.link = nil;
        var deallocTop = this;
        
        while (deallocTop) {
            let cur = deallocTop;
            deallocTop = cur->u.link;
            
            cur->deinit();
            
            for (var i = cur->objectCount() - 1; i >= 0; i--) {
                if (let object = cur->objectAtIndex(i)) {
                    if (object->retainCount() > 1) {
                        object->release(); // won't recurse
                    } else {
                        // object is being deallocated. can now reuse retainCount storage for link
                        object->u.link = deallocTop;
                        deallocTop = object;
                    }
                }
            }
            
            delete cur;
        }
    }
};

// Example guinea pig user data structure

struct Node: NSObject {
    typedef NSObject super;
    const char* name;
    Node* left;
    Node* right;
    
    Node(const char* name, Node* left = nil, Node* right = nil) : name(name), left(left), right(right) {}
    
    virtual String description() override {
        String string;
        snprintf(string.str, sizeof(string.str), "Node %s", name);
        return string;
    }

    virtual int objectCount() override {
        return 2;
    }
    virtual id objectAtIndex(int i) override {
        return i == 0 ? left : right;
    }
};

void test() {
    printf("test1 (small tree)\n");
    let tree = new Node("root", new Node("left", new Node("left-a"), new Node("left-b")), new Node("right", new Node("right-a")));
    tree->release();
    printf("\n");
    
    printf("test2 (long list)\n");

    printEnabled = false;
    Node* first = nil;
    
    for (var i = 0; i < 100000; i++) {
        first = new Node("node", first);
    }
    printf("b4 release\n");
    first->release();
    printf("after release\n");
    printf("done\n");
}

int main() {
    test();
    return 0;
}

/*
 
Sketch output when recursion is used (mimics the current recursive algorithm found in Swift & Objective-C). Note indentation:

test1 (small tree)
    1 deinit Node root
        2 deinit Node left
            3 deinit Node left-a
            4 deinit Node left-b
        5 deinit Node right
            6 deinit Node right-a

test2 (long list)
b4 release
1000 deinit Node node
2000 deinit Node node
3000 deinit Node node
...
21000 deinit Node node
22000 deinit Node node
23000 deinit Node node

ThreadSanitizer:DEADLYSIGNAL
==67795==ERROR: ThreadSanitizer: SEGV on unknown address 0x60000108a000 (pc 0x0001001912b7 bp 0x7ffeef6f7250 sp 0x7ffeef6f7230 T2047778)
==67795==The signal is caused by a WRITE memory access.

Sketch output when recursion is not used:

test1 (small tree)
    1 deinit Node root
    2 deinit Node left
    3 deinit Node left-a
    4 deinit Node left-b
    5 deinit Node right
    6 deinit Node right-a

test2 (long list)
b4 release
1000 deinit Node node
2000 deinit Node node
3000 deinit Node node
...
98000 deinit Node node
99000 deinit Node node
100000 deinit Node node
after release
 
*/

Edit: fixed some bugs in the implementation and now reusing retainCount variable storage for the link variable.

1 Like