[antlr-interest] ANTLR performance
Lorenzo de Lara
ldelara at affsys.com
Tue May 11 07:35:20 PDT 2010
I have noticed the same thing with rewrite=true and came upon this bug report from 2008, which is currently still open:
http://www.antlr.org/jira/browse/ANTLR-371
The problem is parsers with rewrite rules run in non-linear time on any inputs above a few hundred rewrites. I've verified this in both Java and C#. You can verify this for yourself by commenting out your rewrite rules and running the parser and observing much closer to linear runtime. (5 minutes with rewrite rules on vs. 5 seconds rewrite rules off on a typical 1500 line input for us) The offending method is GetKindOfOps in TokenRewriteStream taking up to 100% of the runtime according to a Java profiling tool.
I've implemented the proposed fix (in Java) which does away with calling GetKindOfOps completely and can confirm it does result in much more reasonable, linear-like performance, without introducing any new problems, as far as I can tell.
-Lorenzo
On 2010-05-11, at 5:17 , Chrobot, Stefan wrote:
Hi,
I'm using ANTLR with the C# target. The generated parser performs too
slow for my needs. My grammar uses k = 6.
Does it have a performance impact? What value should I target to get
optimum performance - 1 or *? Would changing the grammar to 1/* give
significant performance boost?
Stefan
List: http://www.antlr.org/mailman/listinfo/antlr-interest
Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address
More information about the antlr-interest
mailing list