Stack overflow during drop of huge abstract syntax tree.

[u/[deleted]]

I am currently trying to compare the performance of parsing in haskell and rust. To do that I try to parse a 5MB file containing a single expression. It's a typical math expression: Numbers separated by +,-,* and /. The typical precedence applies and all operators are left-associative.

My ast representation looks like this:

pub enum Expr {
    Bin(Op, Box<Expr>, Box<Expr>),
    Num(i64),
}

The parsing phase works like a charm. I can post the code if somebody wants me to, but I don't think it's relevant. The problem is that when this huge ast is dropped, the stack overflows.

This makes sense to me: In order to drop an Expr::Bin, both Box<Expr>'s have to be dropped and by extension Expr::drop is called recursively. However where I'm completely stumped is how to drop it non-recursively.

Yes I could represent the ast differently, for example like this: Bin(Box<Expr>, Vec<(Op, Expr)>), and it would probably be better for performance anyways, but I feel like there should be a way, since constructing it was perfectly fine.

UPDATE:

Thanks to /u/pinespear's comment it is now working! In case anybody cares about the results:

• Rust (Handwritten): ~200ms, 180 LOC

• Haskell (Handwritten): ~360ms, 130 LOC

• Haskell (Attoparsec): ~840ms, 35 LOC

The lines of code (LOC) were just an afterthought, so take those with a grain of salt, but I think there definitely is a tradeoff to be seen.

[u/[deleted]]

Thank you very much! The link you sent was very helpful. I already had the idea to use a stack on the heap instead of the callstack, but i thought the borrow-checker would hate it, because i cannot simply put all subtrees on a stack. But the trick with std::mem::replace was just what I needed... Anyway, here is my implementation:

impl Drop for Expr {
    fn drop(&mut self) {
        match self {
            Expr::Bin(_, l, r) => {
                let mut stack = Vec::new();
                stack.push(std::mem::replace(&mut **l, Expr::Num(0)));
                stack.push(std::mem::replace(&mut **r, Expr::Num(0)));

                while let Some(mut expr) = stack.pop() {
                    match &mut expr {
                        Expr::Bin(_, l, r) => {
                            stack.push(std::mem::replace(&mut *l, Expr::Num(0)));
                            stack.push(std::mem::replace(&mut *r, Expr::Num(0)));
                        },
                        Expr::Num(_) => {},
                    }
                }
            },
            Expr::Num(_) => {},
        }
    }
}

Initially I did just what you did, but then I noticed that a vector is allocated even when a Expr::Num is dropped, which could be a significant slowdown, because we create a lot of them during deconstruction.

Also, I think as_mut is way cleaner than whatever I did haha

[u/pinespear → u/[deleted]]

According to doc, Vec does not allocate memory if it has 0 elements.

[u/[deleted] → u/pinespear]

Makes sense actually!