antlr / antlr/antlr4

[Java] ANTLR4 slower in a simple situation than ANTLR3

Open
#2,602 2 comments 0 reactions 0 assignees View on GitHub
Dominant language
Java
Stars
19k
Forks
3.5k
PR merge metrics
No merged PRs in 30d

Description

**Background:**
I am in the middle of upgrading our parsing engine from ANTLR3 to ANTLR4. Since our codebase relies heavily on the concept of ASTs, our design is to use ANTLR4's visitor pattern to create an AST that looks like what ANTLR3 would generate. Through some performance testing, we have found that a common pattern in our inputs are much slower than ANTLR3. The common pattern is a function call, where the function will take many parameters.

**Grammar:**
```
functionCall
: IDENT LPAREN (expression ( COMMA expression )* )? RPAREN
;

STRING_LITERAL
:
( '"' ( ESC | . )*? '"'
| '\'' ( ESC | . )*? '\''
)
;

fragment
ESC
: '\\'
( 'n'
| 'r'
| 't'
| '"'
| '\''
| '\\'
)
;
```

An `expression` could be very complicated but in the examples we used for performance testing, we only used Strings as an expression, so a sample input would be `func("1", "2", "3", ....)`.

**Performance results:**
ANTLR4 performs more than 40% worse than ANTLR3.

**Things I have tried:**
1. I tried the optimization mentioned in the book to use SLL parser to parse faster, but even with SLL, the performance improvement is minimal. Note that I am not counting the second "full" parsing in case SLL fails; parsing the sample input succeeds on SLL, but it's just not faster.
2. I used JProfiler and it seems that the most expensive part is `org.antlr.v4.runtime.ParserRuleContext.getRuleContexts()`.

Any ideas why ANTLR4 would be slower in this simple situation? Is there any optimizations we could do to make this faster?

Contributor guide

Open the contributing guide

Research direction

Start by reproducing the reported ANTLR3-versus-ANTLR4 comparison with the functionCall grammar and string-heavy input. Profile ParserRuleContext.getRuleContexts() as reported, then compare normal parsing with SLL parsing and determine whether a focused runtime or parser improvement can be validated by the same performance test.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
compilers, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.