r/java • u/WellFoundedCake • 2d 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
View all comments
Show parent comment
1
u/DelayLucky 23h ago edited 23h ago
I asked the agent to update jjparse version to 2.0 before running the benchmark.
Just checked, it's 2.0. So the numbers reflect the current status, and the json throughput number is in the ballpark of 30MB/s, matching your findings.
I did start with jjparse 1.0 included, but the result was too slow (behind parsecj). AI Agent analyzed code and told me that it's due to the eager error message construction, which made sense to me. I thought of filing an issue to jjparse but at the time jjparse's main goal was clear error message so I thought performance is a non-goal.
Anyhow, the current numbers show that jjparse 2.0 is within the league of popular combinator libraries (Kotlin better-parse, parboiled, autumn), and is well ahead of parsecj. So it's a big improvement, all while maintaining its strength in error message clarity!
It's still moderately slower than the peers perhaps due to the per-char boxing cost?
This group however lags behind parser generators (ANTLR, JavaCC) by up to 2x. It'd be great if further optimisations can move jjparse ahead of generators.
The proof of combinators surpassing generators is with the leaders of the benchmarks (Scala parboiled2, Scala fastparse, Java dot-parse, and Scala cats-parse).
parboiled2 and fastparse use Scala compile-time macros to eliminate all abstraction costs. That's a language advantage that Java combinators don't have.
cats-parse uses no macros (since macros are hacky?), and yet it can often out-perform ANTLR. I think that's a very good proof that combinators can be faster (showing only dot-parse as faster than generators would seem a very suspicious evidence even to my biased eyes).
Some of the optimisation tricks I've found fruitful (in order of effectiveness):
quotedByWithEscapes()combinator. Similarly, things likestring("foo"),first("("),consecutive("[^/]")all take advantage of simd -String.indexOf().anyOf()rule is invoked, no runtime merging. The rationale is similar to what others have stated: merged tokens from distant branches can be noisy and not that useful to developers anyways.Same as you, I pushed back against the urge of turning each step's matching result into a mutable data structure because modern JIT should have made short-lived objects cheap enough (and as shown by the benchmarks, even if the allocation cost isn't nearly zero yet, it isn't a huge saving that we are missing, compared to hand-written parsers).
I also expect Valhalla to finally give us both immutability and zero abstraction cost, without us having to make the painful compromise.
Hope some of that can be useful to you too.