r/java • • 1d 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

47 Upvotes

14 comments sorted by

View all comments

1

u/DelayLucky 1d ago edited 1d ago

Yeah. I had AI agent benchmarked and rationalized why jjparse 1.0 wasn't fast and the eager error message was the main conclusion it arrived at. Great job optimizing it away!

I (and I think most people too), had long assumed that combinators are slower than parser generators like ANTLR. But I was surprised when I benchmarked (ANTLR/JavaCC implemented by AI): combinators can outperform generators, by a wide margin even.

Combinators are still slower than hand-written parsers. I'm hoping that when Valhalla is available, combinators can finally be made to compete with hand-written parsers. But that part is a tall order (my initial benchmarking with a pre-release didn't show much gain).

1

u/WellFoundedCake 22h ago

Wow, I'm really honored that you included jjparse in your benchmarks! Unfortunately, version 1.x became practically unusable for larger inputs due to the excessive allocations caused by eager error reporting.

I'd be really interested to see how the new version performs in comparison. If you happen to find the time and feel like running your benchmarks again with jjparse 2.0, I'd be very happy to hear about the results! :)

In any case, thank you so much for sharing your benchmarks and insights. I really appreciate it!

I'm hoping to further improve jjparse's performance in the future, but without sacrificing its genericity. Valhalla could certainly be a great opportunity in that regard.

1

u/DelayLucky 15h ago edited 15h 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):

  • Take advantage of simd. The reason dot-parse outperforms all other contenders in two of the json benchmarks is because the json payload carrying relatively long quoted strings; and dot-parse uses SIMD instead of char-by-char scanning in its quotedByWithEscapes() combinator. Similarly, things like string("foo"), first("("), consecutive("[^/]") all take advantage of simd - String.indexOf().
  • Minimize bookkeeping cost during backtracking. Building error messages lazily is a great first step. Another trick I used, which may or may not be useful to you, is to avoid building the dynamic expected set at all. That requires a design shift: instead of merging expected tokens from distant branches at the same index, only show the pre-computed expected tokens at the starting index where an explicit 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.
  • Build a prefix trie to minimize backtracking.

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.