"线程 '<main>'已溢出其堆栈"建造大树时 [英] "thread '<main>' has overflowed its stack" when constructing a large tree
问题描述
我实现了一个树结构:
use std::collections::VecDeque;
use std::rc::{Rc, Weak};
use std::cell::RefCell;
struct A {
children: Option<VecDeque<Rc<RefCell<A>>>>
}
// I got thread '<main>' has overflowed its stack
fn main(){
let mut tree_stack: VecDeque<Rc<RefCell<A>>> = VecDeque::new();
// when num is 1000, everything works
for i in 0..100000 {
tree_stack.push_back(Rc::new(RefCell::new(A {children: None})));
}
println!("{:?}", "reach here means we are not out of mem");
loop {
if tree_stack.len() == 1 {break;}
let mut new_tree_node = Rc::new(RefCell::new(A {children: None}));
let mut tree_node_children: VecDeque<Rc<RefCell<A>>> = VecDeque::new();
// combine last two nodes to one new node
match tree_stack.pop_back() {
Some(x) => {
tree_node_children.push_front(x);
},
None => {}
}
match tree_stack.pop_back() {
Some(x) => {
tree_node_children.push_front(x);
},
None => {}
}
new_tree_node.borrow_mut().children = Some(tree_node_children);
tree_stack.push_back(new_tree_node);
}
}
但它崩溃了
thread '<main>' has overflowed its stack
我该如何解决?
推荐答案
您遇到的问题是因为您有一个巨大的节点链表.当该列表被删除时，第一个元素首先尝试释放结构的所有成员.这意味着第二个元素做同样的事情，依此类推，直到列表的末尾.这意味着您将拥有一个与列表中元素数量成正比的调用堆栈！
The problem that you are experiencing is because you have a giant linked-list of nodes. When that list is dropped, the first element tries to free all the members of the struct first. That means that the second element does the same, and so on, until the end of the list. This means that you will have a call stack that is proportional to the number of elements in your list!
这是一个小复制:
struct A {
children: Option<Box<A>>
}
fn main() {
let mut list = A { children: None };
for _ in 0..1_000_000 {
list = A { children: Some(Box::new(list)) };
}
}
以下是您修复它的方法:
And here's how you would fix it:
impl Drop for A {
fn drop(&mut self) {
if let Some(mut child) = self.children.take() {
while let Some(next) = child.children.take() {
child = next;
}
}
}
}
此代码用迭代覆盖了默认的递归放置实现.它将 children 从节点中剥离出来，用一个终端项 (None) 替换它.然后它允许节点正常丢弃，但不会有递归调用.
This code overrides the default recursive drop implementation with an iterative one. It rips the children out of the node, replacing it with a terminal item (None). It then allows the node to drop normally, but there will be no recursive calls.
代码有点复杂，因为我们放不下自己，所以我们需要跳两步舞，忽略第一项，然后把所有孩子都吃掉.
The code is complicated a bit because we can't drop ourselves, so we need to do a little two-step dance to ignore the first item and then eat up all the children.
另见:
这篇关于"线程 '<main>'已溢出其堆栈"建造大树时的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
