#Why does this stack overflow?

27 messages · Page 1 of 1 (latest)

tacit forge
#

I understand why stack overflows happen if you have too many recursive function calls, but I don't know why this specific code overflows. It's only using a for loop and the Boxs should mean that all the data is put on the heap not the stack(?). Any help would be appreciated 🙂

fn main() {
    make_tree(1_000_000);
}

enum Tree{
    Leaf,
    Node((Box<Tree>, Box<Tree>))
}

fn make_tree(n:usize){
    let mut res = Tree::Leaf;
    for _ in 0..n {
        res = Tree::Node((
            Box::new(Tree::Leaf),
            Box::new(res),
        ));
    }
}
chilly plover
#

huh

#

so it's actually not constructing the tree that's the problem, it's dropping it

#

?play ```rust
fn main() {
make_tree(1_000_000);
println!("done");
}

enum Tree{
Leaf,
Node((Box<Tree>, Box<Tree>))
}

fn make_tree(n:usize){
let mut res = Tree::Leaf;
for _ in 0..n {
res = Tree::Node((
Box::new(Tree::Leaf),
Box::new(res),
));
}
// no stack overflow if we explicitly forget the tree instead of dropping it
std::mem::forget(res);
}

rotund gardenBOT
# 
done```
chilly plover
#

iirc the drop is recursive

tacit forge
#

oooh interesting, thanks for the help!

chilly plover
#

?play ```rust
pub fn main() {
make_tree(1_000_000);
}

enum Tree {
Leaf,
Node((Box<Tree>, Box<Tree>)),
}

impl Drop for Tree {
fn drop(&mut self) {
match self {
Self::Leaf => {}
Self::Node((left, right)) => {
let mut stack = vec![
std::mem::replace(&mut **left, Self::Leaf),
std::mem::replace(&mut **right, Self::Leaf),
];
while let Some(mut node) = stack.pop() {
match &mut node {
Self::Leaf => {}
Self::Node((left, right)) => {
stack.push(std::mem::replace(&mut **left, Self::Leaf));
stack.push(std::mem::replace(&mut **right, Self::Leaf));
}
}
}
}
}
}
}

pub fn make_tree(n: usize) {
let mut res = Tree::Leaf;
for _ in 0..n {
res = Tree::Node((Box::new(Tree::Leaf), Box::new(res)));
}
}

rotund gardenBOT
chilly plover
#

there I've added an iterative drop impl

tacit forge
#

oooh thanks even more! I was just reading the page on "too many lists" and working out how to do this 😁

chilly plover
#

ah, yeah, I was about to link that lol

#

but yeah, rust's default drop impl basically just recursively drops every member of a type. You can probably see how that would stack overflow with that deeply-nested of a data structure

tacit forge
#

yeah it completely makes sense, I imagine the same is going to be true for clone too

chilly plover
#

probably, yeah

#

if you use the default derive

#

?play ```rust
fn main() {
make_tree(1_000_000);
}

#[derive(Clone)]
enum Tree{
Leaf,
Node((Box<Tree>, Box<Tree>))
}

fn make_tree(n:usize){
let mut res = Tree::Leaf;
for _ in 0..n {
res = Tree::Node((
Box::new(Tree::Leaf),
Box::new(res),
));
}
let res2 = res.clone();
std::mem::forget(res);
std::mem::forget(res2);
}

rotund gardenBOT
# 
thread 'main' has overflowed its stack
fatal runtime error: stack overflow```
chilly plover
#

yep

#

by the way

#

if you're actually using a type like this (which you probably shouldn't in most cases, as the too many lists book explains), you could store both child nodes together inside one box

#

i.e., ```rust
enum Tree{
Leaf,
Node(Box<(Tree, Tree)>),
}

#

this has basically the same semantics, but uses I think half as many memory allocations

#

it's a little harder to swap around nodes though

tacit forge
#

Thanks again!

floral ridge