last day (15 days later) » 

21:54
0
Q: Can this recursive function take less stack space (without rewriting as a loop)?

Edward PetersI've got some code which is running for a while and then throwing stack overflow errors. Based on the behavior and debugging, I do not think this is a case of infinite recursion, but instead of deep (but finite) and inefficient recursion. I'm pretty convinced the following code is to blame: fn g...

@SvenMarnach So to answer your laziness question: The function can theoretically return without having called that closure. The closure could then be called at some future point, again lazily returning a structure that includes some number of closures. At no point would any execution of this function then be nested beneath another in the call stack.
@Ry- So there are two reasons I'm asking rather than doing that. One, testing is a pain, and the stuff I omitted to not bog SO down with unnecessary details makes it a little less trivial a rewrite. Two, and more importantly, I'm trying to gain insight into the workings of Rust, and I think I'll learn more by making this work recursively (or getting a definite answer why it can't.) FWIW, I did due dilligence making sure this is the issue - lldb shows a stack trace lousy with get_descendent_leaves calls, and printlns showed several threads deeply recursed in this function at once.
@SvenMarnach I was just considering that possibility - why would it only reduce the recursion depth by 1? Assuming I'm correct in understanding that Iterators are lazy, that would mean the recursive call was never made before the function returned. Wouldn't that mean that my code never contributed additional stack frames?
@SvenMarnach So it's Rust's implementation of flatten making the recursive calls? Looking at the source that seems possible. My only doubt is that I'm pretty sure I could write an interpreter (ignoring a laundry list of thing like user-defined iterators, thread safety, and everything else that Rust supports) that would evaluate this without a recursive call - for instance, Flatten.next is tail recursive, so it's certainly possible. (Also, rust supports tail recursion it's just not guaranteed, correct?)
Please provide a proper minimal reproducible example, otherwise we can't play around with your code.
"getting a small example that did the same thing without introducing a ton of my own assumptions isn't feasible" - So how are we supposed to help you? We can't see the other code, so now we have to make a bunch of assumptions that, according to what you say here, makes the entire discussion irrelevant ... I'd vote to close due to missing details. There's just really no point in discussing hypotheticals.
"I'm pretty convinced the following code is to blame:" - More than 90% of the time I've heard this it turned out to be wrong, wasting a bunch of our time in the process. Again, please provide an MRE, otherwise this entire question is pointless. If you are incapable of reproducing it with your own custom mocks that make this code compile, then this code is not the reason why it crashes.
@Finomnis I've edited in what I believe to be parallel behavior as an MRE.
@EdwardPeters It's a MRE if you actually say what it's supposed to do. From my point of view, it crashes, which is exactly what it's supposed to do. It already says awful_vec_builder, and that's what it is. So what's wrong with it?
@EdwardPeters "Can this be built" - can what be built? What's the desired output of the awful_vec_builder function?
The problem in your original example is that I don't know what self is and it makes absolutely no sense to me that we query a child recursively and then call something on self with it again. Your second example doesn't contain a tree, so I have absolutely no idea what I'm looking at.
@Finomnis I've edited in additional explanation of the example. If you need there to be an actual tree-as-data I can provide that (though it takes some work as the tree growth itself cannot be recursive), but this is actually a closer fit to the original, as children are computed in the recursive call rather than being natively pre-defined.
21:54
@EdwardPeters Your example makes much more sense with an actual explanation now. However, are you sure that the result of awful_vec_builder(5000,0) actually fits on the stack?
@Finomnis yes. It's a Vec, so it's heap allocated. :) (I checked that even making the base case empty, so the result is trivial in both heap and stack, still smashes the stack - see the commented line in the latest edit.)
vec![] and Vec::new() are identical. I'm talking about the map/flatten/collect calls. I'm not sure how much stack usage they cause. What's the reason to avoid something iterative? Like, an actual iterator?
@EdwardPeters This crashes as well, just fyi: play.rust-lang.org/…
I should have used vec![] there, the point was only that it was empty (and thus ultimately the result was empty) - so it's not the result that's consuming the stack (or the heap), it's the recursive calls.
I'm not sure what you mean about "avoiding something iterative". Are you referring to the "use a loop and two mut Vec thing I mentioned in the question, or the discussion of what it would look like if I returned an Iterator?
I mean, why recursion? This very reason is why recursion is avoided.
Complicated answer, two reasons. One, I think that the recursive representation is often clearer, especially if mixed functions come into play. Two, while I'm a newbie at Rust, my day job does involve writing stack-safe interpreters for IR that may itself not be stack safe - so I know this can be done, and I'm curious as to rusts behind-the-scenes behavior here.
22:07
The problem is that I don't know for sure where the stack space goes, to be honest. Let debug for a second.
I don't know if you read the long discussion thread, but we did eventually agree that if this returned an Iterator instead of pre-emptively collecting, it would not generate stack frames of this function - instead it would return a deeply-nested Iterator with a lot of Flattens in it, and the evaluation of those would be just as deep. (I'm trying to actually implement that, if you know how)
22:23
Is this a good representation of your original problem? play.rust-lang.org/…
When printing the stack address of the same variable in each stack frame, I get an estimated stack frame size of 1872 bytes. That seems quite excessive
5000 is just simply a really deep recursion tbh
 
1 hour later…
23:46
That representation is more or less correct - "depth" is not an attribute of "Point" to me, just something I included in the example that was done as part of the recursion.

last day (15 days later) »