Switch from manual parsing to winnow makes parsing 30% slower

[zeenix]

Hi, I switch a manual parsing code to winnow here and benchmarks say that it's now 30% slower. I was hoping for the opposite. :) Pasting the relevant code here:

fn validate(path: &[u8]) -> Result<()> {
    use winnow::{
        ascii::alphanumeric1,
        combinator::{alt, repeat},
        error::InputError,
        Parser,
    };
    // Rules
    //
    // * At least 1 character.
    // * First character must be `/`
    // * No trailing `/`
    // * No `//`
    // * Only ASCII alphanumeric, `_` or '/'

    let allowed_chars = alt((
        alphanumeric1::<&[u8], InputError<_>>.map(|_| ()),
        b'_'.map(|_| ()),
    ));
    let component = (b'/', repeat(1.., allowed_chars).map(|()| ()));
    let non_root = repeat(1.., component).map(|()| ());
    let root = b'/'.map(|_: u8| ());

    alt((non_root, root)).parse(path).map_err(|_| {
        Error::IncorrectType
    })
}

I already checked if just reducing to non_root case or disallowing _ (i-e removing the alt use) help but they don't see to have any affect.

[zeenix]

@epage Do you have a clue what could be the culprit here? :)

[epage]

I suspect the alts are the biggest problem. Next, I would try to minimuze the use of repeat.

Something like

let allowed_chars = (b'a'..=b'z', b'A'..=b'Z', b'0'..=b'9', b'_');
let component = take_while(1.., allowed_chars);
let non_root = repeat(0.., (b'/', component).map(|()| ());
let root = b'/'.map(|_| ());
alt((non_root, root)).parse(path).map_err(|_| {
    Error::IncorrectType
})

Hmm, was hoping to get rid of that last alt but I think switching to take_while will make a big difference.

[zeenix]

@epage Thanks so much for your quick response! You suggestion indeed helps a lot. This code:

   let allowed_chars = (b'a'..=b'z', b'A'..=b'Z', b'0'..=b'9', b'_');
    let component = (b'/', take_while::<_, _, InputError<_>>(1.., allowed_chars));
    let non_root = repeat(1.., component).map(|()| ());
    let root = b'/'.map(|_: u8| ());

    alt((non_root, root))
        .parse(path)
        .map_err(|_| Error::InvalidObjectPath)
}

improves the performance by 11%. Unfortunately, this is still 19% slower than the manual code. :( I'll try to remove the last repeat and map use..

[zeenix]

Just to keep things in perspective: We're talking 57 vs 67 ns here. So it's not a huge deal, given that it does simplify the code. It's just that it'd be nice to get the same performance (if not better).

[zeenix]

ok, so I simplified it quite a bit:

    let allowed_chars = (AsChar::is_alphanum, b'_');
    let component = take_while::<_, _, InputError<_>>(1.., allowed_chars);

    (b'/', separated(0.., component, b'/'))
        .map(|_: (u8, ())| ())
        .parse(path)
        .map_err(|_| Error::InvalidObjectPath)

Unfortunately this doesn't help with performance but I guess 10 ns extra for parsing a million of these strings, is not a big price to pay for the simplification and readability improvements.

[epage]

Does () for the error type make a difference? I wonder if removing ErrMode (#75) would help.

[zeenix]

I winnow'ified another parser in zbus project, and this one regresses by 20%, even though I'm not using alt or repeat:

fn validate(name: &str) -> Result<()> {
    use winnow::{
        combinator::separated,
        error::InputError,
        stream::AsChar,
        token::{one_of, take_while},
        Parser,
    };
    // Rules
    //
    // * Only ASCII alphanumeric, `_` or '-'.
    // * Must not begin with a `.`.
    // * Must contain at least one `.`.
    // * Each element must:
    //  * not begin with a digit.
    //  * be 1 character (so name must be minimum 3 characters long).
    // * <= 255 characters.
    if name.len() > 255 {
        return Err(Error::InvalidWellKnownName(format!(
            "`{}` is {} characters long, which is longer than maximum allowed (255)",
            name,
            name.len(),
        )));
    }

    let first_element_char = one_of((AsChar::is_alpha, '_', '-'));
    let subsequent_element_chars =
        take_while::<_, _, InputError<_>>(0.., (AsChar::is_alphanum, '_', '-'));
    let element = (first_element_char, subsequent_element_chars);
    let mut well_known_name = separated(2.., element, '.');

    well_known_name
        .parse(name)
        .map_err(|e| Error::InvalidWellKnownName(format!("{e}")))
}

I tried replacing one_of with dispatch and InputError with () but it didn't help anything.

[epage]

Your parsing rules do not care about UTF-8, so I would parse well_known_name.as_bytes() for a significant performance boost.

[zeenix]

Believe it or not, this is exactly what I did just after posting this comment:

    well_known_name
        .parse(name.as_bytes())
        .map_err(|_| Error::InvalidWellKnownName(format!("Invalid well-known name")))

Not only the performance improved, the specific benchmark for this, show a significant improvement over the manual parser:

parse_name/well_known   time:   [93.976 ns 94.246 ns 94.547 ns]
                        change: [-20.096% -18.719% -17.513%] (p = 0.00 < 0.05)
                        Performance has improved.

[zeenix]

oh my! A full conversion to operate on bytes:

    let first_element_char = one_of((AsChar::is_alpha, b'_', b'-'));
    let subsequent_element_chars = take_while::<_, _, ()>(0.., (AsChar::is_alphanum, b'_', b'-'));
    let element = (first_element_char, subsequent_element_chars);
    let mut well_known_name = separated(2.., element, b'.');

    well_known_name.parse(name.as_bytes()).map_err(|_| {
        Error::InvalidWellKnownName(
            "Invalid well-known name. \
            See https://dbus.freedesktop.org/doc/dbus-specification.html#message-protocol-names-bus"
            .to_string(),
        )
    })

makes it much faster:

parse_name/well_known   time:   [63.440 ns 63.666 ns 63.906 ns]
                        change: [-33.898% -32.696% -31.559%] (p = 0.00 < 0.05)

And this is only in comparison to the previous version (already using bytes). 😍