Document that recursive 'owned' data structures may result in running out of stack space

[LouisJenkinsCS]

@mppf

Having a recursive data structure, such as a node in a linked list, easily results in running out of memory when using owned. This is because it will recursively invoke the destructor of each node and use O(N) space rather than O(1) space in an iterative method of destroying the list.

MWE

class Node {
    var data : int;
    var next : owned Node;
}

proc Node.deinit() {
    if data % 100 == 0 then writeln("Deallocating Node #", data);
}

class Stack {
    var head : owned Node;
}

proc Stack.push(elt) {
    var n = new owned Node(elt, head);
    head = n;
}

var s = new Stack();

writeln("Filling stack...");
for i in 1..100000 do s.push(i);

writeln("Deallocating Stack...");
delete s;

writeln("Done...");

Output:

Filling stack...
Deallocating Stack...
Deallocating Node #100000
Deallocating Node #99000
Deallocating Node #98000
Deallocating Node #97000
Deallocating Node #96000
Deallocating Node #95000
Deallocating Node #94000
Deallocating Node #93000
Deallocating Node #92000
Deallocating Node #91000
Deallocating Node #90000
Deallocating Node #89000
Deallocating Node #88000
Deallocating Node #87000
Deallocating Node #86000
Deallocating Node #85000
Deallocating Node #84000
Deallocating Node #83000
Deallocating Node #82000
Deallocating Node #81000
Deallocating Node #80000
Deallocating Node #79000
Deallocating Node #78000
Deallocating Node #77000
Deallocating Node #76000
Deallocating Node #75000
Deallocating Node #74000
Deallocating Node #73000
_pmiu_daemon(SIGCHLD): [NID 00028] [c0-0c0s7n0] [Fri Aug 17 17:50:29 2018] PE RANK 0 exit signal Segmentation fault

It should be noted that this is an inherent flaw in naive implementations of data structures, but it is extremely common and easy to come across, especially with the push towards using owned/borrowed/shared as first-class and unmanaged as second class.

Bonus - Iterative Destruction

while head != nil {
   var tmp = head;
   head = head.next;
   delete tmp;
}

[mppf]

I think such a data structure should just use unmanaged. However it is possible to manually destroy owned things in a loop with owned.clear. Note that the iterative destruction isn't that easy either and a new programmer would be likely to trip up on the issue either way. That's why we put things like list in a library :)

especially with the push towards using owned/borrowed/shared as first-class and unmanaged as second class.

While we encourage people to use owned/borrowed/shared because we think they are easier, they're not appropriate for every use case.

[LouisJenkinsCS]

In one of your slides at CHIUW, on slide 21, it gave a "mini binary tree" example where you have owned left and right tree nodes which would also suffer from this problem. I feel it would be dishonest to recommend it as unmanaged.

[LouisJenkinsCS]

Slide is here: https://chapel-lang.org/CHIUW/2018/ferguson-slides.pdf

[mppf]

I agree that pattern is problematic for large data structures but it's not obvious to me that it's the language / compiler's problem to solve vs. the user's. There are many easy-to-write ways of running out of stack space.

Sure, we could add arena allocation that the user could opt-in to, but the user could opt-in to unmanaged or write their own deinit for the data structure that used owned.clear() to delete everything in a iterative manner. So I don't think it really solves the problem, which I'd phrase as "A user might be surprised by the recursive deinitialization".

I think we should do the tail-recursion optimization anyway (assuming it is not too hard) because optimization is a good idea. But that wouldn't help with the tree example either.

[bradcray]

In one of your slides at CHIUW, on slide 21, it gave a "mini binary tree" example where you have owned left and right tree nodes which would also suffer from this problem.

Wouldn't this case only use O(log n) stack space rather than O(n)? (which I'd argue is not a problematic amount).

[LouisJenkinsCS]

Hmmm, that's right Brad, it does look like it's O(log(n)) for a balanced tree which should actually be fine. I guess it's only an issue for certain data structures and I still think there should be an abstraction to help for it.

[bradcray]

@LouisJenkinsCS: This issue feels like an "ain't broke / won't fix" to me. I think the feature is working as advertised and don't read any obvious requests in the issue description apart from "I wish this wouldn't happen." The main potential TODO I see is "implement a tail recursion optimization", but I think that's a separate issue than this one (at least based on the title and original description). Is it OK to close this?

[bradcray]

(Oh, and I just remembered that #10821 requests the tail optimization piece).

[LouisJenkinsCS]

Issue #10821 references this issue, do you still want me to close it?

[bradcray]

do you still want me to close it?

Yes. Closing the issue doesn't break the reference or prevent people from seeing it, just the implied burden/expectation.

[LouisJenkinsCS]

Actually, as a request I would like that this issue be documented somewhere before closing. It may come as a surprise that recursive data structures can run out of memory. While Rust has this issue as well, it does offer a solution to the problem, such as what is described in issue #10820. Some documentation would be all that I am asking for so that future users do not get surprised by this.

[bradcray]

I updated the title to reflect the revised request.

[mppf]

Tail-recursion optimization doesn't solve this issue (see https://github.com/chapel-lang/chapel/issues/10821#issuecomment-426317204 ).

It might be possible to solve the issue by making deinit routines accept a list of classes to destroy. Instead of calling delete recursively, they'd add class instances to this list. Might need a work list, etc. See https://github.com/chapel-lang/chapel/issues/10821#issuecomment-426318055

[LouisJenkinsCS]

Can this be generated by the compiler?

[mppf]

@LouisJenkinsCS - conceivably, but doing so isn't high on the priority list; "use unmanaged for such cases" seems like an OK place for the moment. Nonetheless I was thinking about it & so my comments above will hopefully be useful if/when somebody gets back to it.

[mppf]

Some discussion on Reddit about how the compiler can address this issue: https://www.reddit.com/r/ProgrammingLanguages/comments/9lrk20/chapel_1180/e7a3dab/