Add lalrpop as benchmark for rosetta-rs

[Pat-Lafon]

I noticed that there is https://github.com/rosetta-rs/parse-rosetta-rs run by epage. There they list a bunch of different parsing crates with their corresponding performance. It seems like lalrpop is mentioned but doesn't have a corresponding implementation. Might be a good thing to add to see how things stack up(and to be transparent) if anyone is interested.

It's also not clear to me if lalrpop's table is fully accurate. Is "precedence climbing" equivalent to lalrpop's precedence annotations(which the table says lalrpop doesn't have)?

[dburgener]

I've created a PR in parse-rosetta-rs to add a lalrpop example: rosetta-rs/parse-rosetta-rs#42

Feedback and comments welcome.

[dburgener]

BTW, here's the results on my box as of right now:

Name	Overhead (release)	Build (debug)	Parse (release)	Downloads	Version
null	0 KiB	471ms	26ms	-	-
chumsky	780 KiB	9s	2s		v0.3.0
combine	227 KiB	5s	1s		v3.8.1
lalrpop	1,526 KiB	15s	1s		v0.20.0
nom	158 KiB	3s	1s		v7.1.3
peg	34 KiB	3s	20ms		v0.8.1
pest	154 KiB	5s	1s		v2.7.3
pom	216 KiB	3s	2s		v3.3.0
winnow	137 KiB	2s	1s		v0.5.15
yap	89 KiB	861ms	1s		v0.10.0

lalrpop's build time is a lot slower than the alternatives. My impression without a lot of investigation is that that's primarily because of our more extensive dependency tree compared to the other parsers in the benchmark. Also, lalrpop looks like the only one shipping a "build.rs", so we're maybe actually building our parser at build time, while others are functioning more as a library. I'm not convinced that build time is a particularly significant metric though.

On runtime performance, we seem solidly middle of the road. This table (generated by a parse-rosetta-rs script) only does second level granularity (there's probably an option for ms granularity, I haven't looked...), so it obscures the differences within that 1s range. But we seem somewhat in line on json parsing as of now.

I'd take everything with a massive grain of salt until it's actually merged. And my system for the benchmarking isn't the most quiescent in the world, so I'm hoping that epage will rerun "official" benchmarks with lalrpop once it's merged.

[Pat-Lafon]

I haven't used most of the parsers here but my understanding was that many of them are built in the recursive-descent style. My expectation would be that lalrpop trades off a slower compile time to generate a faster parser. It should be the case that users only pay this cost once but maybe that is something that needs to be communicated clearly as an expectation. (Maybe there are easy ways to bring the compile time down?)

Hmm, the one on the landing page has ms resolution but that might be because the benchmarks are slower on your machine. Looking at the formatting code, they only show ms times if you are below one second.

Looking at your pr, I do expect that you actually need to build up a value. All the benchmarks except the peg one do this.

[dburgener]

Looking at your pr, I do expect that you actually need to build up a value. All the benchmarks except the peg one do this.

That makes sense. I happened to pick the peg one at random to use as a model to build off of, so I guess I was misled there :)

Hmm, the one on the landing page has ms resolution but that might be because the benchmarks are slower on your machine. Looking at the formatting code, they only show ms times if you are below one second.

Yeah, that's probably it. Looking more at the script to make the table, it does have a feature of rounding to seconds for loads over 1s.

I assume the official benchmarks will be much more useful than the ones on my machine.

(Maybe there are easy ways to bring the compile time down?)

Yeah, worth looking into. Personally, I'm basically always happy to tradeoff a longer compile time for a quicker runtime though. That narrative would be nicer if we actually had a quicker runtime, but hopefully #814 will be a big step forward there.

[Pat-Lafon]

One thing I hadn't realized/remembered from looking at the build times is that both lalrpop takes up like half the time and regex takes up a fair bit of the rest of it. Worse though, regex and it's subsequent dependencies get built twice in release more even though they have the same features because build-dependencies are treated differently from dependencies. See https://www.reddit.com/r/rust/comments/ymuuuz/why_does_cargo_not_dedup_normal_and_build/iv5t9hm/?utm_source=share&utm_medium=web3x&utm_name=web3xcss&utm_term=1&utm_content=share_button . It seems like an easy win but I didn't find a solution to get around this.

[Pat-Lafon]

Nevermind, you can do

[profile.release.package."*"]
opt-level = 3

but that just means that the first compilation of regex which is the main bottle neck is slower. Actually might make the compilation time worse.

[dburgener]

FYI, this has merged, and epage has reran the benchmarks. Our time of "2s" makes us in the slowest chunk, which makes sense and to some extent is why we're having this conversation. When I get some more time on this (tomorrow?) I'll do a head to head comparison on #814 with this.