r/java • u/WellFoundedCake • 8h ago
Lessons learned while optimizing my Java parser combinator library
A while ago, I shared my Java parser combinator library, jjparse, here on reddit. Since then, I've been working on a few improvements, which eventually led to the release of a new major version. I thought this would be a good opportunity to share some of the things I've learned along the way, give a little update on the project, and hopefully get some feedback and discussion going.
As you might know, parser combinators typically rely heavily on backtracking (which is the default in jjparse). Consequently, parser failures are not necessarily exceptional but often part of perfectly successful parsing operations.
My original implementation was pretty straightforward: Whenever a parser failed, it generated diagnostic information explaining what went wrong (i.e., an error message). A perfectly reasonable approach from a conceptual point of view, but as it turned out, not particularly efficient.
Even when parsing eventually succeeded, all those intermediate failures generated error messages that were immediately discarded. And with enough backtracking, that's a lot of unnecessary heap allocations. I only noticed this when I started experimenting with larger inputs for benchmarking. Smaller examples worked just fine, but larger ones showed wildly varying runtimes. Profiling eventually revealed that a substantial part of the runtime was spent dealing with all the garbage produced by error reporting.
So, my lesson learned here is to keep allocations on parser failures to a minimum and only generate detailed error messages when they're actually needed. Looking back, it seems pretty obvious, but I guess that's often the case with these things.
The new implementation stores the information needed for diagnostics in the parser itself. Failures now only point to this information, and actual error messages are generated lazily when requested. I've also added tracking of the farthest failure to provide more useful diagnostics in the presence of backtracking. Redesigning the error reporting also made me reconsider what information a useful error message should actually contain.
For ordinary syntax errors, expectations work quite well:
unexpected token 'x', expected token 'y'
However, parser combinators can also recognize languages beyond the class of context-free languages, and not every failure is purely syntactic in the typical sense. For example, when parsing identifiers that must not be reserved keywords, an explanation might be more useful than an expectation:
unexpected token 'x', because 'x' is a reserved keyword
This led me to distinguish between an expectation and a reason, both of which are optional. The general format of a reported error is now:
unexpected <input token>, expected <expectation> because <reason>
I'm still not entirely sure how flexible this design will turn out to be, particularly when it comes to composing expectations and reasons across parser alternatives. Should reasons be combined? Should expectations take precedence? What if different alternatives fail for entirely different reasons? I'd be interested in hearing what you think!
That aside, all these changes required some breaking API changes, hence version 2.0. A couple of other things I've been working on in this regard:
Input filtering: Previously, whitespace skipping was somewhat of a hack built into the parser implementation. Now, inputs can be filtered using another parser (
input.withFilter(parser)). Whether the implementation is particularly efficient remains to be seen, but I quite like how the API turned out.Benchmarks: I've finally added a JMH benchmark to the repository, parsing 10 - 100 MB of synthetically generated, non-repetitive JSON into an AST. The result is around 30 - 34 MB/s. Nothing to write home about compared to specialized parsers, but probably at least roughly comparable to other parser combinator libraries on the JVM (although I haven't tested that yet, tbh). One obvious performance bottleneck is the generic input abstraction, which means that even parsing plain text involves boxing and unboxing characters (or rather Unicode codepoints). I might eventually optimize this under the hood in the future, but I'd really like to preserve the generic API. After all, that's kind of the whole point of the library.
Anyway, I'm still figuring things out, and I'm sure there are plenty of things that could be improved. I'd particularly love to hear your thoughts on the API and overall design. Criticism, suggestions, alternative approaches, or even a PR are all very welcome!
For anyone interested in taking a look: https://github.com/BjoernLoetters/Jar-Jar-Parse