C++ target performance

[ghost]

I found the C++ target to have poor performance, when parsing and creating a parse tree.
How does that compare to the Java target?

When parsing a 227,000-line file of C code the ANTLR parser required 14 seconds.
A parser generated by LRSTAR required 0.1 seconds. It looks very strange.

Has anybody compared the C++ performance to the Java performance ?

[KvanTTT]

Similar issues:

• Parsing with C++ target 5x slower than Java
• [Cpp] I found Cpp-runtime is 4x slower than Java-runtime
• Performance across targets

[ghost]

OK, Java target is 5x faster than C++.
In my experience LRSTAR parsers are 140x faster than ANTLR C++ targets.
So then only 28x faster than ANTLR Java targets. That's still very strange.
Does anybody want to try LRSTAR to verify my findings? I'm not an ANTLR
or Java guy.
https://sourceforge.net/project/lrstar

[kaby76]

I don't think there's a good Antlr grammar for C. The one in grammars-v4/c requires huge lookaheads for expressions and declarations, and is ambiguous for parameterDeclarations. The expression rules are unnatural for Antlr. Similar rules in the Java Language Spec were refactored for performance. It seems as though it's derived from ISO 9899, but I can't tell what refactorings were made.

[ghost]

I used the same C grammar for both ANTLR and LRSTAR, which seemed to work fine.
The grammar was a large subset (90%) of the full specification. LRSTAR can read ANTLR
grammars (without Labels and a few other operators). Maybe it's like comparing apples
to oranges. I did not study the C++ target code. It's possible to create C++ code that is
not fast. It was about 2 years ago. I should repeat the test again and take a closer look
at the C++ target. Also I should use the Java target for a comparison.

Unfortunately, this stuff takes time.

[kaby76]

I would recommend reading the paper at https://www.antlr.org/papers/LL-star-PLDI11.pdf, generating a parser for a simple grammar and looking over the generated code and ATNs. Antlr performs a powerset construction from ATNs at parse time for branch predictions in the recursive descent parse. There's no simple table representing either DFA or ATN graphs.

[ghost]

OK, thanks. But 14 seconds seems like a lot of time to ser up branch predictions. Apples to oranges, I guess. I'll look at the paper.

[KvanTTT]

If I understand correctly, the more actual article exists: https://www.antlr.org/papers/allstar-techreport.pdf It's not draft.

[ghost]

So, what you are saying is that you have to pay a performance price to avoid the complexity of LALR(k) or LL(k)?
But it was 140x slower than LALR(1). I suspect that most of the problem is NOT in the ALL(*) algorithm. It has to
be somewhere else, serialization, unicode to char, constructors-destructors, or something in the C++ target. I
haven't gotten around to redoing the test yet, but it's on my to-do list.

[kaby76]

Paul, could you post the 227k-line file so I can do a quick profile?

[ghost]

test.input.txt

[kaby76]

Paul, Thanks for that file.

Yes, grammars-v4/c takes a long time--12s for the C# target. So, I decided to dive into some profiling using the C# target.

Of the 12 seconds to run, 6 seconds is in AdaptivePredict(), and most of that in Closure() or Closure_(). Most of the calls to AdaptivePredict() don't create any new DFA state, but closure()/closure_() is called nonetheless. So, even though we may start in a DFA, most of the time it doesn't help: the parser is constantly going back to an ATN config set to interpret the next state to move to on a symbol because the DFA state is parse stack sensitive (see Function 4 in the paper, if D0 stack sensitive then input.seek(start); return LLpredict(A, start, γ0);, section 3.1 Predictions sensitive to the call stack). I think it may be stack sensitive because the grammar is ambiguous, but I don't know if semantic predicates would help in disambiguating.

Yes, it's spending most of the time predicting what to do in the recursive descent.

[ghost]

Wow. Is that the same behavior with Java target? I assume it is.
It seems like a heavy price to pay, but ALL(*) seems to work for most people.
Honey badger?

[ghost]

Thanks kaby76. It would have taken me a long time to figure that out, too long.
Closure? Kind of like what a parser generator does, but at parsing time? Then
that's what makes ALL(*) so powerful.

My LRSTAR does LR(*) at parsing time, but it's shallow LR(*). It looks ahead
only as far as it needs to, but it refuses to be recursive (call itself), so shallow.
I would like to make a deep LR(*) that is recursive in the near future, but I'm
feeling like Terence Parr when he said, ANTLR 4 is the last one.

Thanks again.