Why is LALRPOP so slow?

[joelreymont]

Menhir is OCaml's version of LALRPOP and is also blazingly fast.

Why is LALRPOP so slow compared to Menhir?

Has anyone profiled this already?

[dburgener]

There was some profiling done by a contributor a couple of years ago, which resulted in major performance improvements in the 0.20.2 release (we measured around a 50x speedup). In 0.20.2 and beyond, we're generally similar in performance to other rust parser generators according to this third party benchmark.

I definitely think there's more performance work to be done though. And performance can be very use-case dependent. The benchmark mentioned above is for a specific use case. We had some discussions of other use cases experiencing worse performance here: #1028. That thread discussed the idea of pre-compiling regexes for better performance, which would likely help, but no one has taken on the work.

I have a PR open to add benchmarking into lalrpop so that we can easily measure the benefits of future performance work (#981), but it's blocked on another open PR. Benchmarking and profiling are of course different activities, but benchmarking will help validate end to end any claimed improvements that we're evaluating. And if we expand out the suite of benches, that will also help with measuring which use cases are more or less performant.

So to answer your question - yes, someone has profiled, which resulted in a 50x speedup in 0.20.2, but I don't think anyone has profiled since 0.20.2.

If you wanted to collect and share any profiling data, we would definitely be interested, and I'm happy to review and accept performance improvement PRs.

[joelreymont]

I don't think my LALRPOP grammar is in any way degenerate but refining it was painfully slow. On the other hand, my Menhir grammar for the same parser was a pleasure to iterate on because Menhir, the LR(1) OCaml parser generator is so blazingly fast.

I did some cursory profiling or LALRPOP and narrowed the bottleneck to the lane table algorithm. I conclude then that I would need to drop the lane table algorithm and adopt the Menhir algorithm to truly speed up LALRPOP.

Would that be too big of a change to LALRPOP, though?

[dburgener]

Ah, I misunderstood initially. You're talking about the time to generate a grammar.

Most of our performance work has gone into the speed of the generated parsers. I would argue that's the more important metric, but it does mean that speed of generation has been largely unexamined and unoptimized. There may be wins to be had short of switching out algorithms. A conclusion that the slowness is in the lane table part is worth something, but that doesn't answer questions about whether it's an inherent slowness in the algorithm or if there are fixable issues in the implementation.

To directly answer your question, at least personally I don't have appetite for maintaining a different generation algorithm. I'd want to see someone with a solid contribution history sign up to support it over the long term to be willing to take it in. But that's just my personal opinion. Other maintainers may differ.

[joelreymont]

I'll take stab.

Please let me know if there are any profiling tools or approaches that you would recommend.

[joelreymont]

I take my comment back. I tried running the latest LALRPOP against my grammar, as well as other much larger grammars, and parser generation performance is super-fast! Also, I tried profiling and improving generation performance but couldn't eke out more than 2%. Thank you for such an awesome piece of software!