Performance of right-associative operators

[01mf02]

Hi,

let me first thank you for your excellent work on chumsky, ariadne and other crates such as flume that I had the pleasure to use.

I am using chumsky in my jaq crate. @jameschenjav has hit a performance bottleneck in my parser, see 01mf02/jaq#7. I was able to trace down the problem to my implementation of right-associative operators, using Parser::foldr. I am basically following your technique in nano_rust.rs to implement operators with differing precedence, but I also require right-associative operators. A simplified version that demonstrates the problem is shown below:

use chumsky::{error::Simple, prelude::*};

fn bin<P, O>(prev: P, op: O) -> impl Parser<char, usize, Error = P::Error> + Clone
where
    P: Parser<char, usize> + Clone,
    O: Parser<char, char, Error = P::Error> + Clone,
{
    // right-associative: extremely slow!
    /*
    let args = prev.clone().then(op).repeated().then(prev);
    args.foldr(|(a, _op), b| a + b)
    */

    // left-associative
    let args = prev.clone().then(op.then(prev).repeated());
    args.foldl(|a, (_op, b)| a + b)
}

fn main() {
    let mut expr = Recursive::declare();

    let int = text::int::<char, Simple<char>>(10)
        .from_str()
        .unwrapped()
        .or(expr.clone().delimited_by(just('('), just(')')));
    let add = bin(int, just('+')).boxed();
    let sub = bin(add, just('-')).boxed();
    let mul = bin(sub, just('*')).boxed();
    let div = bin(mul, just('/')).boxed();

    expr.define(div);

    assert_eq!(expr.parse("3"), Ok(3));
    assert_eq!(expr.parse("((((1+2-3*4/5))))"), Ok(15));
}

When using the right-associative variant of the bin function, then the parser gets quite a bit slower; in particular when adding more parentheses in the parsed expression. Do you have any idea how to make right-associative operators faster?

[zesterer]

Apologies about not responding earlier. This behaviour is rather strange. I'll try to get the time to do some local testing.

[zesterer]

Hopefully #288 will go a long way toward improving the writing of operator parsing.

[01mf02]

The API proposed in #288 sounds indeed exactly like what I would need. In the mean time, I implemented manual precedence climbing, which solves the performance problem for my specific use case. A solution included with chumsky would still be preferable.

[zesterer]

I think I'm likely going to add a dedicated binary_op combinator, to be used like so:

expr.binary_op(just(Token::Add), |a, b| Expr::Add(a, b))

in the hopes that we can micro-optimise this case internally.

[Zij-IT]

Closable with #464?

[zesterer]

I think I'm going to leave this open for now. I think there's space for standalone combinators without wheeling out the pratt parser.