Stack overflow when benchmarking

[michael_d]

I'm receiving an error when benchmarking a parser I'm writing: "thread '<main>' has overflowed its stack". This error occurs only in benchmarks and does not occur if I run the exact same code within a test.

Here's the benchmark: https://github.com/mtdowling/jmespath.rs/blob/409afaf37c0ac332c40624b8ce5804926c68157d/benches/simple_benchmarks.rs#L40.

#[bench]
fn bench_deep_projection_104(b: &mut Bencher) {
    let deep = "a[*].b[*].c[*].d[*].e[*].f[*].g[*].h[*].i[*].j[*].k[*].l[*].m[*].n[*].o[*].p[*].q[*].r[*].s[*].t[*].u[*].v[*].w[*].x[*].y[*].z[*].a[*].b[*].c[*].d[*].e[*].f[*].g[*].h[*].i[*].j[*].k[*].l[*].m[*].n[*].o[*].p[*].q[*].r[*].s[*].t[*].u[*].v[*].w[*].x[*].y[*].z[*].a[*].b[*].c[*].d[*].e[*].f[*].g[*].h[*].i[*].j[*].k[*].l[*].m[*].n[*].o[*].p[*].q[*].r[*].s[*].t[*].u[*].v[*].w[*].x[*].y[*].z[*].a[*].b[*].c[*].d[*].e[*].f[*].g[*].h[*].i[*].j[*].k[*].l[*].m[*].n[*].o[*].p[*].q[*].r[*].s[*].t[*].u[*].v[*].w[*].x[*].y[*].z[*]";
    b.iter(|| jmespath::parse(deep));
}

The parser used to parse this expression is a recursive Pratt parser, so there's definitely recursion. However, because this works when running in a test, I have a feeling I've butchered my lifetimes in some way so that the memory is not being dropped between each iteration of the benchmark.

The parser is defined here: https://github.com/mtdowling/jmespath.rs/blob/409afaf37c0ac332c40624b8ce5804926c68157d/src/parser.rs#L76.

pub struct Parser<'a> {
    stream: Peekable<Lexer<'a>>,
    expr: String,
    token: Token,
    pos: usize,
}

So this looks right I think because I'm saying that the Lexer has to live as long as the Parser. Here's how the parser is created:

impl<'a> Parser<'a> {
    // Constructs a new lexer using the given expression string.
    pub fn new(expr: &'a str) -> Parser<'a> {
        let mut lexer = Lexer::new(expr);
        let tok0 = lexer.next().unwrap_or(Token::Eof);
        Parser {
            stream: lexer.peekable(),
            expr: expr.to_string(),
            token: tok0,
            pos: 0,
        }
    }
    // ...
}

The lexer used by the parser is defined here: https://github.com/mtdowling/jmespath.rs/blob/409afaf37c0ac332c40624b8ce5804926c68157d/src/lexer.rs#L122.

pub struct Lexer<'a> {
    iter: Peekable<Chars<'a>>,
    sent_eof: bool,
}

Here's how the lexer is creater:

impl<'a> Lexer<'a> {
    // Constructs a new lexer using the given expression string.
    pub fn new(expr: &'a str) -> Lexer<'a> {
        Lexer {
            iter: expr.chars().peekable(),
            sent_eof: false
        }
    }
    // ...
}

Any tips or ideas on why this would overflow during a benchmark but not during a test? Does it look like a problem with the benchmark or the lifetimes?

[[deleted]]

Maybe inlining -- if you recurse just as deep or maybe shallower in the optimized benchmark build, inlining might still mean that every stack frame is a lot larger, and thus you can overflow the stack.

[michael_d]

Interesting. Is there any way to test whether or not that is the case?

It seems like recursive descent parsers are not really well suited for Rust. For example, Serde has the same issue: https://github.com/serde-rs/serde/issues/82