-
Notifications
You must be signed in to change notification settings - Fork 1
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Improve the performance of the new parser #37
Comments
The new parser will hang when parsing some scripts because of SLL parsing strategy. I'm not sure whether it is a bug of antlr4. parser.getInterpreter().setPredictionMode(PredictionMode.SLL); // try simpler/faster SLL(*)
parser.removeErrorListeners();
parser.setErrorHandler(new BailErrorStrategy()); |
Thread Dump:
Complete Dump:
|
@danielsun1106 Can you try using com.tunnelvisionlabs:antlr4 instead of org.antlr:antlr4? Let me know if the performance is noticeably different in your particular application. |
@sharwell |
@danielsun1106 The alternative package I mentioned contains a large number of optimizations which are not planned to be incorporated into the reference release. For most day-to-day users of ANTLR, these optimizations are excessively complicated and provide little real world benefit. However, on a few occasions I have seen large and/or complicated grammars unable to work at all without them. To make things worse, different grammars which require the "optimized" release tend to require it be used with different settings - for example the grammar for the Boo programming language requires us to enable an LL parsing setting that defaults to disabled in the optimized release because it actually slows down other grammars. If your test is limited to SLL parsing, then you are likely benefiting from one or more of the following features of the optimized release:
|
So maybe this is something that should be done once the grammar is stable? |
@sharwell Thanks for your detailed reply! The two-stage parsing strategy may be much suitable for the new parser based on Antlr4. It's pity that we can not apply two-stage parsing strategy because of the performance issue of @blackdrag You're right. We can tune the performance later. |
The tail call elimination is the biggie I suspect. I plan on following Sam's lead there and will introduce into antlr/antlr4 repo when it bumps up in priority for me. |
grails-web-databinding/src/main/groovy/org/grails/web/databinding/GrailsWebDataBindingListener.groovy cost 22s; http://ci.groovy-lang.org/viewLog.html?buildId=33761&tab=testsInfo&buildTypeId=Groovy_Antlr4grammar |
@danielsun1106 : I think (and hope) that the test in question is impacted by something outside of the test suite (such as noisy neighbors in the VM, or even clock skew). Nothing in the parsing of that fairly short file should give us that kind of performance, and the prior tests took much shorter time. |
@jespersm : Unfortunately, parsing "GrailsWebDataBindingListener.groovy" really costs a lot of time. On my machine it costs about 36s... I extracted the code snippet as follows, parsing which costs most of the time: // costs about 30s
String[] codes = [
className + '.' + propertyName + '.typeMismatch.error',
className + '.' + propertyName + '.typeMismatch',
classAsPropertyName + '.' + propertyName + '.typeMismatch.error',
classAsPropertyName + '.' + propertyName + '.typeMismatch',
bindingResult.resolveMessageCodes('typeMismatch', propertyName)
].flatten() as String[] // costs about 1s
String[] codes = [
].flatten() as String[] |
In order to improve the performance when parsing large numbers of files, I plan to implement a LRU cache, which will replace the default PredictionContextCache. ps: Guava is developed by Google and licenced under APL2 |
the problem is the size of the guava library with 2+ MB and their compatibility issues with other guava versions. If you base it on their source it should be ok, since it is APL2 |
I see. Thanks :-) |
@danielsun1106 One of the areas of optimization in my fork of ANTLR 4 is the construction and storage of |
@sharwell Can I get the latest version(merged 4.5.3 codes from the antlr/antlr4) via "com.tunnelvisionlabs:antlr4" as usual? I will give it a try :-) Finally, Could you tell whether the optimized fork is licensed under APL2? ps: I tried to cache PredicationContext instances via LRU cache, no memory leak but still very slow... Cheers, |
http://mvnrepository.com/artifact/com.tunnelvisionlabs/antlr4/4.5.3 It is licensed under BSD, same with antlr/antlr4 :-) |
@sharwell |
@danielsun1106 The lexer and parser each store a DFA. You can clear the DFA on either to release the memory used by it, but doing so means the next time you parse a file it will have to rebuild all required sections of the DFA it needs for parsing. Typically the lexer DFA remains very small relative to the parser DFA, so in practice I've only ever needed to clear the latter. // Clear a lexer DFA:
lexer.getInterpreter().atn.clearDFA();
// Clear a parser DFA:
parser.getInterpreter().atn.clearDFA();
|
@sharwell |
@danielsun1106 I don't think the 💡 The memory characteristics of the two forks are dramatically different. Make sure to not reuse results from analyzing the reference release when looking for ways to improve the optimized release. That said, if you do find ways to improve things it would be a nice addition. 😀 |
That's great! I'll try later :-)
|
@sharwell Because we have to clearDFA before parsing each time, how about making each parser has its own DFA array and context cache and initialize DFA array and context cache when creating the parser, which will help us remove the synronization and gain better performance. // Groovy script will be accessed concurrently in the production environment. The suggestion is based on the following content :-) |
The DFA cache is a concurrent data structure that is designed and intended to be used in concurrent parsing scenarios without synchronization. The fast path (the case where DFA states already exist for the current input) does not have any synchronization at all. Assigning separate DFA instances to different parsers is a substantial waste of computing resources (the DFA will be recomputed and the memory will be multiplied by the the number of concurrent parser instances). Based on the evidence provided so far, my suggestion is do not call |
@sharwell |
@danielsun1106 I'm not sure about the reference release, but the optimized version only caches |
@sharwell Then I have to clearDFA before parsing, completing all test cases costs about 14 minutes on my machine(Note antlr/antlr4 costs 11~12 minutes). At last I try to use the two-stage parsing strategy, optimized antlr4 costs 11~12 minutes(almost same with antlr/antlr4). |
We need to solve both issues. However, for long-running instances such as application servers, an unbounded cache is not very good. If we can reset or trim this cache at (configurable) intervals, we can at least work around the issue. |
@danielsun1106 Is there a branch where I can check out and run those tests easily? Sometimes there are small non-functional changes I can make to the grammar or use site to make a big perf difference. |
@jespersm Interval-based clearing of the cache is certainly one approach. You can do it safely like this:
In the above approach,
|
@sharwell |
@danielsun1106 Keep in mind that I don't need the branch clean, I just need it to work. If I can get it running on a reasonably sized test scenario I can typically make a big improvement in not much time. 😄 |
@sharwell To run the tests, you need to fetch https://github.com/jespersm/groovy and checkout the antlr4 branch, and run |
@sharwell |
@sharwell
The test result report can be found at If you want to run test cases again, executing ps: We create parser and start parsing at org.codehaus.groovy.parser.antlr4.ASTBuilder public ModuleNode buildAST() {
this.parser.getInterpreter().setPredictionMode(PredictionMode.SLL);
this.parser.removeErrorListeners();
this.parser.setErrorHandler(new BailErrorStrategy());
try {
this.startParsing(this.parser);
} catch (RuntimeException e) {
if (log.isLoggable(Level.FINE)) {
log.fine(e.getMessage());
}
((CommonTokenStream) this.parser.getInputStream()).reset();
this.setupErrorListener(this.parser);
this.parser.setErrorHandler(new DefaultErrorStrategy());
this.parser.getInterpreter().setPredictionMode(PredictionMode.LL);
this.startParsing(this.parser);
}
this.addClasses();
return this.moduleNode;
} |
In order to improve the whole performance and maintainability, I am rewriting the parser, which is based on the Java grammar updated by @sharwell (https://github.com/antlr/grammars-v4/blob/master/java/Java.g4). The following performance issue does not exist in the new parser( daniellansun/groovy-parser@9950cd6 ) // costs about 30s
String[] codes = [
className + '.' + propertyName + '.typeMismatch.error',
className + '.' + propertyName + '.typeMismatch',
classAsPropertyName + '.' + propertyName + '.typeMismatch.error',
classAsPropertyName + '.' + propertyName + '.typeMismatch',
bindingResult.resolveMessageCodes('typeMismatch', propertyName)
].flatten() as String[] |
@sharwell provided a useful advice:
"You can save a great deal of time on correct inputs by using a two-stage parsing strategy.
antlr/antlr4#192
The text was updated successfully, but these errors were encountered: