Performance Investigation

[bd82]

Context

The early performance numbers of the parser were not stellar.
On modern powerful laptop parsing the java-design-patterns repo took about 4 seconds.

• That repo is about 28k Lines of java code (neto).

7K lines a second is not actually that bad considering the prettier scenario
where normally you would only incrementally re-print the files which have changed (staged in git).

• Consider that the average Java File only takes a few miliseconds to parse that would not be noticeable by human user.

However those are not good performance numbers relative to the previous parser implementation (x3 faster). And also compared to other Chevrotain based Parsers, For example the ECMAScript parser example runs at over 100K LOC per second.

Causes

The main culprit is the use of backtracking to keep the grammar as aligned as possible
with the official specifications style.
In some cases backtracking is required to resolve ambiguities regardless of the need to align with the grammar, e.g lambda expression vs cast expression vs parenthesis expression.

Current Status

Several quick wins, optimizations focused around reducing the use of backtracking
or "fast failing" during backtracking have been applied recently.

• 5e3121a
• 5bd3016
• 4c03377
• 9e4dca9

This has already more than doubled the performance to 16-17K LOC per second.
and am confidant more optimizations are possible.

So while this is not going to be the fastest Java Parser in the world partially
due to the design goal to align strong with the spec's style, and partly because the Java
grammar is not LL(K) while Chevrotain is at its core an LL(K) parser library.

It would be more than fast enough for the prettier scenario and also most
other scenarios that do not need to process millions of lines of code at once.

[bd82]

I will keep the issue open to update it with future performance related work.

[bd82]

lets re-open this if/when there would actually be future performance work 😄